汉诺塔问题

问题描述

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

汉诺塔问题是用递归方法求解的一个典型问题

那么问题来了，我们要怎么移动呢？最少要移动多少次呢

从上面整体综合分析可知把n个盘子从1座（相当第一柱子）移到3座（相当第三柱子）：
（1）把1座上（n-1）个盘子借助3座移到2座。
（2）把1座上第n个盘子移动3座。
（3）把2座上（n-1）个盘子借助1座移动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=64步……由此可以知道，移动n个盘子需要2^n-1步就可以完成全部的搬移操作。

#include <iostream>
using namespace std;
//将编号为numdisk的盘子从init杆移至desti杆 
void moveOne(int numDisk, string init, string desti) 
{
   cout << "Move disk No. " << numDisk << " from " << init << " to " << desti << endl;
}
//将numDisks个盘子从init杆借助temp杆移至desti杆
void move(int numDisks, string init, string temp, string desti)
{
   if(numDisks == 1)
   	moveOne(1, init, desti);
   else
   {
   	move(numDisks-1, init, desti, temp);//首先将上面的（numDisk-1）个盘子从init杆借助desti杆移至temp杆
   	moveOne(numDisks, init, desti);		//然后将编号为numDisks的盘子从init杆移至desti杆
   	move(numDisks-1, temp, init, desti);//最后将上面的（numDisks-1）个盘子从temp杆借助init杆移至desti杆 
   }
} 
int main()
{
   move(3, "A", "B", "C");	 
   return 0;
}

结果如下所示：

所以，得出结论，如果说，一共有n个盘子，那么全部移动完，需要移动2^n-1步，就可以全部移动完了。