经典算法:汉诺塔

蒋吉兆 · · 1109 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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

视频教程

什么是汉诺塔?

我这里直接拉来一个图解释一下(挂了请联系我)
Image text
就是这么一个东西了,把所有的圆盘从左边移动到右边,并且大的圆盘不能够压住小的。怎么才能完成呢?

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

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

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

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

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

好的 十个呢?就算想了半天弄好了,怎么让程序帮我们做呢?头大!

牛角尖钻完了,冷静分析

在我们每次完成之前的状态,都是把最大的圆盘放到了最右边,剩下的圆盘放到了中间。
Image text
然后把中间的再都放到右边就好了

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

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

Image text

当我们把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\n",from,to)
        return
    }
    move(num-1,from,to,button)
    fmt.Printf("%s--->%s\n",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.


有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:蒋吉兆

查看原文:经典算法:汉诺塔

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

1109 次点击  ∙  1 赞  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传