首页 > 代码库 > HDU 1316 斐波那契数列+高精度

HDU 1316 斐波那契数列+高精度

2024-07-17 16:48:59   226人阅读

How Many Fibs?

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4235    Accepted Submission(s): 1669


Problem Description
Recall the definition of the Fibonacci numbers: 
f1 := 1 
f2 := 2 
fn := fn-1 + fn-2 (n >= 3) 

Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a, b]. 
 

 

Input
The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a = b = 0. Otherwise, a <= b <= 10^100. The numbers a and b are given with no superfluous leading zeros.
 

 

Output
For each test case output on a single line the number of Fibonacci numbers fi with a <= fi <= b. 
 

 

Sample Input
10 100
1234567890 9876543210
0 0
 

 

Sample Output
5
4
 
 
题意：
给定范围[a,b]（a<=b<=10^100），求在这范围内的斐波那契数有多少个。
 
 
思路：
在我印象中，1000项的斐波那契数好像就有200多位了，枚举1---1000项的斐波那契数放到数组里，然后strcmp求在[a,b]之间的斐波那契的个数。
 
 
代码：
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 #include <iostream> 6 using namespace std; 7  8 char a[110], b[110]; 9 char f[1005][500];10 int f1[500];11 int f2[500];12 13 void init_f(){                 //高精度加法初始化斐波那契数f[] 14     strcpy(f[0],"1");15     strcpy(f[1],"1");16     int i, j, k, l, r;17     for(i=2;i<=1000;i++){18         int n1=strlen(f[i-2]);19         int n2=strlen(f[i-1]);20         memset(f1,0,sizeof(f1));21         memset(f2,0,sizeof(f2));22         for(j=n1-1;j>=0;j--) f1[j]=f[i-2][n1-j-1]-‘0‘;23         for(j=n2-1;j>=0;j--) f2[j]=f[i-1][n2-j-1]-‘0‘;24         int c=0;25         while(j<=max(n1,n2)){26             f1[j]=f1[j]+f2[j]+c;27             if(f1[j]>=10) {28                 f1[j]-=10;c=1;29             }30             else c=0;31             j++;32         }33         k=max(n1,n2);34         while(!f1[k]) k--;          //去掉后面多余的0 35         for(j=k;j>=0;j--) f[i][j]=f1[k-j]+‘0‘;36     37     }38 }39 40 41 main()42 {43     init_f();44     int ans;45     while(scanf("%s%s",a,b)!=EOF&&(strcmp(a,"0")||strcmp(b,"0"))){46         int n1=strlen(a), n2=strlen(b);47         int flag;48         if(n1==n2) flag=1;49         else flag=0;50         ans=0;51         for(int i=1;i<=1000;i++){52             int n=strlen(f[i]);53             if(flag){                                 //当a和b的长度一样时 54                 if(n==n1&&strcmp(f[i],a)>=0&&strcmp(f[i],b)<=0) ans++;55                 if(n>n1||n==n1&&strcmp(f[i],b)>0) break;56                 continue;57             }58             if(n>n2||n==n2&&strcmp(f[i],b)>0) break;      //当a和b的长度不一样时 59             if(n>n1&&n<n2) {60                 ans++;continue;61             }62             if(n==n1&&strcmp(f[i],a)>=0) ans++;63             if(n==n2&&strcmp(f[i],b)<=0) ans++;64         }65         printf("%d\n",ans);66     }67 }

 


联系
我们