| 4杆汉诺塔的最优移动次数 |
| |
| 引用本文： | 许道云.4杆汉诺塔的最优移动次数[J].贵州大学学报(自然科学版),2012,29(5):49-52,62. |
| |
| 作者姓名： | 许道云 |
| |
| 作者单位： | 贵州大学计算机科学与信息学院,贵州 贵阳,550025 |
| |
| 基金项目： | 基金项目：国家自然科学基金（No.6126006） |
| |
| 摘 要： | 通常汉诺塔问题只带三根杆,当圆盘数为n时,最优移动次数为T3(n)=2n-1.对于带4杆的汉诺塔问题,最优移动次数满足关系T4(n)=2T4(m)+T3(n-m),其中m=arglmin{2T4(l)+T3(n-l)}依赖于n.对于正数整k,当k(k-1)/2+1≤n≤k(k+1)/2,n=k(k-1)/2+l时,T4(n)=(l+k-2)2k-1+1.特别,T4(sk)=2T4(sk-1)+T3(k),其中s0=0,sk=sk-1+k(k≥1).
|
| 关 键 词： | 4杆汉诺塔 最优移动方案 移动次数 |
Optimal Number of Moving Discs in the Tower of Hanoi with Four Pegs |
| |
| XU Dao-yun.Optimal Number of Moving Discs in the Tower of Hanoi with Four Pegs[J].Journal of Guizhou University(Natural Science),2012,29(5):49-52,62. |
| |
| Authors: | XU Dao-yun |
| |
| Institution: | XU Dao-yun ( College of Computer Science and Information, Guizhou University, Guiyang 550025, China) |
| |
| Abstract: | The optimal number of moving discs is T3 （n） = 2n - 1 in the tower of Hanoi with three pegs and n discs. For the tower of Hanoi with four pegs, the optimal number satisfies the equation T4 （n） = 2 T4 （m） ＋ T3 （ n-m） ,where m = arg, mint2T4（l） ＋ T3（n - l） } depending on n. Given k（k-1）/2＋1≤n≤k（k＋1）/2 and n=k（k - 1）/2 ＋ l for some integers k and 1, T4（n） = （l ＋ k - 2）2^k-1 ＋ 1. Specially, T4（sk） = 2T4（sk-1） ＋T3（k） ,whereso = O,sk = sk-1 ＋ k（k ≥ 1）.. |
| |
| Keywords: | Tower of Hanoi with four pegs optimal frame of moving number of moving |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
