

斐波那契数列

斐波那契数列（The Fibonacci sequence，OEIS A000045）的定义如下：

该数列的前几项如下：

卢卡斯数列¶

卢卡斯数列（The Lucas sequence，OEIS A000032）的定义如下：

该数列的前几项如下：

研究斐波那契数列，很多时候需要借助卢卡斯数列为工具。

斐波那契数列通项公式¶

第个斐波那契数可以在的时间内使用递推公式计算。但我们仍有更快速的方法计算。

解析解¶

解析解即公式解。我们有斐波那契数列的通项公式（Binet's Formula）：

这个公式可以很容易地用归纳法证明，当然也可以通过生成函数的概念推导，或者解一个方程得到。

当然你可能发现，这个公式分子的第二项总是小于，并且它以指数级的速度减小。因此我们可以把这个公式写成

这里的中括号表示取离它最近的整数。

这两个公式在计算的时侯要求极高的精确度，因此在实践中很少用到。但是请不要忽视！结合模意义下二次剩余和逆元的概念，在 OI 中使用这个公式仍是有用的。

卢卡斯数列通项公式¶

我们有卢卡斯数列的通项公式：

与斐波那契数列非常相似。事实上有：

也就是说，和恰好构成二项式展开再合并同类项后的分子系数。也就是说，Pell 方程

的全体解，恰好是

恰好是卢卡斯数列和斐波那契数列。因此有

矩阵形式¶

斐波那契数列的递推可以用矩阵乘法的形式表达：

设，我们得到

于是我们可以用矩阵乘法在的时间内计算斐波那契数列。此外，前一节讲述的公式也可通过矩阵对角化的技巧来得到。

快速倍增法¶

使用上面的方法我们可以得到以下等式：

于是可以通过这样的方法快速计算两个相邻的斐波那契数（常数比矩乘小）。代码如下，返回值是一个二元组。

pair<int, int> fib(int n) {
  if (n == 0) return {0, 1};
  auto p = fib(n >> 1);
  int c = p.first * (2 * p.second - p.first);
  int d = p.first * p.first + p.second * p.second;
  if (n & 1)
    return {d, c + d};
  else
    return {c, d};
}

性质¶

斐波那契数列拥有许多有趣的性质，这里列举出一部分简单的性质：

卡西尼性质（Cassini's identity）：。
附加性质：。
取上一条性质中，我们得到。
由上一条性质可以归纳证明，。
上述性质可逆，即。
GCD 性质：。
以斐波那契数列相邻两项作为输入会使欧几里德算法达到最坏复杂度（具体参见维基 - 拉梅）。

斐波那契数列与卢卡斯数列的关系¶

不难发现，关于卢卡斯数列与斐波那契数列的等式，与三角函数公式具有很高的相似性。比如：

与

很像。以及

与

很像。因此，卢卡斯数列与余弦函数很像，而斐波那契数列与正弦函数很像。比如，根据

可以得到两下标之和的等式：

于是推论就有二倍下标的等式：

这也是一种快速倍增下标的办法。同样地，也可以仿照三角函数的公式，比如奇偶性、和差化积、积化和差、半角、万能代换等等，推理出更多有关卢卡斯数列与斐波那契数列的相应等式。

斐波那契编码¶

我们可以利用斐波那契数列为正整数编码。根据齐肯多夫定理，任何自然数可以被唯一地表示成一些斐波那契数的和：

并且（即不能使用两个相邻的斐波那契数）

于是我们可以用的编码表示一个正整数，其中则表示被使用。编码末位我们强制给它加一个 1（这样会出现两个相邻的 1），表示这一串编码结束。举几个例子：

给编码的过程可以使用贪心算法解决：

从大到小枚举斐波那契数，直到。
把减掉，在编码的的位置上放一个 1（编码从左到右以 0 为起点）。
如果为正，回到步骤 1。
最后在编码末位添加一个 1，表示编码的结束位置。

解码过程同理，先删掉末位的 1，对于编码为 1 的位置（编码从左到右以 0 为起点），累加一个到答案。最后的答案就是原数字。

模意义下周期性¶

考虑模意义下的斐波那契数列，可以容易地使用抽屉原理证明，该数列是有周期性的。考虑模意义下前个斐波那契数对（两个相邻数配对）：

的剩余系大小为，意味着在前个数对中必有两个相同的数对，于是这两个数对可以往后生成相同的斐波那契数列，那么他们就是周期性的。

事实上，我们有一个远比它要强的结论。模意义下斐波那契数列的周期被称为皮萨诺周期（OEIS A001175），该数可以证明总是不超过，且只有在满足的形式时才取到等号。

习题¶

SPOJ - Euclid Algorithm Revisited
SPOJ - Fibonacci Sum
HackerRank - Is Fibo
Project Euler - Even Fibonacci numbers

本页面主要译自博文 Числа Фибоначчи 与其英文翻译版 Fibonacci Numbers。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。

Last update and/or translate time of this article，Check the history
Found smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
Contributor of this article OI-wiki
Translator of this article Visit the original article!
The article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.