积木塔：按步号生成移动¶

Codex（GPT-6）整理并验证经典汉诺塔的步号构造，程序为 alternative.cpp。首选的递归构造及最优性证明见主解。

本步移动哪一块¶

这里将最上方、最小的积木编号为 \(d=1\) ，最底部为 \(d=n\) .第 \(t\) 步从 \(1\) 开始计数，令

\[ d=1+\nu_2(t) \]

其中 \(\nu_2(t)\) 是 \(t\) 中因子 \(2\) 的个数。这正是本步移动的积木；它对应输入名字数组中的下标 \(n-d\) .

平台按 \(A,B,C\) 编为 \(0,1,2\) .该积木始终按固定循环方向移动：若 \(n-d\) 为偶数，则每次平台编号加 \(1\) 模 \(3\) ；否则加 \(2\) 模 \(3\) .记这一增量为 \(\delta_d\) .

积木 \(d\) 的移动发生在 \(t=(2k+1)2^{d-1}\) ，此前已移动 \(k=\lfloor t/2^d\rfloor\) 次。因此本步来源和目标为

\[ a=k\delta_d\bmod3,\qquad b=(a+\delta_d)\bmod3 \]

依次枚举 \(t=1,\ldots,2^n-1\) ，按输出模板打印即可。

为什么等同于递归构造¶

对 \(n\) 归纳。中间步 \(t=2^{n-1}\) 只移动最底部积木，方向为 \(A\to B\) .中间步两侧分别是把上层塔从 \(A\) 搬到 \(C\)、从 \(C\) 搬到 \(B\) 的两个子问题。

每个子问题相对 \(n-1\) 块的标准问题交换了平台角色，使小积木的循环方向反转，正对应 \(n-d\) 奇偶性的变化；后半段继续累计此前的移动次数。每个编号 \(d<n\) 的出现位置仍是奇数乘 \(2^{d-1}\) ，而两段的连接处由最大的编号占据。由此，积木编号、每块累计移动次数和平台方向都与递归序列一致，故输出合法且最优。

复杂度与使用¶

实现用不断除以 \(2\) 计算 \(\nu_2(t)\) .全部步骤的额外除法次数小于 \(2^n\) ，因为含至少 \(j\) 个因子 \(2\) 的步数为 \(\lfloor(2^n-1)/2^j\rfloor\) ，对 \(j\ge1\) 求和小于 \(2^n\) .

因此时间仍为 \(O(H+Z+n)\) ，\(H\) 为输入名字字符数，\(Z\) 为输出字符数；存储名字需要 \(O(H+n)\) 空间，除此之外仅需常数状态。此方案避免递归栈，但对名字存储后的总体空间阶没有改变。作为直接按编号生成的备用方案，当前计时见主解。