算法
- 高精度
- 斐波那契数列
- 阶乘
y总的分享: 求解斐波那契数列的若干方法
高精度加法
#include <iostream>
#include <cstring>
#include <algorithm>
#include<vector>
using namespace std;
const int N = 100010;
vector<int> A, B, C;
vector<int> add(vector<int> &A, vector<int> &B)
{
int t = 0;
for(int i = 0; i < A.size() || i < B.size(); i ++)
{
if(i < A.size()) t += A[i];
if(i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
//最高位如果进位还有1,那么进位+1
if(t) C.push_back(1);
return C;
}
int main()
{
string a, b;
cin >> a >> b;
for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] -'0');
for(int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');
C = add(A, B);
for(int i = C.size() - 1; i >= 0; i --)
cout << C[i];
return 0;
}
高精度乘法
#include <iostream>
#include <cstring>
#include <algorithm>
#include<vector>
using namespace std;
vector<int> A, C;
vector<int> mul(vector<int> &A, int b)
{
int t = 0;
for(int i = 0; i < A.size() || t; i ++)
{
if(i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
return C;
}
int main()
{
string a;
int b;
cin >> a >> b;
if(b == 0)
{
cout << 0 << endl;
return 0;
}
for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
C = mul(A, b);
for(int i = C.size() - 1; i >= 0; i --) cout << C[i];
return 0;
}
斐波那契数列
递推:(N < 46)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50;
int a[N];
int main()
{
int n;
cin >> n;
a[1] = 0;
a[2] = 1;
for(int i = 3; i <= n; i ++){
a[i] = a[i - 1] + a[i - 2];
}
for(int i = 1; i <= n; i ++) cout << a[i] << " ";
return 0;
}
高精度加法:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1010;
vector<int> f[N], A, B;
vector<int> add(vector<int> &A, vector<int> &B)
{
int t = 0;
vector<int> C;
for(int i = 0; i < A.size() || i < B.size(); i ++)
{
if(i < A.size()) t += A[i];
if(i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
//如果最高位还有进位1
if(t) C.push_back(1);
return C;
}
int main()
{
int n;
cin >> n;
f[0] = {0};
f[1] = {1};
for(int i = 2; i <= 1000; i ++)
f[i] = add(f[i - 1], f[i - 2]);
for(int j = 0; j < n; j ++)
{
for(int i = f[j].size() - 1; i >= 0; i --)
{
cout << f[j][i];
}
cout << " ";
}
return 0;
}
求和
如果要求斐波那契数列第某个数是多少,可以将代码改为:
for(int i = f[n - 1].size() - 1; i >= 0; i --)
{
cout << f[n - 1][i];
}
//6
//0 1 1 2 3 5
//第六个数是5
阶乘
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int N = 1010, M = 1e6;
vector<int> f[N];
vector<int> mul(vector<int> &A, int b){
vector<int> C;
int t = 0; //进位
for(int i = 0; i < A.size() || t; i ++){
if(i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
return C;
}
int main()
{
//预处理
f[0] = {1};
for(int i = 1; i <= 1000; i ++){
f[i] = mul(f[i - 1], i);
}
int n;
cin >> n;
for(int i = f[n].size() - 1; i >= 0; i --) cout << f[n][i];
return 0;
}