计算前几项斐波那契数之和的算法

在计算机里, 斐波那契数(Fibonacci) 被常常用来当作递归和循环迭代的很好的例子. 斐波那契数定义如下:

F(1) = 0
F(2) = 1
F(N) = F(N – 1) + F(N – 2) for N >= 3

$latex-fibonacci 计算前几项斐波那契数之和的算法数学数据结构与算法$

Fibonacci Equation

前几项是: 0, 1, 1, 2, 3, 5, 8, 13, 21…

计算前几项之和, 我们可以写个循环加上每项数字:

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
…

不然发现有以下规律:
$tex_882caded33c9e36a815c7993cab7dd7e 计算前几项斐波那契数之和的算法数学数据结构与算法$

比如:
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项之和, $tex_5b0d46d6ed6c9aa9118a4410e5e8db3a 计算前几项斐波那契数之和的算法数学数据结构与算法$
= 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

GD Star Rating
loading...

本文一共 209 个汉字, 你数一下对不对.

计算前几项斐波那契数之和的算法. (AMP 移动加速版本)
上一篇: 通过 jQuery Migrate Helper 来解决升级 WordPress 5.5 带来的问题
下一篇: 小米路由器使用体验

赞赏我的几个理由.

¥ 打赏支持

扫描二维码，分享本文到微信朋友圈

小赖子的英国生活和资讯

计算前几项斐波那契数之和的算法

使用数学归纳法来证明前几项斐波那契之和的公式

证明前N项斐波那契之和的公式

评论

使用数学归纳法来证明前几项斐波那契之和的公式

证明前N项斐波那契之和的公式

相关文章：

评论