22 递归：这帮小兔崽子、汉诺塔 - 景命

景命

知识点：

• 斐波那契（Fibonacci）数列：
  斐波那契数列的基本思想就是，每一项都等于前两项的和。
          迭代实现：
  
  1. a = int(input("请输入斐波那契数列的项数："))
     
  2. x = y = 1               #斐波那契数列的第一项和第二项的值可以确定为一。
     
  3. for i in range(a-2):    #因为前两项的值已将确认，所以一共运算a - 2项。
     
  4.     s = x + y           #将前两项的值相加赋给s
     
  5.     x = y
     
  6.     y = s
     
  7. print(s)

  复制代码
  
          递归实现：
  
  1. def a(n):
     
  2.     if n < 3:           #n为1或者n为2的时候都是一对兔子，所以返回1。
     
  3.         return 1
     
  4.     else:
     
  5.         return a(n-1) + a(n-2)  #这里用的分治思想来写。
     
  6. 
     
  7. i = int(input("请输入一个正整数："))
     
  8. s = a(i)
     
  9. print("%d个月后，总共有%d对兔子" % (i,s))
     

  复制代码
  
  （斐波那契的这些代码小甲鱼在视频中都有讲过，尤其是递归的代码，不懂得要仔细的看视频哦。）
  
  
  
  
  
  
• 汉诺塔：
  
  汉诺塔问题可细分为
  问题一（“将x上的n-1盘子借助z移动到y上”）拆解为：
          将前n-2个盘子从x移动到z上。
          将最底下的第63个盘子移动到y上e。
          将z上的62个盘子移动到y上。
  问题二（”将y上的n-1个盘子借助x移动到z上“）拆解为：
          将前n-2个盘子从y移动到x上。
          将最底下的第63个盘子移动到z上。
          将x上的62个盘子移动到y上。
  
  递归实现：
  
  1. def hanoi(n,a,b,c):
     
  2. if n == 1:
     
  3. print(a,"->",c)
     
  4. else:
     
  5. hanoi(n-1,a,c,b)
     
  6. print(a,"->",c)
     
  7. hanoi(n-1,b,a,c)
     

  复制代码
  
  （汉诺塔问题小甲鱼在视频中有详细的讲解。）