1216: 斐波那契数列
时间限制: 1 Sec 内存限制: 128 MB
点我
题目描述
Fibonacci数列,定义如下:
f(1)=f(2)=1
f(n)=f(n-1)+f(n-2) n>=3
计算第n项Fibonacci数值。
输入
输入第一行为一个整数n(1<=n<=10000)。
输出
输出对应的f(n)。
样例输入
1 2 3 4 5
样例输出
1 1 2 3 5 数组中每个元素存储3位,存储一位则内存超限,还有要注意每一个元素中前导为0时要把0输出,最高位则不需要,被这个给坑了
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 using namespace std;
5 #define len 100000000
6 int a[10001][1000];
7 int main()
8 {
9 int n,c,i,j;
10 memset(a,0,sizeof(a));
11 a[1][0]=a[2][0]=1;
12 for(i=3;i<10001;i++)
13 {
14 c=0;
15 for(j=0;j<=999;j++)
16 {
17 a[i][j]=(a[i-2][j]+a[i-1][j]+c)%len;
18 c=(a[i-2][j]+a[i-1][j]+c)/len;
19 }
20 }
21 while(cin>>n)
22 {
23 for(i=999;i>=0;i--)
24 if(a[n][i]!=0)
25 break;
26 cout<<a[n][i];
27 for(i--;i>=0;i--)
28 {
29 printf("%08d",a[n][i]);
30 }
31 cout<<endl;
32 }
33 }
转载于:https://www.cnblogs.com/a1225234/p/4675601.html