汉诺塔

public class HanoiTower {
    // 移动次数计数器
    private static int moveCount = 0;
    
    // 1. 基本递归版（打印移动步骤）
    public static void hanoiBasic(int n, char source, char auxiliary, char target) {
        // 基线条件：只有一个圆盘时直接移动
        if (n == 1) {
            moveCount++;
            System.out.printf("步骤%d: 从%c移动到%c\n", moveCount, source, target);
            return;
        }
        
        // 递归步骤1：将n-1个圆盘从源柱移到辅助柱
        hanoiBasic(n - 1, source, target, auxiliary);
        
        // 步骤2：将第n个圆盘从源柱移到目标柱
        moveCount++;
        System.out.printf("步骤%d: 从%c移动到%c\n", moveCount, source, target);
        
        // 递归步骤3：将n-1个圆盘从辅助柱移到目标柱
        hanoiBasic(n - 1, auxiliary, source, target);
    }
    
    // 2. 优化版1：计数不打印（高效计算移动次数）
    public static long hanoiCountOnly(int n) {
        // 数学公式：n个圆盘需要2^n - 1次移动
        return (1L << n) - 1; // 等价于2^n - 1（仅适合n<=63）
    }
    
    // 3. 优化版2：非递归实现（用栈模拟递归，避免栈溢出）
    public static void hanoiNonRecursive(int n, char source, char auxiliary, char target) {
        java.util.Stack<int[]> stack = new java.util.Stack<>();
        // 入栈参数：n, source, auxiliary, target, 是否处理过（0=未处理，1=已处理）
        stack.push(new int[]{n, source, auxiliary, target, 0});
        moveCount = 0;
        
        while (!stack.isEmpty()) {
            int[] current = stack.pop();
            int num = current[0];
            char s = (char) current[1];
            char a = (char) current[2];
            char t = (char) current[3];
            int processed = current[4];
            
            if (num == 1) {
                // 单个圆盘直接移动
                moveCount++;
                System.out.printf("步骤%d: 从%c移动到%c\n", moveCount, s, t);
            } else if (processed == 0) {
                // 第一次处理，按逆序入栈（栈是LIFO）
                stack.push(new int[]{num, s, a, t, 1});          // 标记为已处理
                stack.push(new int[]{num - 1, a, s, t, 0});      // 步骤3
                stack.push(new int[]{num, s, a, t, 2});          // 步骤2（实际移动）
                stack.push(new int[]{num - 1, s, t, a, 0});      // 步骤1
            } else if (processed == 2) {
                // 执行实际移动操作
                moveCount++;
                System.out.printf("步骤%d: 从%c移动到%c\n", moveCount, s, t);
            }
        }
    }
    
    // 4. 优化版3：大数量圆盘的移动次数计算（支持n>63）
    public static String hanoiBigCount(int n) {
        // 使用字符串计算2^n - 1，避免长整数溢出
        StringBuilder result = new StringBuilder("1");
        // 计算2^n
        for (int i = 0; i < n; i++) {
            result = multiplyByTwo(result);
        }
        // 减1
        return subtractOne(result).toString();
    }
    
    // 辅助方法：字符串表示的数字乘以2
    private static StringBuilder multiplyByTwo(StringBuilder num) {
        int carry = 0;
        for (int i = num.length() - 1; i >= 0; i--) {
            int digit = num.charAt(i) - '0';
            int product = digit * 2 + carry;
            num.setCharAt(i, (char) (product % 10 + '0'));
            carry = product / 10;
        }
        if (carry > 0) {
            num.insert(0, carry);
        }
        return num;
    }
    
    // 辅助方法：字符串表示的数字减1
    private static StringBuilder subtractOne(StringBuilder num) {
        int i = num.length() - 1;
        while (i >= 0 && num.charAt(i) == '0') {
            num.setCharAt(i, '9');
            i--;
        }
        if (i < 0) {
            return new StringBuilder("0");
        }
        num.setCharAt(i, (char) (num.charAt(i) - 1));
        // 移除前导零
        if (num.charAt(0) == '0' && num.length() > 1) {
            return new StringBuilder(num.substring(1));
        }
        return num;
    }
    
    public static void main(String[] args) {
        int n = 3;
        System.out.println("=== 基本递归版（n=" + n + "）===");
        moveCount = 0;
        hanoiBasic(n, 'A', 'B', 'C');
        
        System.out.println("\n=== 非递归版（n=" + n + "）===");
        hanoiNonRecursive(n, 'A', 'B', 'C');
        
        System.out.println("\n=== 移动次数计算 ===");
        System.out.println("n=10的移动次数: " + hanoiCountOnly(10));
        System.out.println("n=100的移动次数: " + hanoiBigCount(100));
    }
}