递归是一种非常好的解决难题的方法,有些问题用常规方法解会非常复杂,用递归解则非常简单方便。
汉诺塔是非常好的例子,用递归来实现调理清晰,算法非常简单,只需要几行代码即可。
在编程实践中,我们要思考一个实现功能,需要完成两大部分:
1 问题的算术描述,或者说是用编程语言来描述问题
2 问题的算术解决,用编程语言来解决问题。
算术描述
针对汉诺塔问题,算数描述为:
汉诺塔问题为函数hannuota
汉诺塔的三个位置,为函数的三个字符变量a b c,a为源,c为目标,b为中间临时放置用
汉诺塔的圆环数,为函数的第四个变量数字变量n
即函数hannuota(a, b, c, n)
挪动一块汉诺塔,如a挪到c,可以使用print语句来打印nuo a=>c
算术解决
对任何n,解决的方法都是把n-1个圆盘放到中间b,把最下面最大的圆盘放到c,然后再把中间的圆盘上所有的放到c即可
用函数来表示就是
hannuota(a, c, b, n-1)
hannuota(a, b, c, 1)
hannuota(b, a, c, n-1)
这样每一步都可以拆分成三步,n一直在减小,最终n会减小到1
针对n=1的情况,我们知道直接把汉诺塔圆环从a挪到c即可,表现为使用print语句来打印nuo a=>c
这样整个汉诺塔的问题就解决了,是不是感觉很简单?
汉诺塔python代码
这基本上是最简的代码了,当然挪动一步那里可以直接使用print(f"nuo {a}=>{c} "),但是我还是认为调用hannuota函数更加优美:
# 汉诺塔,a b c为位置,可以用字符串,比如“a” “ta”等,n为汉诺塔的圆环数,如3、4等
def hannuota(a, b, c, n):if n == 1 :print(f"nuo {a}=>{c} ")# passelse:hannuota(a, c, b, n-1)hannuota(a, b, c, 1)hannuota(b, a, c, n-1)
看这个代码多么的简洁漂亮!
可以试试n=3 或4的输出,n再大看起来就太费眼睛了。
# 展示三个圆环的汉诺塔实现过程
hannuota("a", "b", "c", 3)
nuo a=>c
nuo a=>b
nuo c=>b
nuo a=>c
nuo b=>a
nuo b=>c
nuo a=>c
加速
既然我们已经有了这个代码,就想试试圆盘数多一点的情况。为了避免print语句耗费运算时间,我们把它去掉,用一句pass代替。整个函数没有输出,但是我们知道它是跑了一遍的
# 汉诺塔实现加速版,a b c为位置,可以用字符串,比如“a” “ta”等,n为汉诺塔的圆环数,如3、4等
def hannuotafast(a, b, c, n):if n == 1 :# print(f"nuo {a}=>{c} ")passelse:hannuotafast(a, c, b, n-1)hannuotafast(a, b, c, 1)hannuotafast(b, a, c, n-1)
对24层的汉诺塔,在星河社区AIStudio 2核环境下,耗时2.4秒
hannuotafast("a", "b", "c", 24)
运行时长:2.446秒结束时间:2024-09-21 18:33:40
对26层的汉诺塔,在星河社区AIStudio 2核环境下,耗时10.2秒。
大家也可以来试试自己的机器有多快,欢迎在评论区回复!