首页 > 代码库 > HDU 1250 大数加法
HDU 1250 大数加法
Hat‘s Fibonacci
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6948 Accepted Submission(s): 2285
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.
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.
大数加法,简单。。。但是这道题给我的感觉是蛋疼。。。可能状态不行,脑残错误搞了1个多小时。
两个数组没初始化。。。然后题目范围没给出,我提交了一遍又一遍总是WA,害的我以为是我代码错误,题目范围从1000试到7100终于过了。。。
代码:
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include <map> 5 #include <iostream> 6 #include <string> 7 using namespace std; 8 9 void add(char *s1,char *s2,char *a)10 {11 int n1=strlen(s1);12 int n2=strlen(s2);13 int c1[3000], c2[3000];14 int i, j, k=0, num;15 memset(c1,0,sizeof(c1));16 memset(c2,0,sizeof(c2));17 for(i=0;i<n1;i++)18 c1[i]=s1[n1-i-1]-‘0‘;19 for(i=0;i<n2;i++)20 c2[i]=s2[n2-i-1]-‘0‘;21 n1=max(n1,n2);22 for(i=0;i<=n1;i++)23 {24 num=c1[i]+c2[i]+k;25 if(num>=10)26 {27 num-=10;28 k=1;29 }30 else k=0;31 c1[i]=num;32 }33 34 k=n1+2;35 36 while(c1[k]==0)37 k--;38 for(i=0;i<=k;i++)39 a[i]=c1[k-i]+‘0‘;40 a[k+1]=‘\0‘;41 42 }43 44 char f[8000][2050];45 46 main()47 {48 char a[3000], b[3000];49 int i, j, k, n;50 for(i=1;i<=4;i++)51 strcpy(f[i],"1");52 for(i=5;i<7100;i++)53 {54 add(f[i-1],f[i-2],a);55 add(f[i-3],f[i-4],b);56 add(a,b,f[i]);57 }58 59 while(scanf("%d",&n)==1)60 {61 62 printf("%s\n",f[n]);63 }64 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。