栈的应用-汉诺塔

时间:2020-11-26 11:04:23

汉诺(Hanoi)塔问题:古代有一个梵塔,塔内有三个座a、b、c,a座上有n个盘子,盘子大小不等,大的在下,小的在上。有一个和尚想把这64个盘子从a座移到b座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。在移动过程中可以利用b座,要求打印移动的步骤。如果只有一个盘子,则不需要利用b座,直接将盘子从a移动到c。

问题分析

  这是一个典型的递归问题:
  假设要将最后一个盘子n移到c座,则要将前n-1个盘子移到b座,假设这个过程是已知的,是一个整体,此时a座是空的,b座有n-1个盘子,c座有一个盘子即第n个,但它的半径比所有的盘子都大,故可以看成空的:

  1、先假设已经利用函数hanoi(n-1,a,c,b)将前n-1个盘子从a座移到了b座,n-1是盘子的个数,c是在在移动过程中的辅助柱子,f(n-1,a,c,b)是定义的一个未知函数,作用就是将n-1个盘子从a座移到了b座,c作为辅助柱子;
  2、此时move(n,a,c)将第n个盘子从a座移动到c座,move(n,a,c)是一个已定义的函数,此时a是空柱子;

  那么要将b座上的第n-1个盘子移动到c座上,则会重复第一个操作,将前n-2个盘子移动到a座,则此时a座是n-2个盘子,b座是空的,c座有2个盘子即第n个和第n-1个,也可以看成是空的;故不断的重复以上操作就可以移动完成了:

  3、再利用函数hanoi(n-1,b,a,c)将n-1个盘子从b座移到了c座,a是辅助柱子,这样就完成了n个盘子的移动,这一步是不断的调用前两步,将n-1个盘子移动到辅助柱子上,将第n个盘子移动到目标柱子上。

伪代码如下:

    function hanoi(n,a,b,c){
        if(n==0) return;
        hanoi(n-1,a,c,b);//将a上的n-1个盘子移到b上,c辅助
        move(n,a,c);//将a上的第n个盘子移到c上
        hannoi(n-1,b,a,c);//将b上的n-1个盘子移到c上,a辅助
    }

那么,hanoi(n-1,a,b,c)要怎么定义才能使a上的n-1个盘子全部移动到b上,这就需要递归了:从n开始,程序执行时会进入第一行 hanoi(n-1,a,b,c),然后不断的递归调用,无法执行第二行程序,直到n=0,然后return,才能退到第二层,这里就像堆栈一样,栈顶永远是正在执行的函数,函数执行完成退栈之后才能执行外层的函数。

代码分析

以n=3为例,打印出每次递归过程中a,b,c的值,以及移动过程:

    function move(n,a,c) {
        console.log(n+'从'+a+'到'+c);
    }
    function hanoi(n,a,b,c){
        if(n==0)return;
        console.log(a,b,c);
        hanoi(n-1,a,c,b);
        move(n,a,c);
        hanoi(n-1,b,a,c);
    }
    var a='A',b='B',c='C';
    var n=3;    
    hanoi(n,a,b,c);

结果如下:
栈的应用-汉诺塔

1、调用hanoi(3,a,b,c)时,注意形参的值,形参a、b、c的值为A、B、C;一次递归调用hanoi(2,a,c,b)后,a、b、c的值为A、C、B;调用hanoi(1,a,c,b)后,a、b、c的值为A、B、C;递归调用两次后形参的值变成原始的;

2、当n=1, hanoi(0,a,c,b)会直接return,然后执行move(1,a,c),此时a、c的值为A、C,move(1,a,c)中将盘子1从A移到C,然后执行hanoi(0,b,a,c)返回return,这一层就结束了进入hanoi(2,a,c,b)这一层;

3、当n=2,hanoi(1,a,c,b)已经执行完毕,a、b、c的值为A、C、B,然后move(2,a,c)将盘子2从A移到B;然后执行hanoi(1,b,a,c)后,此时a、b、c的值为C、A、B,执行move(1,a,c)是将盘子1从C移到B;

4、当n=3,hanoi(2,a,c,b)已经执行完毕,a、b、c的值为A、B、C,然后move(3,a,c)将盘子3从A移到C;然后执行hanoi(2,b,a,c)后,此时a、b、c的值为C、A、B,然后递归调用hanoi(1,a,c,b)以及hanoi(1,b,a,c)重复上面的过程;

JavaScript栈的应用

  JavaScript的栈的定义之前已经讲过了,这里就不叙述了

    function move(n,a,c) {
        c.push(a.pop());
    }
    function hanoi(n,a,b,c){
        if(n==0)return;
        hanoi(n-1,a,c,b);
        move(n,a,c);
        hanoi(n-1,b,a,c);
    }
    a=new Stack();
    b=new Stack();
    c=new Stack();
    var n=5;
    for(let i=0;i<n;i++){
        a.push(i);
    }
    a.print();
    hanoi(n,a,b,c);
    c.print();