斐波那契数列

斐波那契数列(The Fibonacci sequence,OEIS A000045)的定义如下:

该数列的前几项如下:

性质

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

  1. 卡西尼性质(Cassini’s identity):
  2. 附加性质:
  3. 取上一条性质中 ,我们得到
  4. 由上一条性质可以归纳证明,
  5. 上述性质可逆,即
  6. GCD 性质:
  7. 以斐波那契数列相邻两项作为输入会使欧几里德算法达到最坏复杂度(参见 Lame’s theorem in Euclidean algorithm)。

斐波那契编码

我们可以利用斐波那契数列为正整数编码。根据 Zeckendorf’s theorem ,任何自然数 可以被唯一地表示成一些斐波那契数的和:

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

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

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

  1. 从大到小枚举斐波那契数 ,直到
  2. 减掉 ,在编码的 的位置上放一个1。
  3. 如果 为正,回到步骤1。
  4. 最后在编码末位添加一个1,表示编码的结束位置。

解码过程同理,先删掉末位的1,对于编码为1的位置 ,累加一个 到答案。最后的答案就是原数字。

斐波那契数列通项公式

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

解析解

解析解即公式解。我们有斐波那契数列的通项公式:

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

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

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

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

矩阵形式

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

,我们得到

于是我们可以用矩阵乘法在 的时间内计算斐波那契数列。

快速倍增法

使用上面的方法我们可以得到以下等式:Using above method we can find these equations:

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

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};
}

模意义下周期性

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

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

习题

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


  转载请注明: Sshwy's Blog 斐波那契数列

 上一篇
菜鸡互啄 ACM 心路历程 菜鸡互啄 ACM 心路历程
摘要 极限反杀!成功追梦! 谨以此文,纪念我 OI 生涯中第一次 ACM 赛 RK1。 今天上午,打了一场 ZR 的 ACM。题是敦爷组的,现在总结一下我的心路历程。 队名:阿咆长得像地精炸弹 队长:Sshwy 队员:Sshwy Na
2019.07.27 Sshwy
下一篇 
Tewelvefold way Tewelvefold way
摘要 今天我们来探讨一道综合计数题。 问题描述 n个有标号/无标号的球分给m个有标号/无标号的盒子,盒子有三种限制: A. 无限制B. 每个盒子至少有一个球C. 每个盒子至多一个球 共12种问题。问方案数。(所有球都要放) 为了方便,将
2019.07.20 Sshwy
  目录