python复盘：023-024递归：这帮小兔崽子与汉诺塔
本帖最后由 慕良 于 2020-2-19 12:07 编辑023-024递归：这帮小兔崽子与汉诺塔
斐波那契（Fibonacci）数列的递归实现（分治思想）
例1：兔子的繁衍
月数 1 2 3 4 5 6 7 8 9 10 11 12
数量 1 1 2 3 5 8 13 21 34 5589 144
求20个月后的兔子数量。
迭代：
def fab(n):
n1 = n2 = n3 = 1
if n < 1:
print('输入有误！')
return -1
while (n-2) > 0:
n3 = n2 + n1
n1 = n2
n2 = n3
n -= 1
return n3
result = fab(20)
if result != -1:
print('总共有%d对小兔崽子诞生！' % result)
递归：
def fab(n):
if n < 1:
print('输入有误！')
return -1
if n == 1 or n == 2:
return 1
else:
return fab(n-1) + fab(n-2)
result = fab(20)
if result != -1:
print('总共有%d对小兔崽子诞生！' % result)
例2：汉诺塔
def hanoi(n,x,y,z):#x,y,z代表3根针
if n == 1:
print(x,'-->',z)
else:
hanoi(n-1,x,z,y) #将前n-1个盘子从x移动到y上
print(x,'-->',z) #将最底下的最后一个盘子从x移动到z上
hanoi(n-1,y,x,z) #y上的n-1个盘子移动到z上
n = int(input('请输入汉诺塔的层数：'))
hanoi(n,'x','y','z') 很强
页:
[1]