4杆汉诺塔的最优移动次数

通常汉诺塔问题只带三根杆,当圆盘数为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杆汉诺塔问题

通常汉诺塔问题只考虑带3根杆,当圆盘数为n时,最佳方案的移动次数为H(n)=2 n?1。本文考虑带4杆的汉诺塔问题及其移动方案[(1?α),α,0,0]。一个有趣的问题是:对于0<α<1,当α取什么值时,n≥240时,最优方案的α值稳定在0.9。