经典算法：汉诺塔

Lin_R 发布于2019-07-31 11:17 / 1078人阅读

摘要：学编程，学，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。当我们把层都搬到了中间柱的时候，只需要把最大的那个盘，从搬到柱就好了，剩下的怎么办呢柱永远是目标柱，我们不需要去移动它。

学编程，学IT，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。算是算法的入门小题目之一吧~

视频教程 什么是汉诺塔？

我这里直接拉来一个图解释一下（挂了请联系我）

就是这么一个东西了，把所有的圆盘从左边移动到右边，并且大的圆盘不能够压住小的。怎么才能完成呢？

规则理解了，开始钻牛角尖

先来看看只有一个圆盘的情况，

嗯相当的简单 A--->C 就可以了

两个的情况呢？也不难 A--->B A--->C B--->C

三个的话有点挑战了大家自己推一推

好的十个呢？就算想了半天弄好了，怎么让程序帮我们做呢？头大！

牛角尖钻完了，冷静分析

在我们每次距离对称最近的状态，都是把最大的圆盘放到了最右边，剩下的圆盘放到了中间。

然后把中间的再都放到右边就好了

这道理就跟把大象装冰箱一样啊都是三步呢！

这时候千万不要去想怎么把n-1层都搬到B柱也不要想怎么把N-1层都搬到C柱，如果继续想下去你就会进入死循环，这时候你只需要做一个思维转换。

当我们把n-1层都搬到了中间柱的时候，只需要把最大的那个盘，从A搬到C柱就好了，剩下的怎么办呢？C柱永远是目标柱，我们不需要去移动它。这时候我们大点力！把B柱子掰下来！扔到A前面！无视掉C柱上面的大圆盘，因为我们不会再去动它了！是不是画面似曾相识？对啊！递归啊！继续把最左边的n-1层都弄到中间，最大的扔到C就好了啊！

看到这里如果你还在钻牛角尖的话，可以暂时休息一下了。

思维转换完成的过来写代码！

// JS写一下
function move(num,from,button,to){
    // 如果只有一个圆盘
    if(num==1){
        console.log(from,"---->",to)
        // 最左边的放到最后边完了个事！
        return
    }
    // 如果柱子有点多咋办呢？
    // 先把n-1个左边的放到中间呗
    move(num-1,from,to,button) //放过去了，具体过程是啥？我特么哪里知道 它里面怎么操作?管他呢,反正他自己知道自己干了啥
    console.log(from,"---->",to) // 我就干一件事，我就把左边最大的放到右边，虽然我不知道现在我是不是真正的左边，我可能是被你大力从中间拽过来的左边。
    // 放完了然后呢？
    // 把所有中间的柱子扔到最右边去
    move(num-1,button,from,to)
}

move(3,"A","B","C") //测试一下

//golang
package main

import (
    "fmt"
)

func main() {
    move(3,"A","B","C")
}

func move(num int,from string,button string,to string){
    if num==1 {
        fmt.Printf("%s--->%s
",from,to)
        return
    }
    move(num-1,from,to,button)
    fmt.Printf("%s--->%s
",from,to)
    move(num-1,button,from,to)
}

# python

def move(num ,fro,button,to)
    if (num==1)
        print(fro,"--->",to)
        return
    move(num-1,fro,to,button)
    print(fro,"--->",to)
    move(num-1,button,fro,to)
move(3,"A","B","C")

总结

递归这个东西,千万不可钻牛角尖,把大问题分成小问题,复杂问题简单化,如果非要把递归过程推出来的话,那谁都救不了你

欢迎大家关注我的博客,里面会有我所写博客的视频版本,如果你有更多疑问或者想学前端的话,可以加我微信shouzi_1994或者在博客下方品论留言,三大Q.

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

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

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

经典算法：汉诺塔

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

AWang 2019-08-23 12:40 评论0 收藏0
堆栈的应用——用JavaScript描述数据结构

摘要：一实现一个栈类基于堆栈的特性，可以用数组做线性表进行存储。出栈出栈同样是利用数组的方法，在数组尾部推出数据。聚合最后，将所有功能聚合后，如下所示，一个堆栈的数据结构就搞定了。堆栈的经典算法应用，首推就是汉诺塔。栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。一、实现一个栈类Stack 基于堆...

Hydrogen 2019-08-23 10:54 评论0 收藏0
汉诺塔问题

摘要：概述汉诺塔是一个经典的递归问题，虽说看人家写好的算法程序就那么几行，但着实理解有一定的难度。查阅了一些资料，参阅别人的思路，对汉诺塔算法进行一番梳理。问题来源有一个梵塔，塔内有三个座，座上有若干个盘子，盘子大小不等，大的在下，小的在上如图。概述汉诺塔是一个经典的递归问题，虽说看人家写好的算法程序就那么几行，但着实理解有一定的难度。查阅了一些资料，参阅别人的思路，对汉诺塔算法进行一番...

RayKr 2019-08-14 15:11 评论0 收藏0
经典青蛙跳台阶问题与汉诺塔问题

摘要：问青蛙跳到第个台阶有多少种方法。但是第项却崩溃了。这时候可以采用循环递推当取，时不符合我们的循环判断，取正好作为的值青蛙种类数列与斐波那契数列的差别就是后者首位多一项，所以青蛙项种数为斐波那契数列的项加一只青蛙可以一次跳一个台阶，也可以一次跳两个台阶。问青蛙跳到第n个台阶有多少种方法。 ...

Scott 2021-10-11 10:58 评论0 收藏0
【程序员必会十大算法】之分治算法（汉诺塔问题）

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

codecraft 2021-09-24 09:48 评论0 收藏0