汉诺塔算法

UsherChen 发布于2019-08-21 16:55 / 1089人阅读

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

汉诺塔问题描述：有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和汉诺塔看分治法

GPU云服务器云服务器简单汉诺塔c语言算法汉诺塔汉诺塔 python 汉诺塔c语言讲解

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/88905.html

【程序员必会十大算法】之分治算法（汉诺塔问题）

摘要：应用分治法是一种很重要的算法。字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 ...

codecraft 2021-09-24 09:48 评论0 收藏0
数据结构与算法之汉诺塔问题（Java递归）

摘要：汉诺塔问题有三根柱子，源杆，暂存杆，目的杆上有层盘子，由小到大向下排列，现需要将杆的盘子移到杆中要求大的盘在下面，小的盘在上面一次只能移动一个盘子个人思路先分析问题，用数学的归纳法当只有一个盘时，直接移动当有两个盘时，先将小的移到暂存杆，再汉诺塔问题：有三根柱子，源杆A，暂存杆temp，目的杆C A上有n层盘子，由小到大向下排列，现需要将A杆的盘子移到C杆中 ...

yuxue 2019-08-16 15:51 评论0 收藏0
经典算法：汉诺塔

摘要：学编程，学，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。当我们把层都搬到了中间柱的时候，只需要把最大的那个盘，从搬到柱就好了，剩下的怎么办呢柱永远是目标柱，我们不需要去移动它。学编程，学IT，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。算是算法的入门小题目之一吧~ 视频教程什么是汉诺塔？我这里直接拉来一个图解释一下（挂了请联系我）sho...

Lin_R 2019-07-31 11:17 评论0 收藏0
经典算法：汉诺塔

摘要：学编程，学，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。当我们把层都搬到了中间柱的时候，只需要把最大的那个盘，从搬到柱就好了，剩下的怎么办呢柱永远是目标柱，我们不需要去移动它。学编程，学IT，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。算是算法的入门小题目之一吧~ 视频教程什么是汉诺塔？我这里直接拉来一个图解释一下（挂了请联系我）sho...

AWang 2019-08-23 12:40 评论0 收藏0