UVa 10254 - the Priest Mathematician

链接

传送门

题意

用四个柱子进行的汉诺塔游戏。每次把前$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
22^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
32^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
42^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()]);
}
}
}

支付宝扫码领红包