http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=259#problem/C
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 我所遇到的问题和解析都在代码中，可以参考一下
#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> using namespace std; int f[605][1000];//第一个下标代表第几个斐波那契数，第二个下 //标为存储斐波那契大数的数组 char shu[605][1000];//是为了更好的进行对比的拷贝数组 int main() { memset(f,0,sizeof(f)); memset(shu,0,sizeof(shu)); f[1][0]=1; f[2][0]=2; f[3][0]=3; for(int i=4;i<=600;i++){ for(int j=0;j<501;j++){ f[i][j]=f[i][j]+f[i-1][j]+f[i-2][j];//第一个问题; //为什么要多加一个f[i][j], //是因为下面有进位的现象，需要加上进位的值 if(f[i][j]>9){ f[i][j+1]=f[i][j]/10; f[i][j]=f[i][j]%10; } } //printf("%lld\n",f[i]); } int flag=0,k; for(int i=1;i<=600;i++){ flag=0;//第二个问题 //为什么要进行flag标记 //因为flag标记是为了去以防中间数也有零直接跳过，所以在第一个 // 非零输出先后，后面的数都要记下俩如果只是简单地用if（f[i][j]）， // 会很容易跳过中间的零。 k=0; for(int j=500;j>=0;j--){ if(flag||f[i][j]){ flag=1; shu[i][k]=f[i][j]+'0'; k++; } } shu[i][k]='\0'; //printf("%s\n",shu[i]); } char m[601],n[601]; while(scanf("%s %s",&n,&m)){ if(n[0]=='0'&&m[0]=='0') break; int sum=0; int len1=strlen(n); int len2=strlen(m); // printf("%d %d++\n",len1,len2); for(int i=1;i<=500;i++){ //printf("%s\n",shu[i]); if(strlen(shu[i])>len1&&strlen(shu[i])<len2){ //如果这个数的长度在范围之（n,m)长度之间， //则这个数一定属于（n,m); //printf("%s\n",shu[i]); sum++; } else if(len1==len2&&strlen(shu[i])==len1&&strcmp(shu[i],n)>=0&&strcmp(shu[i],m)<=0){///如果（n,m)两个数长度一样,则比较他们在字典中的大小。 sum++; } else if(len1!=len2&&strlen(shu[i])==len1&&strcmp(shu[i],n)>=0){ //若果长度不相等（n,m），与前面的n长度相等，说明相对较小， //只需要和n比较大小（比n大就好） sum++; } else if(len1!=len2&&strlen(shu[i])==len2&&strcmp(shu[i],m)<=0){ //若果长度不相等（n,m），等与后面的m长度相等，说明相对较大， 只需要和m比较大小（比m小就好） sum++; } } printf("%d\n",sum); } return 0; }strcmp函数是string compare(字符串比较)的缩写，用于比较两个字符串并根据比较结果返回整数。基本形式为strcmp(str1,str2)，若str1=str2，则返回零；若str1<str2，则返回负数；若str1>str2，则返回正数。
