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

经典的汉诺塔问题只带三根杆,当圆盘数为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)。