汉诺塔的两种非递归解法

yangtou

[code]
如同我们能求出fabonacci数列的表达式，一定能用归纳的办法解决hanoi问题。

1 基本规律：
        最容易看出的规律就是盘子移动的序列：
给盘子从小到大编号1，2，……，N,试验移动盘子则可以得到一个这样的盘子移动序列（可以叫他hanoi数列H(n)）：
1，2，1， 3， 1，2，1，    4      ，1，2，1， 3， 1，2，1，………
容易归纳出，1占据所有的奇数位，2占据所有序号可被2整除而不能被4整除的位，。。。。。。m占了能被2^(m-1)整除而不能被2^m整除的所有的位置。。。。。。。。由此可得，对m=((p*2^k) + 2^k-1),H(m)=k。很容易用数学归纳法证明。
这样就可以随机得到某一步所移动的盘子了。

另一方面，还要确定某一个盘子是往哪而移动的。这一点不容易直接想到，但是通过实验可以发现，在某一个盘子数N下，1号盘子的移动方向总是一定的。方向一定就是说，总是按照1