当前位置: 代码迷 >> 综合 >> 斐波那契数列的第N项 51Nod - 1242
  详细解决方案

斐波那契数列的第N项 51Nod - 1242

热度:18   发布时间:2023-12-12 14:25:52.0

斐波那契数列的第N项

斐波那契数列的定义如下:

F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) (n >= 2)

(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …)
给出n,求F(n),由于结果很大,输出F(n) % 1000000009的结果即可。

Input
输入1个数n(1 <= n <= 10^18)。

Output
输出F(n) % 1000000009的结果。

Sample Input
11

Sample Output
89

这道 题 我写的 代码 我自己 觉得 是我自己 写的 很 厉害 的 代码 之一 (至今为止),哇 感觉自己 厉害啦 ,哈哈 !!好啦 不说 废话 啦 下面 给大家 好好的 解析解析 这道 题!

这是一个 很经典的 数列问题,经常会遇到 这样的 题 ,但是 我们当时 写这道题的时候 可没有 考虑到 n 会 那么 的 大 ,哈哈。
这道题 有三种 解法:

  1. 第一种就是 最容易想到的 递归啦,老师 在讲递归 的时侯 应该也 把斐波那契数列 当成典型的例子 f(n) = f(n-1) + f(n-2) 虽然 递归用着简单 但是 他是 很耗 内存的 弄不好 内存就 炸啦,而且 对于 这道题 用递归的的话 ,会 重复进行 许多 多余的 操作 时间 也会 比较长 。不太理解的话 看下面的 图 综合一下 。

  2. 第二种方法 是 在第一种方法的基础上 进行啦 些许 简单的优化。
    第二种方法 使用的 循环 ,因为 用了循环之后 上面所说的 重复 操作 和 占用巨大的 内存资源 的问题 就会 的到解决,但是 呢 这道题的 n 的 范围 真是 太大啦 1e18 , 所以 这种循环的方法在 n 的范围 比较小情况下 优先考虑啦!既简单 又 不慢!

  3. 第三种 方法 是 解决这道题的 适用方法,他是 根据 线性代数 中的 矩阵的 运算 下面 大家 根据下面的 图 进行 理解把 很简单的。
    这里写图片描述

    大家 看了上面的图片 是不是已经 知道了 第三种方法的 思路啦! 下面我 先简单的说一下 我代码 的 思路: 我 是用的 结构体 来 存储的 ,然后我把 求解快速幂的 函数 改成了 求解 一个 矩阵的 快速幂的 函数 , 这其中呢 我还运用啦 operator 的 加载 的方法 简化啦 运算 ,这个 加载 的方法 我感觉很 好用 可以让结构体 变量 想 其他类型的 变量 一样 实现 各种 运算 !<<(~”’.?.”’~)>>

代码 如下 :

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mod 1000000009
#define LL long long
using namespace std;struct Matrix
{LL x1, x2;LL x3, x4;Matrix operator * (Matrix &o) // 加载 结构体乘法{Matrix ans;ans.x1 = (this->x1 * o.x1 + this->x2 * o.x3) % mod;ans.x2 = (this->x1 * o.x2 + this->x2 * o.x4) % mod;ans.x3 = (this->x3 * o.x1 + this->x4 * o.x3) % mod;ans.x4 = (this->x3 * o.x2 + this->x4 * o.x4) % mod;return ans;}
};LL Power(const Matrix a, LL b)
{Matrix ret;ret.x1 = 1; ret.x2 = 0;ret.x3 = 0; ret.x4 = 1;Matrix temp = a;while(b){if(b & 1) ret = ret * temp;temp  = temp * temp;b /= 2;}return ret.x1;
}int main()
{LL n;while(scanf("%lld", &n) != EOF){Matrix temp;LL ans;temp.x1 = 1; temp.x2 = 1;temp.x3 = 1; temp.x4 = 0;if(n <= 2)ans = 1;elseans = Power(temp, n-1);printf("%lld\n", ans);}return 0;
}