欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

递归—汉诺塔

程序员文章站 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');
    }

}

递归—汉诺塔