Python:汉诺塔与递归

简 介

这里 从汉诺塔游戏Hanoi Tower中了解背后递归的数学思想,并使用python来实现

01 汉诺塔效果演示

这个程序图形编程并不是小朋友做的。程序分为两部分,用算法求出移动的步骤,并调用python的tkinter库把移动步骤用图形的方式显示出来。需要源代码的同学,请私信邮箱。另外,这个程序所用的递归算法略显啰嗦,递归算法部分可以采用本文后面介绍的算法。

02 基础知识

在程序中递归的基础是函数。了解函数之后则需要了解递归的概念,以及如何寻找递归规律的方法。

1F

函数

在python中,函数的定义遵循的语法是def 函数名(参数):。函数可以有返回值也可以不带返回值。如果有返回值则使用return关键字返回。我下面用左手举个栗子:

def函数名(参数):

....

....

...

return返回值

之所以存在函数,是因为函数把经常执行的功能给封装起来,方便后续调用,减少工作量。

2F

递归和寻找递归规律的方法

寻找规律的方法就是从简单的情况入手,逐渐变复杂,进而探求其中的规律。寻找递归规律的方法也是如此,由简单入手,通过画图辅助,来寻找其中的规律。

学习知识得挑好欺负的下手(删除)从简单的开始学习。比如,给出一个数字,打印出这个数字到一的所有数字。一般而言,使用while语句(for也可以)。下面这个我用右手举得栗子,是增加了函数的使用,以及奇偶数判断的最终结果。

defMaxprint(num):

ifnum%2==:

print(str(num)+" is an even number")

else:

print(str(num)+" is an odd number")

i=8

whilei>:

Maxprint(i)

i=i-1

如果不使用while等循环语句呢,如果实现同样的的功能。从下面的图左侧部分可以看出,每一个数,都是先打印自己,然后再打印上一个数到1的所有数字。

我们先假设已经存在一个打印函数mp(num),可以打印num到1的所有数字。这一点很重要,不假设这个函数已经存在,我们根本无法进行后续的讨论。这种假设结果已经存在的思想非常有用,比如在是否实现某个目标的问题上,我们可以假设这个目标已经实现,在这种情况下,你个人会有什么不同,会有什么得失。考虑完这些,你个人基本能够想明白是否要花费时间和精力来实现这个目标。

还好没跑远。。。。

在有了mp(num)函数已经实现的前提下,我们可以发现两点:第一点是每一个数都是由打印自己print(num)和打印比自己小1的数的序列mp(num-1)组成。第二点是存在一个特殊的数字,即1,它只需要打印自己。

程序实现如下。很简单有木有!!!如果想要输出8到1,只需要使用mp(8)即可。

defmp(num):

ifnum==1:

print(num)

else:

print(num)

mp(num-1)

03 汉诺塔的实现

1F

汉诺塔的规律

要寻找规律,则必须要抽象成为数学模型。寻找一种合适的语言或者规则定义来描述这个模型就很重要。一个5层高的塔包括5层,分别是1,2,3,4,5,而这个5层高的塔就是G5。在这个定义下,G3表示1,2,3这三层组成的一组。从G1开始,只需要把1这层从p1移到p3。在这里移动过程,我们使用print来代替。从G2开始,则都需要借助p2,总共移动三大步。先把最底下那层以外的所有层都先移动到p2,再把最底层移动到p3(使用print),然后把在p2上的所有层移动到p3。

因此,我们假设已经存在一个移动函数move(源柱子,目标柱子,G组,中间辅助柱子)。因此,除了G1特殊外,其他的G组都是包括三大步:

move(源柱子,中间辅助柱子,G-1组,目标柱子)

把G组中的最大那个(刚好数值也等于G,例如8层塔的最大那个是第8层)从源柱子移动到目标柱子(print)

move(中间辅助柱子,目标柱子,G-1组,源柱子)

2F

程序实现

defmove(pS,pD,Gnumber,pM):

ifGnumber==1:

print(pS+"-->"+pD+" : "+str(Gnumber))

else:

move(pS,pM,Gnumber-1,pD)

print(pS+"-->"+pD+" : "+str(Gnumber))

move(pM,pD,Gnumber-1,pS)

是不是同样的很简单!!!

如果是5层的话,运行结果如下。如果想要记录所有移动过程的话,可以使用列表来记录每一次移动(列表的append方法),每一次的移动都可以记录成为一个三个元素的列表,例如 p1-->p3:2可以记录为[1,3,2],即【源柱子,目标柱子,第几层】。从而整个记录列表是一个二次列表。

p1-->p2 :1

p1-->p3 :2

p2-->p3 :1

p1-->p2 :3

p3-->p1 :1

p3-->p2 :2

p1-->p2 :1

p1-->p3 :4

p2-->p3 :1

p2-->p1 :2

p3-->p1 :1

p2-->p3 :3

p1-->p2 :1

p1-->p3 :2

p2-->p3 :1

04 关于图形的实现

图形的实现简单的说几句,包括以下三点。。。

图形使用tkinter库来实现,汉诺塔的层都是使用button控件动态创建,控件的长度都是对应的层数值。为了方便寻找和控制层,我们使用了列表来作为层数的名称。例如一个5层的塔,我们使用了一个5元列表b。其中第三层的名字就是b[2] (因为列表下标都是从0开始)。关于移动方法,比如[1,3,2] (p1-->p3:2),在这里第二层的名字是b[1],我们就把b[1]这个button控件的位置参数改变,使得其从1号柱子移动到3号柱子。

多多机器人工作室

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180609G0UU1O00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

同媒体快讯

扫码关注腾讯云开发者

领取腾讯云代金券