UVa 254 - Towers of Hanoi

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出Hanoi塔的圆盘数\(n\)和已经移动的步数\(m\)，输出三个根柱子上圆盘的个数。当\(n\)为偶数时，目标柱子为第三根；\(n\)为奇数时，为第二根。

思路

从\(n\)到1以此判断每个盘子的位置，若操作次数不小于\(2^{n-1}\)，则当前盘子已经搬到目标位置，都则留在原地。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//package main;

import java.util.*;
import java.math.*;

public class Main {

    static int[] ans = new int[3];
    static BigInteger[] e = new BigInteger[110];

    public static void dfs(int s, int tmp, int t, int n, BigInteger m) {
        if (n == 0) {
            return;
        }
        if (m.compareTo(e[n - 1]) != -1) {
            ++ans[t];
            dfs(tmp, s, t, n - 1, m.subtract(e[n - 1]));
        }
        else {
            ++ans[s];
            dfs(s, t, tmp, n - 1, m);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        e[0] = BigInteger.ONE;
        for (int i = 1; i < 110; ++i) {
            e[i] = e[i - 1].multiply(BigInteger.valueOf(2));
        }
        while (sc.hasNext()) {
            int n = sc.nextInt();
            BigInteger m = sc.nextBigInteger();
            if (n == 0 && m.compareTo(BigInteger.ZERO) == 0) {
                break;
            }
            ans[0] = ans[1] = ans[2] = 0;
            if (n % 2 == 0) {
                dfs(0, 1, 2, n, m);
            }
            else {
                dfs(0, 2, 1, n, m);
            }
            System.out.println(ans[0] + " " + ans[1] + " " + ans[2]);
        }
    }
}
相关文章