题意:
给你一个区间,问这个区间有多少个斐波那契数.
思路:
水的大数,可以直接模拟,要是懒可以用JAVA,我模拟的,打表打到1000个就足够用了…
#include<stdio.h>
#include<string.h>
int a[110] ,b[110];
int num[1200][110];void csh_num()
{
memset(num ,0 ,sizeof(num));
num[1][1] = 1 ,num[1][0] = 1;
num[2][1] = 2 ,num[2][0] = 1;
for(int i = 3 ;i <= 1000 ;i ++)
{
for(int j = 1 ;j <= 105 ;j ++)
num[i][j] = num[i-1][j] + num[i-2][j];
for(int j = 1 ;j <= 105 ;j ++)
{
num[i][j+1] += num[i][j] / 10;
num[i][j] %= 10;
}
} for(int i = 3 ;i <= 1000 ;i ++)
{
int kg = 0 ,sum = 0;
for(int j = 105 ;j >= 1 ;j --)
{
if(num[i][j]) kg = 1;
if(kg) num[i][0]++;
}
}
return ;
}bool campa(int i ,int la)
{
if(num[i][0] > la) return 1;
if(num[i][0] < la) return 0;
for(int ii = la ;ii >= 1 ;ii --)
{
if(num[i][ii] == a[ii]) continue;
if(num[i][ii] > a[ii]) return 1;
else return 0;
}
return 1;
}bool campb(int i ,int lb)
{
if(num[i][0] > lb) return 0;
if(num[i][0] < lb) return 1;
for(int ii = lb ;ii >= 1 ;ii --)
{
if(num[i][ii] == b[ii]) continue;
if(num[i][ii] > b[ii]) return 0;
else return 1;
}
return 1;
}int main ()
{
csh_num();
int i ,j ,sum;
char stra[105] ,strb[105];
while(~scanf("%s %s" ,stra ,strb) && strcmp(stra ,"0") + strcmp(strb ,"0"))
{
memset(a ,0 ,sizeof(a));
int la = strlen(stra) - 1;
int tt = 0;
for(i = la ;i >= 0 ;i --)
a[++tt] = stra[i] - 48; memset(b ,0 ,sizeof(b));
int lb = strlen(strb) - 1;
tt = 0;
for(i = lb ;i >= 0 ;i --)
b[++tt] = strb[i] - 48;
la++ ,lb++; sum = 0;
for(i = 1 ;i <= 1000 ;i ++)
{
if(!campb(i ,lb)) break;
if(campa(i ,la)) sum ++;
} printf("%d\n" ,sum);
}
return 0;
}