https://projecteuclid.org/journals/bulletin-of-the-belgian-mathematical-society-simon-stevin/volume-21/issue-5/La-quatrième-tour-de-Hanoï/10.36045/bbms/1420071861.full

中文的翻译：https://www.cnblogs.com/british-union/p/18030547/frame-stewart#!comments

Frame-Stewart 算法

对于有 $N$ 个圆盘和 $p(p \geqslant3)$ 个柱子的汉诺塔，该算法寻找 $1 \leqslant l \lt N$，使得以下步骤得到操作次数最小：

• 把前 $l$ 个圆盘通过 $p$ 个柱子移到一个非目标柱子上。
• 把剩下的圆盘通过 $p−1$ 个柱子移到目标柱子上去。
• 把前 $l$ 个通过 $p$ 个柱子移到目标柱子上。

设其答案为 $\Phi(p, N)$，有：

$$ \Phi(p, N) = \displaystyle \min_{ 1 \leqslant l < N }{\color{Red} (}2 \Phi{\color{Green} (}p, l{\color{Green} )} + \Phi{\color{Green} (}p - 1, N - l{\color{Green} )}{\color{Red} )} $$

边界条件：$\Phi(3, N) = 2^N - 1,\Phi(p, 1) = 1$。

按：此处的 3 个柱子，N 个圆盘的情况，是比较容易证明的，可以用归纳法来证明。

有关 $\Psi$ 和 $\Phi$ 的代数性质

有必要引入几个重要函数及其性质来辅助证明定理 $9$ 和定理 $10$。

设

$$ [n] = \{ 0, 1, \dots, n - 1 \} $$

$$ \Delta(n) = n(n + 1) / 2, \ \nabla(n) =  max\{k \geqslant 0 \ | \ \Delta(k) \leqslant n) $$

$$ \Phi(n) = \sum_{i = 0}^{n - 1} 2^{\nabla(i)} $$

此时有 $\Delta u = u + \Delta(u - 1)$。

参考文献 $2$ 指出，

$$ \Phi(n) = \min_{0 \leqslant m < n} 2\Phi(m) + 2^{n - m} - 1 $$