递归—汉诺塔
程序员文章站
2024-03-24 15:52:34
...
汉诺塔是经典递归问题:相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。
1:如果A只有一个(A->C)
2:如果A有两个(A->B),(A->C),(B->C)
3:如果A有三个(A->C),(A->B),(C->B),(A->C),(B->A),(B->C),(A->C).
可以发现每增加一步,其中的步骤会多很多。但是不妨这样想。当有N个要从A->C时,且已知移动方式。使用函数表示move(a->c)。如果要是N+1个该如何想呢。是不是先不看最底下的那个盘子呢,把剩下的N从A移到B上。突然发现最底下还有一个盘子,刚好C为空,把这个最大的放在C上,剩下的就是N个从B移到C的问题了。
再看上面的3:把最上面的盘子从A移到B,在把A 的最大移到C。再把2个盘子从B借助A移到C。
再看上面的2:把最上面的盘子移到B,把最底下移到C,就转化成B移到C一个盘子的问题了。这种递归要从每一步的关系找。把N个问题差成N-1移动和最底下移动的问题。
代码如下:
public class 汉诺塔no1 {
static void move(char a,char b)
{
System.out.println("移动最上层的"+a+"到"+b+"\t");
}
static void hannuota(int n,char a,char b,char c)//主要分析每一大步对于下一步需要走的。
{
if(n==1) {move(a,c);}//从a移到c
else
{
hannuota(n-1,a,c,b);//将n-1个从a借助c移到b
move(a,c); //将第n(最后一个)从a移到c。
hannuota(n-1,b,a,c);//再将n-1个从b借助a移到c
}
}
public static void main(String[] args)
{
hannuota(5,'a','b','c');
}
}
上一篇: 阿里Java开发手册之编程规约
下一篇: 骨牌铺方格