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

景命

知识点：

• 斐波那契（Fibonacci）数列：
  斐波那契数列的基本思想就是，每一项都等于前两项的和。
          迭代实现：

  a = int(input("请输入斐波那契数列的项数："))
  x = y = 1               #斐波那契数列的第一项和第二项的值可以确定为一。
  for i in range(a-2):    #因为前两项的值已将确认，所以一共运算a - 2项。
      s = x + y           #将前两项的值相加赋给s
      x = y
      y = s
  print(s)

          递归实现：

  def a(n):
      if n < 3:           #n为1或者n为2的时候都是一对兔子，所以返回1。
          return 1
      else:
          return a(n-1) + a(n-2)  #这里用的分治思想来写。
  
  i = int(input("请输入一个正整数："))
  s = a(i)
  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上。
  
  递归实现：

  def hanoi(n,a,b,c):
  if n == 1:
  print(a,"->",c)
  else:
  hanoi(n-1,a,c,b)
  print(a,"->",c)
  hanoi(n-1,b,a,c)

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