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

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

## 本步移动哪一块

这里将最上方、最小的积木编号为 $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)$ 空间，除此之外仅需常数状态。此方案避免递归栈，但对名字存储后的总体空间阶没有改变。作为直接按编号生成的备用方案，当前计时见[主解](solution.zh.md#实测结果)。