- Hat's Fibonacci
- Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
- Total Submission(s): 12284 Accepted Submission(s): 4124
- Problem Description
A Fibonacci sequence is calculated by adding the previous two members the sequence, with the first two members being both 1.
F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)
Your task is to take a number as input, and print that Fibonacci number.
Input
Each line will contain an integers. Process to end of file.
Output
For each case, output the result in a line.
- Sample Input
- 100
- Sample Output
- 4203968145672990846840663646
Note:No generated Fibonacci number in excess of 2005 digits will be in the test data, ie. F(20) = 66526 has 5 digits.
用 string 会超时, 以下为超时代码.
- #include <iostream>
- #include <string>
- using namespace std;
- string add(string a,string b)
- {
- int len1=a.length();
- int len2=b.length();
- int i;
- if(len1>len2)
- {
- for(i=1;i<=len1-len2;i++)
- b="0"+b;
- }
- else
- {
- for(i=1;i<=len2-len1;i++)
- a="0"+a;
- }
- string str;
- int cf=0,t;
- len1=a.length();
- for(i=len1-1;i>=0;i--)
- {
- t=a[i]-'0'+b[i]-'0'+cf;
- cf=t/10;
- t%=10;
- str=char(t+'0')+str;
- }
- if(cf!=0)
- str=char(cf+'0')+str;
- return str;
- }
- string fun(int n)
- {
- string f[10010];
- f[1]="1";
- f[2]="1";
- f[3]="1";
- f[4]="1";
- int i;
- string a,b,c;
- for(i=5;i<=n;i++)
- {
- a=add(f[i-1],f[i-2]);
- b=add(f[i-3],f[i-4]);
- f[i]=add(a,b);
- }
- return f[n];
- }
- int main()
- {
- int n;
- while(cin>>n)
- {
- string str;
- str=fun(n);
- cout<<str<<endl;
- cout<<endl;
- }
- return 0;
- }
- View Code
正确的代码
方法一:
利用二维数组和亿进制.
- #include<cstdio>
- #include <iostream>
- #include<cstring>
- using namespace std;
- int str[10001][260]; // 必须为 int 类型.
- int main()
- {
- memset(str,0,sizeof(str));
- str[1][0]=1;
- str[2][0]=1;
- str[3][0]=1;
- str[4][0]=1;
- int i,j,ans=0,c,n;
- for(i=5;i<10001;i++)
- {
- for(j=0,c=0;j<260;j++) // 循环, 来将 j 个数组的 8 位数字的情况全部列举出.
- {
- ans=str[i-1][j]+str[i-2][j]+str[i-3][j]+str[i-4][j]+c;
- c=ans/100000000;
- str[i][j]=ans%100000000; // 每一个数组存 8 位数字, c 来判定是否进位.
- }
- }
- while(cin>>n)
- {
- j=259;
- while(!str[n][j]) // 首位有 0, 清除掉 0.
- j--;
- cout<<str[n][j]; // 开头的首 0 清除掉后的 x 位数字, 可能小于 8 位.
- for(i=j-1;i>=0;i--)
- printf("%08d",str[n][i]); // 每 8 位数字输出一组, 不足的自动部 0.
- printf("\n");
- }
- return 0;
- }
方法二:
利用滚动数组求解
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- int t[6][2555];
- int main()
- {
- int n;
- while(scanf("%d",&n) != EOF)
- {
- memset(t,0,sizeof(t));
- t[0][0] = 1;
- t[1][0] = 1;
- t[2][0] = 1;
- t[3][0] = 1;
- for(int i = 4;i <n;i++)
- {
- int carry = 0;
- int k = i % 4;
- for(int j = 0;j < 2500;j++)
- {
- int x = t[0][j] + t[1][j] + t[2][j] + t[3][j];
- t[k][j] = x + carry;
- carry = t[k][j] / 10;
- t[k][j] %= 10;
- }
- }
- int k = 2500;
- while(t[(n - 1) % 4][--k] == 0);
- for(int i = k;i>= 0;i--)
- {
- printf("%d",t[(n - 1) % 4][i]);
- }
- printf("\n");
- }
- return 0;
- }
- View Code
用 JAVA
- import java.math.BigInteger;
- import java.util.Scanner;
- public class Main {
- public static void main(String[] args) {
- Scanner in = new Scanner (System.in);
- BigInteger a[]=new BigInteger[10001];
- int n;
- while(in.hasNextInt()) {
- n=in.nextInt();
- a[1]=BigInteger.ONE;
- a[2]=BigInteger.ONE;
- a[3]=BigInteger.ONE;
- a[4]=BigInteger.ONE;
- for(int i=5;i<=10000;i++) {
- a[i]=BigInteger.ZERO;
- a[i]=a[i].add(a[i-1]);
- a[i]=a[i].add(a[i-2]);
- a[i]=a[i].add(a[i-3]);
- a[i]=a[i].add(a[i-4]);
- }
- System.out.println(a[n]);
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2639694.html