程序员的数学I

2016-02-13 本文已影响71人锅巴GG

递归——自己定义自己2

思考：和的定义

假设n为0以上的整数，使用递归的方式从0到n的整数之和。

n=0时, S(n)=0

n>1时，n=S(n-1) (n=1,2,3...)
解析式 S(n)= n x (n+1) / 2 (高斯的断言)

斐波那契数列

思考：有一种动物，TA出生2天后，就开始以每天1只的速度繁殖后代。假设第1天，有一只这样的动物（该动物刚出生，从第3天起繁殖后代）。问，到第11天，共有多少只？

思路，按顺序思考，找出规律。

第1天，只有1只动物

第2天，只有1只动物，还没有繁衍后代

第3天，第1天的1只动物，繁殖1个后代，合计2只

第4天，第1天的1只动物，又繁殖1个后代
第3天出生的还没有开始繁殖，总共3只

第1天和第3天出生的2只动物各繁殖1个后代。
第4天出生的1只动物还没繁殖后代，合计5只。
进行归纳的时候，不用想着第n天几只，可以如下思考：

第n-1天出生的动物，在第n天还活着

第n-2天以前出生的动物，在第n天后会繁殖1个后代

总结出递推公式：
若设第n天的动物总数为F(n)，则
F(n)=F(n-1)+F(n-2)
第n天的动物数 = 第n-1天前的动物数 + 第n-2天前出生的动物数
在这里，为了让等式成立（即让n=2时，公式成立），定义F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)
由此，我们可以推断出:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
...
F(11) = F(10) + F(9) = 55 + 34 = 89