基于非递归算法的汉诺塔游戏之Python实现

本文代码涉及到汉诺塔问题的非递归算法,可能不是很好理解,我在代码中加了大量注释,希望能够有所帮助,如果实在难以理解的话,请搜索这个算法并结合下面的代码进行阅读和理解。感谢国防科技大学刘万伟老师提供算法思路和第一版本的代码。

def hannoi(n):

#用来记录移动过程中每个盘子的当前位置

#初始都在A柱子上,即chr(65+0)

L = [0] * n

#n个盘子一共需要移动2^n-1次才能完成

for i in range(1, 2**n):

#假设盘子编号分别为0,1,2,...,n-1

#第i步应该移动的盘子编号

#正好是i的二进制形式中最后连续的0的个数

b_i = bin(i)

j = len(b_i) - b_i.rfind('1') - 1

print('第'+str(i)+'步:移动盘子'+str(j+1),

chr(65+L[j]),'->', end=' ')

#把ABC三根柱子摆成三角形

#把第j个盘子移动到下一根柱子上

#根据j的奇偶性决定是顺时针移动还是逆时针移动

L[j] = ((L[j]+1)%3 if j%2 == 0 else (L[j]+2)%3)

#下一根柱子,这里65是A的ASCII码

print(chr(65+L[j]))

hannoi(3)

运行结果为:

第1步:移动盘子1 A -> B

第2步:移动盘子2 A -> C

第3步:移动盘子1 B -> C

第4步:移动盘子3 A -> B

第5步:移动盘子1 C -> A

第6步:移动盘子2 C -> B

第7步:移动盘子1 A -> B

原文发布于微信公众号 - Python小屋(Python_xiaowu)

原文发表时间:2016-12-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏iOS技术杂谈

KVC 使用方法详解及底层实现你要知道的KVC、KVO、Delegate、Notification都在这里

你要知道的KVC、KVO、Delegate、Notification都在这里 转载请注明出处 https://cloud.tencent.com/develop...

46470
来自专栏菩提树下的杨过

objective-C 的内存管理之-引用计数

obj-c本质就是"改进过的c语言",大家都知道c语言是没有垃圾回收(GC)机制的(注:虽然obj-c2.0后来增加了GC功能,但是在iphone上不能用,因此...

207100
来自专栏freesan44

WebViewJavascriptBridge优化开发背景处理办法

WebViewJavascriptBridge作为JS和原生OC的交互,通常都是在WebView中用self.bridge注册方法来进行调用,但这样对于WebV...

11110
来自专栏青玉伏案

Objective-C中的深拷贝和浅拷贝

        在Objective-C中对象之间的拷贝分为浅拷贝和深拷贝。说白了,对非容器类的浅拷贝就是拷贝对象的地址,对象里面存的内容仍然是一份,没有新的内...

21690
来自专栏『不羁阁』 | 行走少年郎专栏

OC知识--Foundation框架详尽总结之『字典类』

16450
来自专栏iOS 开发杂谈

浅谈 KVO 的实现原理

KVO 全称 KeyValueObserving 是 Objective-C 对观察者模式(Observer Pattern)的实现;KVO 提供一种机制,当指...

42630
来自专栏進无尽的文章

编码篇 - NSInvocation的简单使用

在认识 NSInvocation 之前,iOS开发中我们一般会使用以下两种方式去调用一个方法

16420
来自专栏C语言及其他语言

【每日一题】问题 1109: Hanoi双塔问题

关注我们 题目描述 给定A,B,C三根足够长的细柱,在A柱上放有2n个中间有空的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分...

355100
来自专栏ShaoYL

IOS开发系列—Objective-C之Foundation框架

21460
来自专栏Scott_Mr 个人专栏

利用Runtime实现简单的字典转模型

11930

扫码关注云+社区

领取腾讯云代金券