生活随笔
收集整理的这篇文章主要介绍了
(大整数类Biginteger)大斐波数
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
题目
Fibonacci数列，定义如下：
f(1)=f(2)=1
f(n)=f(n-1)+f(n-2) n>=3。
计算第n项Fibonacci数值。
输入
输入第一行为一个整数N，接下来N行为整数Pi（1<=Pi<=1000）。
输出
输出为N行，每行为对应的f(Pi)。
样例输入
5
1
2
3
4
5
样例输出
1
1
2
3
5
分析与解答：
biginteger分析参见：
https://blog.csdn.net/mrcrack/article/details/53263235
代码：
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
struct BigInteger {
static const int BASE =
100000000;
static const int WIDTH =
8;
vector<int> s;BigInteger(
long long num =
0) { *
this = num; } BigInteger
operator = (
long long num) { s.clear();
do {s.push_back(num % BASE);num /= BASE;}
while (num >
0);
return *
this;}BigInteger
operator = (
const string& str) { s.clear();
int x, len = (str.length() -
1) / WIDTH +
1;
for (
int i =
0; i < len; i++) {
int end = str.length() - i*WIDTH;
int start = max(
0, end - WIDTH);
sscanf(str.substr(start, end - start).c_str(),
"%d", &x);s.push_back(x);}
return *
this;}BigInteger
operator + (
const BigInteger& b)
const {BigInteger c;c.s.clear();
for (
int i =
0, g =
0; ; i++) {
if (g ==
0 && i >= s.size() && i >= b.s.size())
break;
int x = g;
if (i < s.size()) x += s[i];
if (i < b.s.size()) x += b.s[i];c.s.push_back(x % BASE);g = x / BASE;}
return c;}
};ostream&
operator << (ostream &out,
const BigInteger& x) {out << x.s.back();
for (
int i = x.s.size() -
2; i >=
0; i--) {
char buf[
20];
sprintf(buf,
"%08d", x.s[i]);
for (
int j =
0; j <
strlen(buf); j++) out << buf[j];}
return out;
}istream&
operator >> (istream &in, BigInteger& x) {
string s;
if (!(in >> s))
return in;x = s;
return in;
}
int main(){BigInteger a,b,ans[
1005];ans[
1]=
1;ans[
2]=
1;
for(
int i=
3;i<=
1001;++i){ans[i]=ans[i-
1]+ans[i-
2];}
int n;
cin>>n;
while(n--){
int i;
cin>>i;
cout<<ans[i]<<endl;}
}
总结
以上是生活随笔为你收集整理的(大整数类Biginteger)大斐波数的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
