UVA10254 - The Priest Mathematician（找規律）
題目鏈接
題目大意：4根柱子的漢諾塔。
解題思路：題目裡面有提示，先借助四個柱子移走k個，然後在借助三個柱子移走剩余的n - k個，再把n個移動到n - k個所在柱子。那麼F[n] = min(2 * F[k] + H[n - k]);H[n - k] = 2^(n - k) - 1;把前面的60項打出來，再打印出F[n] - f[n - 1],會發現規律：
F[1] = 1；
F[2] = F[1] + 2^1;
F[3] = F[2] + 2^1;(2個)
f[4] = f[3] + 2^2;
f[5] = f[4] + 2^2;
f[6] = f[5] + 2^2;（3個）
F[7] = f[6] + 2^3;
... (4個)
但是n到達10000，結果要用到大數。
代碼：
import java.util.*;
import java.math.*;
import java.io.*;
public class Main {
static BigInteger f[] = new BigInteger[10005];
public static void init () {
f[0] = BigInteger.ZERO;
f[1] = BigInteger.valueOf(1);
int k = 1, j = 2;
BigInteger addnum;
while (j <= 10000) {
addnum = BigInteger.valueOf(1).shiftLeft(k);
for (int i = 0; i < k + 1 && j <= 10000; i++, j++)
f[j] = f[j - 1].add(addnum);
k++;
}
}
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
init();
while (cin.hasNext()) {
int n = cin.nextInt();
System.out.println(f[n]);
}
}
}
