Octave / MATLAB 第68题：递归函数算法：汉诺塔移动步骤打印

题目

编写递归函数 <code>hanoi(n, from_rod, to_rod, aux_rod)</code>，打印将 n 个圆盘从源柱子 A 借助辅助柱 B 移动到目标柱 C 的详细步骤，并统计总移动次数（$2^n - 1$）。

输入格式：无需外部输入（测试 n = 3）。

输出格式：分行打印圆盘每一步的移动轨迹以及总步数。

数据范围与约定：递归结构。

思路与算法

1. 汉诺塔递归分治原理
三步走策略：① 先把上面 $n-1$ 个盘子从 A 移到 B（借助 C）；② 把第 $n$ 个底盘直接从 A 移到 C；③ 再把那 $n-1$ 个盘子从 B 移到 C（借助 A）。

2. 递归基（Base Case）
当 $n=1$ 时直接完成单步移动，这是递归终止的锚点。

3. 步数理论值
移动 $n$ 阶汉诺塔需要严格 $2^n - 1$ 步。

完整程序

% Octave / MATLAB 第68题：递归实现汉诺塔
1;

% 全局计数器
global move_count;
move_count = 0;

function hanoi(n, from_p, to_p, aux_p)
    global move_count;
    if n == 1
        move_count = move_count + 1;
        fprintf("步骤 %d: 将圆盘 1 从 %s -> %s\n", move_count, from_p, to_p);
        return;
    end
    % 1. 把上面 n-1 个盘子移到辅助柱
    hanoi(n - 1, from_p, aux_p, to_p);
    
    % 2. 移动第 n 个大盘到目标柱
    move_count = move_count + 1;
    fprintf("步骤 %d: 将圆盘 %d 从 %s -> %s\n", move_count, n, from_p, to_p);
    
    % 3. 把辅助柱上的 n-1 个盘子移到目标柱
    hanoi(n - 1, aux_p, to_p, from_p);
end

% 主程序
disks = 3;
fprintf("=== %d 阶汉诺塔移动步骤 ===\n", disks);
hanoi(disks, 'A', 'C', 'B');
fprintf("总移动步数: %d (理论值 2^%d - 1 = %d)\n", move_count, disks, 2^disks - 1);

运行示例

输出：

=== 3 阶汉诺塔移动步骤 ===
步骤 1: 将圆盘 1 从 A -> C
步骤 2: 将圆盘 2 从 A -> B
步骤 3: 将圆盘 1 从 C -> B
步骤 4: 将圆盘 3 从 A -> C
步骤 5: 将圆盘 1 从 B -> A
步骤 6: 将圆盘 2 从 B -> C
步骤 7: 将圆盘 1 从 A -> C
总移动步数: 7 (理论值 2^3 - 1 = 7)