汉诺塔算法

汉诺塔问题描述:有A, B, C三个圆柱,其中A上从上至下放置了从小到大n个圆盘,一次只能移动一个圆盘,且大的圆盘不能放在小圆盘之上,要求打印出从A将圆盘移到C的方案。

当n = 1时, A->C
当n = 2时, A->B, A->C, B->C
当n = 3时, [A->C, A->B, C->B,] A->C,[B->A, B->C, A->C]
当n = 4时, A->B, A->C, B->C, A->B, C->A, C->B, A->B,

        A->C, 
        B->C, B->A, C->A, B->C, A->B, A->C, B->C

当n = 5时, A->C, A->B, C->B, A->C, B->A, B->C, A->C,

        A->B, 
        C->B, C->A, B->A, C->B, A->C, A->B, C->B
        
        A->C,
        
        B->A, B->C, A->C, B->A, C->B, C->A, B->A,
        B->C, 
        A->C, A->B, C->B, A->C, B->A, B->C, A->C

当n > 2时,第n项,[A->B],A->C,[B->C]

       第n-1项,A->B  [A->C],A->B,[C->B]    B->C [B->A],B->C,[A->C]
       第n-1-1项,
        第n-1项,A->C(此处的C应该是B),A->C,和第n-1-1项,A->B(此处的B应是C),B->C
        ……
        如此重复,可以用递归求得结果
        

由此,不难看出,计算n个圆盘,所需要的次数为f(n) = 2*f(n-1)+1

代码:

const move=(a,c)=>{
    console.info(`${a}->${c}`)
}

const hanoi = (n,a,b,c)=>{
    if(n === 1){
        move(a,c)
    }else{
        //[A->B]
        hanoi(n-1,a,c,b);
        move(a,c);
        //[B->C]
        hanoi(n-1,b,a,c);
    }
}

参考:从fibonacci和汉诺塔看分治法

你可能感兴趣的