- 王靖翔 的博客
斐波那契数的几种方式
- 2023-3-15 20:54:33 @
递归
递归也是计算斐波那契数最常见的了,也是最不省时间的,毕竟斐波那契数的增长很快。因为只要一个数大,那么下一个数会接近 2 倍的增长
#include <iostream>
using namespace std;
int fib(int n) {
if (n == 2 || n == 1) { // 终止条件
return 1;
} else {
return fib(n - 1) + fib(n - 2); // 前两项之和
}
}
int main() {
int number;
cin >> number;
cout << fib(number);
return 0;
}
记忆优化法/递推
记忆优化法是递归的升级版本,因为递归要每个数二叉遍历,但是我目前只知道一个数优化
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;
long long a[200 + 10]; // 别忘了 kll (开 long long)
int n;
int main() {
cin >> n;
a[1] = 1; // 和递归终止条件一样
a[2] = 1;
for (int i = 3; i <= n + 1; i++) { // 开始循环
a[i] = a[i - 1] + a[i - 2]; // 当前的数是前两项之和
}
cout << a[n]; // 输出当前的 n
return 0;
}
高精度
高精度是 的,因为高精度他本身就有一个好的运算方式,还支持大数的运算,然而我们这个斐波那契数列其实只用到高精度加法(前两项之和)再配上记忆优化法的方式,不过我们要用 a[i] = 高精度函数(a[i-1],a[i-2])
的方式
#include <bits/stdc++.h>
using namespace std;
string sum(string a, string b) { // 知周所众的高精度函数
if (a.size() < b.size()) {
swap(a, b);
}
for (int i = a.size() - 1, j = b.size() - 1; i >= 0; --i, --j) {
a[i] = char(a[i] + (j >= 0 ? b[j] - '0' : 0));
if (a[i] - '0' >= 10) { // 进位
a[i] = char((a[i] - '0') % 10 + '0');
if (i) {
a[i - 1] += 1;
} else {
a = '1' + a;
}
}
}
return a;
}
string fib[203]; // 先开个表
int main() {
fib[0] = "0";
fib[1] = "1";
for (int i = 2; i <= 200; ++i) {
fib[i] = sum(fib[i - 1], fib[i - 2]); // 记忆优化法
}
int x;
cin >> x;
cout << fib[x] << endl; // 直线输出
return 0; // 完美结束
}