链接：点击打开链接
题意：问区间[a,b]中有多少斐波那契数
代码：
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define N 10000
#define M 300
char str[N][M];
int cmp(char *a,char *b){
int len1,len2;
len1=strlen(a);
len2=strlen(b);
if(len1>len2)
return 1;
if(len1<len2)
return -1;
if(len1==len2){
if(strcmp(a,b)==0)
return 0;
else if(strcmp(a,b)>0)
return 1;
else if(strcmp(a,b)<0)
return -1;
}
} //由于斐波那契不是依照字符顺序排序，因此自写一个cmp函数
void overthrow(char *s){
int i,j;
i=M-1;
while(s[i]=='0')
i--;
s[i+1]=' ';
for(j=0;j<=i/2;j++)
swap(s[j],s[i-j]);
} //由于是从左右往右加的,所以将高位和地位互换
void bignumber(){
long long i,j,t;
str[1][0]='1';str[2][0]='2';
for(i=3;i<N;i++){
t=0;
for(j=0;j<M;j++){
t=t+str[i-1][j]-'0'+str[i-2][j]-'0';
str[i][j]=t%10+'0';
t/=10;
}
}
} //大数斐波那契,注意是字符想加的时候要-'0'
int binsearch1(char *s){
int low,high,mid;
low=1;high=N;
while(low<=high){
mid=(low+high)/2;
if(cmp(str[mid],s)==0)
return mid;
else if(cmp(str[mid],s)>0)
high=mid-1;
else if(cmp(str[mid],s)<0)
low=mid+1;
}
return low;
} //返回比要查找的数较大的数的下标
int binsearch2(char *s){
int low,high,mid;
low=1;high=N;
while(low<=high){
mid=(low+high)/2;
if(cmp(str[mid],s)==0)
return mid;
else if(cmp(str[mid],s)>0)
high=mid-1;
else if(cmp(str[mid],s)<0)
low=mid+1;
}
return high;
} //返回比要查找的数较小的数的下标
int main(){
char a[305],b[305];
int i,j,sum;
for(i=1;i<N;i++)
for(j=0;j<M;j++)
str[i][j]='0'; //初始化为字符'0'
bignumber();
for(i=1;i<N;i++)
overthrow(str[i]); //调用完bignumber(),之后翻转每个斐波那契数
// for(i=1;i<=20;i++)
// cout<<str[i]<<endl;
while(cin>>a>>b){
if(strcmp(a,"0")==0&&strcmp(b,"0")==0)
break;
// cout<<binsearch1(a)<<endl;
// cout<<binsearch2(b)<<endl;
sum=binsearch2(b)-binsearch1(a)+1; //不要忘记加1
printf("%d
",sum);
}
return 0;
}