# 积木塔

## 解法与署名

首选出题人的汉诺塔递归，采用配套讲解中“由递归参数直接确定积木编号”的实现，程序为 [std.cpp](std.cpp)。Codex（GPT-6）整理完整行读入及输出格式，不需要模拟平台上的积木数组。

[按步号生成移动](solution-alternative.zh.md)是同阶复杂度、不同构造方式的备用方案，程序为 [alternative.cpp](alternative.cpp)。它使用经典汉诺塔移动规律，直接计算本步的积木和平台；该规律不归为模型原创。

## 用初始位置表示大小关系

从底到顶把积木编号为 $0,1,\ldots,n-1$ .较大的编号只能放在较小编号上方。名字只用于输出，不能据名字排序。

定义过程 $\operatorname{Move}(i,a,b,c)$ ：把编号 $i$ 到 $n-1$ 的整座塔从平台 $a$ 搬到 $b$ ，借助 $c$ .若 $i=n$ ，不做操作；否则依次执行：

1. $\operatorname{Move}(i+1,a,c,b)$ .
2. 把积木 $i$ 从 $a$ 移到 $b$ ，输出一行。
3. $\operatorname{Move}(i+1,c,b,a)$ .

初始调用为 $\operatorname{Move}(0,0,1,2)$ ，平台下标对应输入名字的顺序。

## 合法性与最优性

对塔高归纳。上层积木先被合法移走，底部积木于是可以移到目标平台，再把上层塔合法放到它上面，得到正确目标状态。

设移动 $k$ 块的最少次数为 $F(k)$ .最底部积木第一次移动前，其余 $k-1$ 块必须搬到剩下的一个平台；它最后移入目标平台后，上层塔还须搬到目标平台。因此至少需要 $2F(k-1)+1$ 次。递归构造恰好达到这个下界。

$$F(0)=0,\qquad F(k)=2F(k-1)+1=2^k-1$$

达到下界时，最底部只移动一次，两段子问题也必须最优；继续归纳可知三平台问题的最短身份移动序列唯一。即使名字重复，输出文字也由该序列确定。

## 字符串与复杂度

读完 $n$ 后忽略该行剩余内容，再用 `getline` 读取每个名字。不要分词读名字，也不要去掉行首或行尾空格。输出时将完整名字直接嵌入模板，名字与模板自带的空格都须保留。

设 $H$ 为输入名字字符总数，$Z$ 为输出字符总数。总时间为 $O(H+Z+n)$ ，其中递归产生 $2^n-1$ 次移动；存储名字和递归栈共需 $O(H+n)$ 空间。当前上限对应 $1023$ 次移动。

## 验证与使用

固定种子的十份正式输入配方见 `tests/plan.json` .先自行编译程序，再运行：

```text
python tests/generate.py --out-dir <output-directory> --std <compiled-program>
```

省略 `--std` 仅生成输入；`--case 01` 选择指定用例。小规模独立验证见 [check_r16.py](../../../tools/check_r16.py)，范围校验见 [validate_r16.py](../../../tools/validate_r16.py)。五轮时间、内存、输入和程序哈希见[测量记录](../../../docs/benchmark-R16.json)。环境与校准方法见[评测说明](../../../docs/评测环境与性能.md)。

## 实测结果

Intel Core Ultra 9 275HX、Windows 11、GCC 16.2.0、C++17 -O2。两份程序在相同十份正式输入上交替运行五轮。时间取每个用例中位数的最大值，包含启动与输入输出；峰值工作集独立测量，包含运行时开销。

| 程序与算法 | 最慢中位数（秒） | 峰值（MiB） | 0.5 秒参考时限 |
| --- | ---: | ---: | --- |
| [汉诺塔递归](std.cpp) | 0.029726 | 5.31 | 已测输入通过 |
| [按步号构造](alternative.cpp) | 0.031369 | 5.30 | 已测输入通过 |

时限由标程最慢中位数乘以 2，向上取整到 0.5 秒得到。原始轮次、输入、源码和程序哈希见[测量记录](../../../docs/benchmark-R16.json)。其他评测机需重新校准；这些测量只描述随附实现及已测输入。