tips2：汉诺塔知识

 

虽然搞程序多年了，对递归算法还是有些打怵。递归本身好理解，但其各层嵌套却容易将人绕晕，递归的汉诺塔问题就将我搞晕了多次。我搜了好多资料，也查阅了好多书籍，但都是泛泛而谈，不够详细，下面是我精心总结一下汉诺塔问题。

汉诺塔的问题：（百度百科引用）

**汉诺塔问题是源于印度一个古老传说的益智玩具。[大梵天]{.ul}创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
**

或许下面的解释会好理解一些：
现在要求庙里的老和尚把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子。

1、此时老和尚（后面我们叫他第1个和尚）觉得很难，所以他想：要是有一个人能把前63个盘子先移动到第二个柱子上，我再把最后一个盘子直接移动到第三个柱子，再让那个人把刚才的前63个盘子从第二个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他找了比他年轻的和尚（后面我们叫他第2个和尚）（呵呵，倚老卖老），命令：

① 你把前63个盘子移动到第二柱子上

② 在我自己把第64个盘子一道第三个柱子上后

③ 你把前63个盘子移动到第三柱子上

2、第2个和尚接了任务，也觉得很难，所以他也和第1个和尚一样想：要是有一个人能把前62个盘子先移动到第三个柱子上，我再把最后一个盘子直接移动到第二个柱子，再让那个人把刚才的前62个盘子从第三个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他也找了比他年轻的和尚（后面我们叫他第3和尚）（呵呵，又倚老卖老），命令：

① 你把前62个盘子移动到第三柱子上

② 在我自己把第63个盘子一道第二个柱子上后

③ 你把前62个盘子移动到第二柱子上

3、第3个和尚接了任务，又把移动前61个盘子的任务依葫芦话瓢的交给了第4个和尚，等等递推下去，直到把任务交给了第64个和尚为止（估计第64个和尚很郁闷，没机会也命令下别人，因为到他这里盘子已经只有一个了）。

4、到此任务下交完成，到各司其职完成的时候了。

完成回推了：

第64个和尚移动第1个盘子，把它移开，然后第63个和尚移动他给自己分

配的第2个盘子。第64个和尚再把第1个盘子移动到第2个盘子上。到这里第64个和尚的任务完成，第63个和尚完成了第62个和尚交给他的任务的第一步。

从上面可以看出，只有第64个和尚的任务完成了，第63个和尚的任务才能完成，只有第2个和尚—第64个和尚的任务完成后，第1个和尚的任务才能完成。这是一个典型的递归问题。

现在我们以有3个盘子来分析：

第1个和尚命令：

㈠ 第2个和尚你先把第一柱子前2个盘子移动到第二柱子。（借助第三个柱子）

㈡第1个和尚我自己把第一柱子最后的盘子移动到第三柱子。

㈢第2个和尚你把前2个盘子从第二柱子移动到第三柱子。

很显然，第㈡步很容易实现（哎，人总是自私地，把简单留给自己，困难的给别人）

其中第㈠步。第2个和尚他有2个盘子，他就命令：

① 第3个和尚你把第一柱子第1个盘子移动到第三柱子。（借助第二柱子）

② 第2个和尚我自己把第一柱子第2个盘子移动到第二柱子上。

③ 第3个和尚你把第1个盘子从第三柱子移动到第二柱子。

同样，第步很容易实现，但第3个和尚他只需要移动1个盘子，所以他也不用在下派任务了。（注意：这就是停止递归的条件，也叫边界值）

第㈢步可以分解为，第2个和尚还是有2个盘子，命令：

①第3个和尚你把第二柱子上的第1个盘子移动到第一柱子。

② 第2个和尚我把第2个盘子从第二柱子移动到第三柱子。

③第3个和尚你把第一柱子上的盘子移动到第三柱子。

分析组合起来就是：1→3 1→2 3→2 1→3 2→1 2→3
1→3共需要七步。如果是4个盘子，则第一个和尚的命令中第1步和第3步各有3个盘子，所以各需要7步，共14步，再加上第1个和尚的1步，所以4个盘子总共需要移动7+1+7=15步，同样，5个盘子需要15+1+15=31步，6个盘子需要31+1+31=63步……由此可以知道，移动n个盘子需要（2的n次方）–1步。

从上面整体综合分析可知把n个盘子从1座（相当第一柱子）移到3座（相当第三柱子）：

（1）把1座上（n-1）个盘子借助3座移到2座。

（2）把1座上第n个盘子移动3座。

（3）把2座上（n-1）个盘子借助1座移动3座。

下面用hanoi（n,a,b,c）表示把1座n个盘子借助2座移动到3座。

很明显，(1)步上是 hanoi(n-1,1,3,2)

(2)步上是hanoi(n-1,2,1,3)

下面是实现代码:

[cpp] [view
plaincopyprint?]{.ul}

  1. //汉诺塔问题

  2. #include

  3. using namespace std;

  5. //将编号为numdisk的盘子从init杆移至desti杆

  6. void moveOne(int numDisk, string init, string desti)

  7. {

  8. cout << “Move disk No. “ << numDisk << “ from “ << init

    << “ to “ << desti << endl;

  9. }

  10. //将numDisks个盘子从init杆借助temp杆移至desti杆

  11. void move(int numDisks, string init, string temp, string

    desti)

  12. {

  13. if(numDisks == 1)

  14. moveOne(1, init, desti);

  15. else

  16. {

  18. move(numDisks-1, init, desti,

    temp);//首先将上面的（numDisk-1）个盘子从init杆借助desti杆移至temp杆

  19. moveOne(numDisks, init, desti);

    //然后将编号为numDisks的盘子从init杆移至desti杆

  20. move(numDisks-1, temp, init,

    desti);//最后将上面的（numDisks-1）个盘子从temp杆借助init杆移至desti杆

  21. }

  22. }

  24. int main()

  25. {

  26. move(3, “A”, “B”, “C”);

  27. return 0;

  28. }

  29. /*

  30. //===============运行结果==================

  31. Move disk No. 1 from A to C

  32. Move disk No. 2 from A to B

  33. Move disk No. 1 from C to B

  34. Move disk No. 3 from A to C

  35. Move disk No. 1 from B to A

  36. Move disk No. 2 from B to C

  37. Move disk No. 1 from A to C

  38. 请按任意键继续. . .

  39. */

下面构造Hanoi类

[cpp] [view
plaincopyprint?]{.ul}

  1. //汉诺塔问题

  2. #include

  3. using namespace std;

  5. class Hanoi

  6. {

  7. public:

  8. Hanoi(int disks):totalDisks(disks){};

  9. void solve();

  10. private:

  11. int totalDisks;

  12. void move(int numDisks, string init, string temp, string

    desti);

  13. void moveOne(int numDisk, string init, string desti);

  14. };

  15. void Hanoi::solve()

  16. {

  17. string init = “A”;

  18. string temp = “B”;

  19. string desti = “C”;

  20. move(totalDisks, init , temp, desti);

  21. }

  22. //将编号为numdisk的盘子从init杆移至desti杆

  23. void Hanoi::moveOne(int numDisk, string init, string desti)

  24. {

  25. cout << “Move disk No. “ << numDisk << “ from “ << init

    << “ to “ << desti << endl;

  26. }

  27. //将numDisks个盘子从init杆借助temp杆移至desti杆

  28. void Hanoi::move(int numDisks, string init, string temp,

    string desti)

  29. {

  30. if(numDisks == 1)

  31. moveOne(1, init, desti);

  32. else

  33. {

  35. move(numDisks-1, init, desti,

    temp);//首先将上面的（numDisk-1）个盘子从init杆借助desti杆移至temp杆

  36. moveOne(numDisks, init, desti);

    //然后将编号为numDisks的盘子从init杆移至desti杆

  37. move(numDisks-1, temp, init,

    desti);//最后将上面的（numDisks-1）个盘子从temp杆借助init杆移至desti杆

  38. }

  39. }

  41. int main()

  42. {

  43. Hanoi hanoi(3);

  44. hanoi.solve();

  46. return 0;

  47. }

  48. /*

  49. //===============运行结果==================

  50. Move disk No. 1 from A to C

  51. Move disk No. 2 from A to B

  52. Move disk No. 1 from C to B

  53. Move disk No. 3 from A to C

  54. Move disk No. 1 from B to A

  55. Move disk No. 2 from B to C

  56. Move disk No. 1 from A to C

来源：
<[http://blog.csdn.net/geekwangminli/article/details/7981570]{.ul}>

计算机原理

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！