先来看看什么是汉诺塔问题：
来源：
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
分析：对于这样一个问题，任何人都不可能直接写出移动盘子的每一步，但我们可以利用下面的方法来解决。设移动盘子数为n，为了将这n个盘子从A杆移动到C杆，可以做以下三步：
(1)以C盘为中介，从A杆将1至n-1号盘移至B杆；
(2)将A杆中剩下的第n号盘移至C杆；
(3)以A杆为中介；从B杆将1至n-1号盘移至C杆。
我们画个图示意一下：
如果只有一个盘子，那么我们直接将盘子移动C柱就行。
也就是A -> C 。
如果有两个盘子，我们该怎么挪呢？
1.先将红盘移动到B柱。
A -> B
2.再将绿盘移到C柱。
A -> C
3.最后将B柱的红盘移到C柱。
B -> C
如果有三个盘子：
一定要保证大的在下，小的在上。
- A -> C
2.A ->B
3.C ->B
4.A->C
5.B -> A
6. B -> C
7. A -> C
如果是四个柱子：
也是这种思路，我们可以把他们放到一起来对比。
1个盘子 A -> B 移动一次
2个盘子 A -> B A->C B->C 移动三次
3个盘子 A-> C A->B C->B A->C B->A B->C A->C 移动七次 公式为:2^n-1
那么如果有64个盘子我们看看需要移动多少次：
这太大了，用我们一般的计算机来跑也需要数百年。
那么我们的代码该怎么去写呢？
public class demo { /** * * @param n:盘子个数 * @param pos1:起始位置 * @param pos2:中转位置 * @param pos3:目的位置 */ public static void Hanoi(int n,char pos1,char pos2,char pos3){ if (n == 1 ){ move(pos1,pos3); return ; } //无论这个有多少个盘子，我都需要借助pos3 移动到pos2 上，只留下最底下，最大的那个盘子 Hanoi(n-1,pos1,pos3,pos2); //将这个最大的盘子移动到pos3 上 move(pos1,pos2); //于是问题转化成了： Hanoi(n-1,pos2,pos1,pos3); //具体是怎么操作的我们不用管 } public static void move(char pos1,char pos2){ System.out.print(pos1 + "->" + pos2 +" "); } public static void main(String[] args) { Hanoi(2,'A','B','C'); System.out.println(); Hanoi(4,'A','B','C'); System.out.println(); } }
如果这里是 64 个盘子，肯定是跑不完的。
