汉诺塔算法思想与把大象装进冰箱的思想相似。假设有三个柱子A,B,C。要把A柱子上的n个盘子移到C柱子上,始终要求大的盘子在下,小的盘子在上。可以先把A柱子上的n-1个盘子当做整体,先移到辅助柱子B上,接着把A上最大的盘子移到C柱子上,最后把B柱子的盘子移到C柱子上,总共三步骤。
步骤如下:
1、将A柱子上的n-1个盘子看作是整体,将它移到B柱子上(相当于打开冰箱的门);
2、将A柱子上最大的也就是最底端的盘子移到C柱子上(相当于把大象装进冰箱);
3、将B柱子上的盘子移到C柱子上(相当于关闭冰箱门)
步骤虽少,但如何打开冰箱门呢?
A移动到B,需要借助第三个柱子C,才能移动到B,B柱子就作为一个辅助柱子;同样B移动到C也要借助A,A此时就为辅助柱子。
通过递归的思想,可以很好地解决打开冰箱的问题,每一次递归都要走这三个步骤,打开、放大象、关冰箱。
代码实现如下:
#include <iostream>int main(void){ void Hanoi(int n,char A,char B,char C); int n; char A='A',B='B',C='C'; std::cout<<"Please input the number of plates :"; std::cin>>n; std::cout<<"the actions of move are :"<<std::endl; Hanoi(n,'A','B','C'); return 0;}void Hanoi(int n,char A,char B,char C){ void move(char x,char y); if(n==1)move(A,C); else{ Hanoi(n-1,A,C,B); move(A,C); Hanoi(n-1,B,A,C); }}void move(char x,char y){ std::cout<<x<<"--->"<<y<<std::endl;}运行结果(运行系统:Windows、编译软件:GCC、代码语言:C++)如下: