UVA 10254 The Priest Mathematician 題解：四柱漢諾塔最優移動次數的規律與大數計算

題目大意

四柱漢諾塔（Reve's Puzzle）。n 個盤子從 A 移到 D，借助 B、C。求最少移動次數。n ≤ 10000，結果極大，需大整數。

Frame-Stewart 算法規律

最優策略：先用四柱移走 k 個盤子到中間柱，再用三柱移走剩餘 n-k 個到目標柱，最後用四柱移走 k 個疊上。最優 k 無簡單閉式，但本題數列呈現明顯規律：

f[1] = 1
f[2] = f[1] + 2^1
f[3] = f[2] + 2^1          // 2^1 重複 2 次
f[4] = f[3] + 2^2
f[5] = f[4] + 2^2
f[6] = f[5] + 2^2          // 2^2 重複 3 次
f[7] = f[6] + 2^3
...                         // 2^k 重複 k+1 次

預計算大整數

Java BigInteger 實現：

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
    static BigInteger f[] = new BigInteger[10005];
    static void init() {
        f[0]=BigInteger.ZERO; f[1]=BigInteger.ONE;
        int k=1, j=2;
        while (j<=10000) {
            BigInteger add = BigInteger.ONE.shiftLeft(k); // 2^k
            for (int i=0; i