MITx - 6.00.1x学习笔记——递归

最近在学习MITx - 6.00.1x,对课程中讲解的递归做了一个简单的笔记。以下是应用递归思想解决汉诺塔和斐波那契数列问题的总结。

汉诺塔

有三根杆子A、B、C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将将所有圆盘移至C杆:

  1. 每次只能移动一个圆盘;
  2. 大盘不能叠在小盘上面。

思路

解法的基本思想是递归。先把A塔顶部的N-1块盘移动到B塔,再把A塔剩下的大盘移到C,最后把B塔的N-1块盘移到C。
每次移动多于一块盘时,则再次使用上述算法来移动。

Python实现

def printMove(A,C):
    print('move from '+str(A)+'to '+str(C));    
def Towers(n,A,B,C):
    if n==1:
        printMove(A,C);
    else:
        Towers(n-1,A,C,B);
        Towers(1,A,B,C);
        Towers(n-1,B,A,C);

斐波那契数列

在数学上,斐波那契数列是以递归的方法来定义:
Fn=Fn-1+Fn-2,其中初值F1=1,F2=1,或者F0=1,F1=1。

模型

以兔子的繁殖为模型来描述此数列:

  • 第一个月初有一对新生的兔子;
  • 过一个月后,兔子会发育成熟,在第二个月末,会诞生一对新兔子;
  • 每月月末每对发育成熟的兔子会诞生下一堆新兔子;
  • 兔子永远不会死去。

问题:每个月末会有多少只雌兔。

分析过程

  1. 第一个月初,有一只雌兔;
  2. 第一个月末,仍然只有一只雌兔(正在怀孕);
  3. 第二个月末,有两只雌兔,一只是新生的,一只可生育;
  4. 第三个月末,可生育的兔子会生下一对新的兔子,总共有三只雌兔;
  5. 第n个月末,雌兔(n)=雌兔(n-1)+雌兔(n-2)。因为在第(n-2)月的每对兔子将会在第n月生下一对新兔子,再加上第(n-1)月原有的雌兔数量,即为第n个月末雌兔的数量。
Month Females
F0 1
F1 1
F2 2
F3 3
F4 5
F5 8

Python实现

def fib(n):
    """assumes n an int >= 0
       returns Fibonacci of n"""
    assert type(n)==int and n>0
    if n==0 or n==1:
        return 1
    else:
        return fib(n-1)+fib(n-2)

参考

  1. https://courses.edx.org/courses/course-v1:MITx+6.00.1x_8+1T2016/info
  2. https://zh.wikipedia.org/zh-cn/%E6%B1%89%E8%AF%BA%E5%A1%94
  3. https://en.wikipedia.org/wiki/Fibonacci_number

你可能感兴趣的