k-杆汉诺塔的最优移动次数  

Optimal Number of Moving Discs in the Tower of Hanoi with k-Pegs

作　　者：王勇明[1] 许道云[1] WANG Yongming XU Daoyun(College of Computer Science and Technology, Guizhou University, Guiyang 550025, Chin)

机构地区：[1]贵州大学计算机科学与技术学院,贵州贵阳550025

出　　处：《贵州大学学报（自然科学版）》2017年第3期62-65,共4页Journal of Guizhou University:Natural Sciences

基　　金：国家自然科学基金项目(61262006)

摘　　要：经典的汉诺塔问题只带三根杆,当圆盘数为n时,最优移动次数为H_3(n)=2~n-1。对于带k杆的汉诺塔问题,最优移动次数满足递归关系H_k(n)=2H_k(l_k(n))+H_(k-1)(n-l_k(n)),其中最优剖分数l_k(n)=min{l:arg_lmin{2H_k(l)+H_(k-1)(n-l)}}依赖于n,k。由于m<k时,H_k(m)=2m-1,边界条件为l_3(n)=n-1,l_k(m)=0(m<k)。The optimal number of moving discs is H_3（ n） = 2~n-1 in the classical Hanoi tower with three pegs and n discs. For the tower of Hanoi with k pegs,the optimal number satisfies the equation H_k（ n） = 2H_k（ l_k（ n）） ＋H_（k-1）（ n-lk（ n）） where the optimal partition number l_k（ n） = min{ l： arg_lmin{ 2H_k（ l） ＋H_（k-1）（ n-l） } } depending on n,k,H_k（ m） = 2m-1 for mk and the boundary condition l_3= n-1,l_k（ m） = 0（ mk）.

关 键 词：多杆汉诺塔 最优移动方案 移动次数 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]