解决汉诺塔问题中发现的print函数返回值问题

前言:在练习python循环嵌套的时候,选择了一个经典的汉诺塔问题来研究,在过程中发现了一些有意思的东西。先介绍下什么是汉诺塔问题(百度百科):源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,任何时候,在小圆盘上都不能放大圆盘,且在三根柱子之间一次只能移动一个圆盘。问应该如何操作?

1,问题分解

直接考虑从上部移动是非常复杂的,每移动一块都要考虑下一步要移到哪个柱子上合适,整个过程是的不确定性很强,现在唯一能确定的就是最后一步,即63个盘子已经由a移到b,现在只需要将最后一个盘子由a移到c,最后一个盘子就到了才c柱子上了。

循环往复,即每次都是先将其他圆盘移动到辅助柱子上,并将最底下的圆盘移到c柱子上,然后再把原先的柱子作为辅助柱子,并重复此过程。我们可以这样实现这个过程:

func:

if n!=then;预定值func(n-1, a, c, b);将n-1个盘子由a移动到b,以c为辅助柱子(注意参数顺序)move a[n] to c;将a上的最后一个盘子移动到cfunc(n-1, b, a, c);将n-1个盘子由b移动到c,以a为辅助柱子

endif;完成

2,程序实现

下面用python来实现汉诺塔程序(以移动两块盘子为例),这段程序就是让我纠结很久的那段,大家首先看到的时候有没有什么疑问?

我的疑问点是这里的逻辑运算or,为什么会输出3个结果?(a or b # 如果 a 是非 0,它返回 a 的值,否则它返回 b 的计算值),按照or的逻辑,如果move(n-1,a,c,b)为非0就输出a就结束运算,不会再进行下次循环了,应该只输出move(1,a,c,b)=('a', '-->', 'b')的值才对,如下(n=2时else后面相当于下面程序):

3 疑问探索

为了回答这个疑问,我做了一系列的探索

探索1:用“,”替换or发现同样可以达到目的,or在这里是完全没用的。

探索2:用print输出结果,结果多了一个none,到这里基本发现问题了,应该是print函数嵌套调用返回结果的问题。

探索3:继续研究print(),你会发现嵌套调用print结果是多返回一个none值的,也就是说print(x)会被判断成0,而直接返回X值是被判断成非0.

验证:修改程序如下,直接return数值,而不是调用print嵌套函数,结果就和预期的一样啦。原来都是print搞的鬼。

4 汉诺塔问题程序优化

其实整个程序是不用逻辑判断函数的,有以下比较直观容易理解的写法

如果将这个问题的盘子数量减为10个或更少,就不会有太大的问题了。这里我尝试了下移动10个盘子,我的电脑的运行时间为:0.092055秒 ,但盘子数量为64的话,你一共需要移动约1800亿亿步(18,446,744,073,709,551,615),才能最终完成整个过程。这是一个天文数字,假设计算机每秒能够移动100万步,那么约需要18万亿秒,即58万年。

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

扫码关注云+社区

领取腾讯云代金券