四柱汉诺塔的研究-转载

Rubidium_Chloride · 2022-06-22 19:12:10 · 题解

和小粉兔吵了一架，小粉兔说是对的，那么小粉兔审这个题解的时候得给过。

参考资料：知乎

论文

这里不赘述证明过程，只是作为一个转载告诉大家这个结论被证明了。

主要证明的有以下几个结论：

第一个：（详情见论文）一个叫做 Frame-Stewart algorithm 的柿子，令 n 个盘，p 个柱子，则这个算法的步数 \Phi(p,n) 满足 \Phi(p,n)=\min\limits_{1\le l<n}\{2\Phi(p,l)+\Phi(p-1,N-l)\} 在 n=4 的时候是最优解。

然后第一份资料则说明了 n=4 的时候具有通项。

直接从知乎拿图过来。

有什么用？增加一根柱子的步数复杂度变低了。

变成了

。

以上主要内容转自知乎和论文。

之前一直不知道这个被 close 了，补个档。