Hanoi tower（河内塔）问题

luyuanhong

题  有三个杆子，一个杆子上从上到下有 n 个从小到大的环，要求将这些环逐步移动到

另一个杆子上，移动时大环不能放在小环上，问：最少要移动几次？

解  设 n 个环从一个杆子移动到另一个杆子，最少要移动 a(n) 次。

    现在考虑有 n+1 个环的问题。

    移动中，总是有一步要将最大的第 n+1 个环移到另一个杆子上。而在此之前，必须要

将在这最大环上面的 n 个环移走，移到第三根杆子上。移动这 n 个环，最少要 a(n) 次。

然后移动 1 次，将最大的第 n+1 个环移到另一个杆子上。然后，还需要将在第三根杆子上

的 n 个环移动到最大的第 n+1 个环上面。移动这 n 个环，又最少要 a(n) 次。所以，n+1

个环最少要移动 a(n)+1+a(n) = 2a(n)+1 次。

   也就是说，有递推公式： a(n+1) = 2a(n)+1 ，n=1,2,3,… 。

   下面，用数学归纳法证明：a(n) = 2^n-1 ，n=1,2,3,… 。

（1）当 n=1 时，最少要移动一次，a(1) = 2^1-1 = 1 ，结论显然成立。

（2）设已知对某个给定的正整数 n ，结论成立，有 a(n) = 2^n-1 ，下面看 n+1 时的情形：

    a(n+1) = 2a(n)+1 = 2×(2^n-1)+1 = 2^(n+1)-2+1 = 2^(n+1)-1 。

    可见，n+1 时结论也成立。

（3）所以，对任何正整数 n ，结论都成立。

11111qqqq

这个问题很早以前就解决了