草庐IT

Python实现 — — 汉诺塔问题

翊先生 2023-04-19 原文

我们今天来看一个很有意思的实例，叫做汉诺塔问题。

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

我们编写的代码依旧遵循汉诺塔的规则-----小圆盘上不能放大圆盘，也就是说大的圆盘不能放在小的圆盘上面。

我们先来看一下代码（这里我们先设只有两个圆盘）：

count=0
def hanoi(n,a,b,c):
    global count
    if n == 1 :
        print("{}:{}->{}".format(1,a,c))
        count+=1
    else:
        hanoi(n-1,a,c,b)
        print("{}:{}->{}".format(n,a,c))
        hanoi(n-1,b,a,c)
        count+=1

hanoi(2,"A","B","C")
print(count)

我们在这里设三根柱子从左往右分别为ABC，我们先试试2个圆盘。

我们先看代码的输出:

输出部分分为两段 ：

（1）该怎么搬运
（2）需要多少步

怎么搬运也分为两部分:

（1）搬运的圆盘是第几层的
（2）从哪根柱子搬运到哪根柱子

一下理解代码有点困难我们先缩减代码，我们先把计算需要多少步的代码删减，你们先自己试试一下可以删减几行代码。

这是删减完的代码：

def hanoi(n,a,b,c):
    if n == 1:
        print("{}:{}->{}".format(1,a,c))
    else:
        hanoi(n-1,a,c,b)
        print("{}:{}->{}".format(n,a,c))
        hanoi(n-1,b,a,c)

hanoi(2,"A","B","C")

OK，我们缩减完代码后下一步就要将这个问题抽象，现在我们知道了题目，但怎么解呢？我们把这个解分为三步：

（1）将上面的n-1个圆盘，从A借助C移动到B
（2）将最下面的一个圆盘，从A移动到C
（3）将上面的n-1个圆盘，从B借助A移动到C

（n-1代表除了最下面一个圆盘的所有圆盘，现在不理解没关系后面有解释，现在只需要记住就行了）

接下来我们只需要理解hanoi函数，hanoi函数是一个递归函数，所以分为基例部分和递归链条部分，其中基例部分很好理解，当n=1时，则打印1:A->C。如果n>1则执行第5第6第7行代码，但我们要知道递归函数中的基例和递归链条是密不可分的，我们设n=2时，则先执行的代码是第5行，但代码不知道n=1时该怎么办，所以又重新执行函数寻找答案，代码发现当n=1时执行基例的部分，所以打印1：A->C？我们知道了代码的输出结果所以知道这是不对的，原因就是我们把函数的原本的顺序（a,b,c）变成了（a,c,b）所以输出的结果是1：A->B。

以此类推我们很快就能理解第6第7行代码了。但这样思考就是对的吗，假如现在把圆盘加到20个，那一共有1048575步，25个圆盘有33554431步，如果我们依然和二个圆盘一样去思考肯定是不行的。

这个时候我们就需要理解计算机思维，其中最重要的就是自动化和抽象，而这里就是抽象，我们要把n-1看做一个整体，看做除了最后一个圆盘的所有圆盘：

我们不断的将n进行n-1的操作，直到n=2时，再算出来的n就等于1了，这个时候n就会进入基例部分不会进入递归链条

所以n-1就是除了最后一个圆盘的所有圆盘，这样理解的话我们瞬间就能理解第5行代码在干什么了，第5行代码表达的意思就是第一步，把n-1个圆盘移到B柱子上，接下去的第6第7行分别对应着第二和第三步。

怎么样有没有醍醐灌顶，如果你之前无法理解什么叫抽象那么想现在应该能初步理解一点了。那么这次精彩的实例分享就到此结束了，在这里我祝大家在2023年里学习一帆风顺，bug越来越少。

汉诺mdashxffxff0cxff0python

有关Python实现 — — 汉诺塔问题的更多相关文章

  1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  2. ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2

    我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

  3. ruby - 通过 rvm 升级 ruby​​gems 的问题 - 2

    尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub

  4. ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2

    我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search

  5. ruby - Fast-stemmer 安装问题 - 2

    由于fast-stemmer的问题，我很难安装我想要的任何ruby​​gem。我把我得到的错误放在下面。Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingfast-stemmer:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcreatingMakefilemake"DESTDIR="cleanmake"DESTDIR=

  6. ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2

    我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden

  7. ruby - 安装 Ruby 时遇到问题(无法下载资源 "readline--patch") - 2

    当我尝试安装Ruby时遇到此错误。我试过查看this和this但无济于事➜~brewinstallrubyWarning:YouareusingOSX10.12.Wedonotprovidesupportforthispre-releaseversion.Youmayencounterbuildfailuresorotherbreakages.Pleasecreatepull-requestsinsteadoffilingissues.==>Installingdependenciesforruby:readline,libyaml,makedepend==>Installingrub

  8. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  9. ruby-on-rails - 简单的 Ruby on Rails 问题——如何将评论附加到用户和文章？ - 2

    我意识到这可能是一个非常基本的问题，但我现在已经花了几天时间回过头来解决这个问题，但出于某种原因，Google就是没有帮助我。(我认为部分问题在于我是一个初学者，我不知道该问什么......)我也看过O'Reilly的RubyCookbook和RailsAPI，但我仍然停留在这个问题上.我找到了一些关于多态关系的信息，但它似乎不是我需要的(尽管如果我错了请告诉我)。我正在尝试调整MichaelHartl'stutorial创建一个包含用户、文章和评论的博客应用程序(不使用脚手架)。我希望评论既属于用户又属于文章。我的主要问题是:我不知道如何将当前文章的ID放入评论Controller。

  10. Python 相当于 Perl/Ruby ||= - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Pythonconditionalassignmentoperator对于这样一个简单的问题表示歉意，但是谷歌搜索||=并不是很有帮助；)Python中是否有与Ruby和Perl中的||=语句等效的语句？例如:foo="hey"foo||="what"#assignfooifit'sundefined#fooisstill"hey"bar||="yeah"#baris"yeah"另外，类似这样的东西的通用术语是什么？条件分配是我的第一个猜测，但Wikipediapage跟我想的不太一样。

随机推荐