在计算机里, 斐波那契数(Fibonacci) 被常常用来当作递归和循环迭代的很好的例子. 斐波那契数定义如下:
F(1) = 0
F(2) = 1
F(N) = F(N – 1) + F(N – 2) for N >= 3
Fibonacci Equation
前几项是: 0, 1, 1, 2, 3, 5, 8, 13, 21…
计算前几项之和, 我们可以写个循环加上每项数字:
1 2 3 4 5 6 7 8 9 10 11 12 | function sumOfFib(n) { let a = 0; let b = 1; let sum = 0; for (let i = 1; i < n; ++ i) { let c = a + b; a = b; b = c; sum += a; } return sum; } |
function sumOfFib(n) {
let a = 0;
let b = 1;
let sum = 0;
for (let i = 1; i < n; ++ i) {
let c = a + b;
a = b;
b = c;
sum += a;
}
return sum;
}我们定义S函数为前几项斐波那契数列之和:
S(1) = F(1) = 0
S(2) = F(1) + F(2) = 1
S(3) = F(1) + F(2) + F(3) = 2
S(4) = F(1) + F(2) + F(3) + F(4) = 4
S(5) = F(1) + F(2) + F(3) + F(4) + F(5) = 7
…
不然发现有以下规律:
比如:
S(4) = F(6) – 1 = 5 – 1 = 4
S(3) = F(5) – 1 = 3 – 1 = 2
使用数学归纳法来证明前几项斐波那契之和的公式
初始条件:
S(1) = 0
S(2) = 1
若 S(N) = F(N+2) – 1 成立:
那么扩展到N+1项:
S(N+1) = S(N) + F(N+1)
= F(N+2) + F(N+1) – 1
= F(N+3) – 1
也成立, 因此得证.
证明前N项斐波那契之和的公式
我们可以换种形式来写斐波那契数列公式 F(N) = F(N + 2) – F(N + 1).
然后我们要求前N项之和, 
= F(2) – F(1) + F(3) – F(2) + F(4) – F(3) + …. F(N + 2) – F(N + 1)
中间项都可以互相抵消掉, 因此最后结果是:
= F(N + 2) – F(1) = F(N + 2) – 1
英文: Algorithm to Sum The Fibonacci Numbers
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK