Description
以下数列 0 1 1 2 3 5 8 13 21 ... 被称为斐波纳契数列。
这个数列从第 33 项开始，每一项都等于前两项之和。
输入一个整数 N，请你输出这个序列的前 N 项。
输入格式
一个整数 N。
输出格式
在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。
数据范围
0 < N < 46
输入样例：
5
输出样例：
0 1 1 2 3
| 难度： | 中等 |
| 时/空限制 | 1s / 64MB |
递归版本
#include<iostream> using namespace std; int main() { long long f[50]; int n; cin >> n; f[1] = 0; f[2] = 1; for(int i = 3; i <= n;i ++) f[i] = f[i - 1] + f[i - 2]; for(int i = 1;i <= n;i ++) cout << f[i] << ' '; return 0; }
递推版本
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int main() { int n; cin>>n; int a = 0,b = 1; for(int i = 1;i <= n;i ++) { cout<< a << ' '; int fn = a + b; a = b, b = fn; } return 0; }
算法模板
首先定义斐波那契数列问题：
递归
const int MOD = 1000000007; int f(int n) { if (n <= 1) return 1; return (f(n - 1) + f(n - 2)) % MOD; }
记忆化搜索
const int N = 100000, MOD = 1000000007; int a[N]; int f2(int n) { if (a[n]) return a[n]; if (n <= 1) return 1; a[n] = f2(n - 1) + f2(n - 2); a[n] %= MOD; return a[n]; }
递推
const int N = 100000000, MOD = 1000000007; int f3(int n) { a[0] = a[1] = 1; for (int i = 2; i <= n; i ++ ) { a[i] = a[i - 1] + a[i - 2]; a[i] %= MOD; } return a[n]; }
递推+滚动变量
仔细观察我们会发现，递推时我们只需要记录前两项的值即可，没有必要记录所有值，所以我们可以用滚动变量递推。
时间复杂度还是 O(n)，但空间复杂度变成了 O(1) 。
const int MOD = 1000000007; int f4(int n) { int x, y, z; x = y = 1; for (int i = 2; i <= n; i ++ ) { z = (x + y) % MOD; x = y; y = z; } return z; }
矩阵运算 + 快速幂
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <ctime> using namespace std; const int MOD = 1000000007; void mul(int a[][2], int b[][2], int c[][2]) { int temp[][2] = {{0, 0}, {0, 0}}; for (int i = 0; i < 2; i ++ ) for (int j = 0; j < 2; j ++ ) for (int k = 0; k < 2; k ++ ) { long long x = temp[i][j] + (long long)a[i][k] * b[k][j]; temp[i][j] = x % MOD; } for (int i = 0; i < 2; i ++ ) for (int j = 0; j < 2; j ++ ) c[i][j] = temp[i][j]; } int f_final(long long n) { int x[2] = {1, 1}; int res[][2] = {{1, 0}, {0, 1}}; int t[][2] = {{1, 1}, {1, 0}}; long long k = n - 1; while (k) { if (k&1) mul(res, t, res); mul(t, t, t); k >>= 1; } int c[2] = {0, 0}; for (int i = 0; i < 2; i ++ ) for (int j = 0; j < 2; j ++ ) { long long r = c[i] + (long long)x[j] * res[j][i]; c[i] = r % MOD; } return c[0]; } int main() { long long n ; cin >> n; cout << f_final(n) << endl; return 0; }
快速幂算法模板
int qmi(int m, int k, int p) { int res = 1 % p, t = m; while (k) { if (k&1) res = res * t % p; t = t * t % p; k >>= 1; } return res; }
