Posted on 2011-05-22 13:56
acpeng 閱讀(441)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ACM程序
OJ地址：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1828f(1) = 1, f(2) = 1, f(n > 2) = f(n - 1) + f(n - 2)。
輸入n，計(jì)算f(n)。f(n)位數(shù)小于1000。
Sample Input
100
Sample Output
354224848179261915075
基本思路，字符串方式模擬計(jì)算過程。簡單題。
1 /*
2 計(jì)算Fibonacci數(shù)列第 n 項(xiàng)
3 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1828
4 */
5 #include<stdio.h>
6 #include<string.h>
7 void addstr(char *str1,char *str2,char *str3)
8 {
9 int lgth1,lgth2,c,tmp,i,j,k;
10 char add1num,add2num;
11 lgth1=(int)strlen(str1);lgth2=(int)strlen(str2);
12 k=lgth1>lgth2?lgth1:lgth2;
13 str3[k+1]='\0';
14 i=0;j=0;
15 while(*(str1+i)!='\0')i++;i--;
16 while(*(str2+j)!='\0')j++;j--;
17 c=0;
18 for(;i>=0 || j>=0;i--,j--,k--)
19 {
20 if(j<0)add2num='0';
21 else add2num=*(str2+j);
22 if(i<0)add1num='0';
23 else add1num=*(str1+i);
24 tmp=add1num-'0'+add2num-'0'+c;
25 *(str3+k)=tmp%10+'0';
26 c=tmp/10;
27 }
28 if(c!=0)
29 *(str3+k)=c+'0';
30 else
31 {
32 for(i=0;*(str3+i+1)!='\0';i++)
33 *(str3+i)=*(str3+i+1);
34 *(str3+i)='\0';
35 }
36 }
37
38 int main()
39 {
40 int n,j;
41 char str1[1003],str2[1003],Fibo[1003];
42 while(scanf("%d",&n)!=EOF)
43 {
44 memset(str1,0,1003);
45 memset(str2,0,1003);
46 memset(Fibo,0,1003);
47 strcpy(str2,"1");
48 for(j=1;j<=n;j++)
49 {
50 memset(str1,0,1003);
51 strcpy(str1,str2);
52 memset(str2,0,1003);
53 strcpy(str2,Fibo);
54 addstr(str1,str2,Fibo);
55 }
56 printf("%s\n",Fibo);
57 }
58 return 0;
59 }