链接
传送门
题意
用四个柱子进行的汉诺塔游戏。每次把前\(k\)个盘子放到第四个柱子上，然后按照三个柱子的汉诺塔玩法把剩余盘子转移到目标柱子上，最后把第四个柱子上的盘子转移到目标柱子上。输出转移\(n\)个盘子到目标柱子上的最少移动次数。
思路
思路出自：D_Double's Journey
设\(g[n]\)为三根柱子的汉诺塔移动\(n\)个圆盘所需最少步数，\(f[n]\)为四根柱子所需要的最少步数。可得\(f[n] = min(f[k] \times 2 + g[n - k])\)。打表求出前几项后可以得出规律。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| f[1] = 1
----------------
f[2] = 3, f[2] = f[1] + 2^1
f[3] = 5, f[3] = f[2] + 2^1
共 2 个 2^1
----------------
f[4] = 9, f[4] = f[3] + 2^2
f[5] = 13, f[5] = f[4] + 2^2
f[6] = 17, f[6] = f[5] + 2^2
共 3 个 2^2
----------------
f[7] = 25, f[7] = f[6] + 2^3
f[8] = 33, f[8] = f[7] + 2^3
f[9] = 41, f[9] = f[8] + 2^3
f[10] = 49, f[10] = f[9] + 2^3
共 4 个 2^3
|
代码
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
| import java.math.*;
import java.util.*;
public class Main {
static final int maxn = 10010;
public static void main(String[] args) {
BigInteger[] a = new BigInteger[maxn];
a[0] = BigInteger.ZERO;
BigInteger k = BigInteger.ONE;
int i = 1, cnt = 1;
while (i < maxn) {
for (int j = 0; j < cnt && i < maxn; ++j) {
a[i] = a[i - 1].add(k);
++i;
}
k = k.add(k);
++cnt;
}
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
System.out.println(a[sc.nextInt()]);
}
}
}
|