UVa 254 - Towers of Hanoi

链接

传送门

题意

给出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]);
}
}
}