汉诺塔python3函数编写和过程分析

!/usr/bin/env python3

-- coding: utf-8 --

利用递归函数计算阶乘

N! = 1 * 2 * 3 * ... * N

def fact(n):

if n == 1:

return 1

return n * fact(n-1)

print('fact(1) =', fact(1))

print('fact(5) =', fact(5))

print('fact(10) =', fact(10))

利用递归函数移动汉若塔:

def move(n, a, b, c):

if n == 1:

print('move', a, '-->', c) # 只有一个时,从 A 搬到 C

else:

move(n-1, a, c, b) # 否则,先将前 n-1 个搬到 B

move(1, a, b, c) # 将剩下的一个从 A 搬到 C

move(n-1, b, a, c) # 将 B 上的 n-1 个搬到 C

汉诺塔递归,每次递归的思想都是将n-1个放置到另一个空位上去

进行到n-1个开始后,a/b/c顺序会改变,但此时,仍要按照公式里的来排序,简单点来说就是将abc顺序调换

move(3, 'A', 'B', 'C')

print('============')

move(4, 'A', 'B', 'C')

执行move(3, 'A', 'B', 'C')时,第一步是判断,n是否等于1

不等于1,执行else

得到结果

move(2, a, c, b)

move(1, a, b, c)

move(2, b, a, c)

=============

此时递归已经形成:

先执行第一个move(2, a, c, b)

这里就是我最开始的误区:

[下面的是错误的展示]

move(2-1, a, c, b)

move(1, a, b, c)

move(2-1, b, a, c)

这里犯了一个很低级的错误

在定义的函数里,a/b/c三个分别代表的是第一个柱子,第二个柱子,第三个柱子

也就是说,这里的abc是代表的位置,但我执行到n-1步时,还认为应该直接套用公式,这里就出现问题了

所以,正确的应该是:

move(1, a, b, c) 对应的结果是a --> c

move(1, a, c, b) 对应的结果是a --> b

move(1, c, a, b) 对应的结果是c --> b

这里写的时候,感觉有点乱,我的方法是:

写下a c b此时应执行的顺序,然后按照1 2 3位置来排序

1 3 2,即2 3位置调换

1 2 3,位置不变

2 1 3, 即1 2位置调换

=============

同理,执行move(2, b, a, c)

move(1, b, c, a) 对应的结果是b --> a

move(1, b, a, c) 对应的结果是b --> c

move(1, a, b, c) 对应的结果是a --> c

=============

最后将上述结果组合下

move(1, a, b, c) 对应的结果是a --> c

move(1, a, c, b) 对应的结果是a --> b

move(1, c, a, b) 对应的结果是c --> b

move(1, a, b, c) 对应的结果是a --> c

move(1, b, c, a) 对应的结果是b --> a

move(1, b, a, c) 对应的结果是b --> c

move(1, a, b, c) 对应的结果是a --> c

=============

由此就形成了递归的效果

函数的思路很简单:

就是将n-1个看成整理

先将n-1个移动到中间的位置上去

然后移动最下面的(第n个)到最右边的位置上去

然后把n-1个(被看做整体的)移动到最右边的位置上去

上一篇:使用Ceph集群作为Kubernetes的动态分配持久化存储(转)


下一篇:nodejs开发辅助工具nodemon