Description
我们定义斐波那契数列如下:
f1=1
f2=2
f(n)=f(n-1)+f(n-2)(n>=3)
现在,给定两个数a和b,计算有多少个斐波那契数列中的数在a和b之间(包含边界)。
Input
输入包含多组测试数据,每组测试数据都是两个非负整数a和b,当a和b都等于0时,程序结束。0<=a<=b<=10^100,注意a和b都不会出现前导0的情况(即首位为0)。
Output
输出在a和b之间(满足a<=f(i)<=b)数的数量。
Sample Input
10 100
1234567890 9876543210
0 0
Sample Output
5
4
注:代码有点问题,系统过不了(hdu 1316) #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string.h>
#include <malloc.h>
using namespace std; void add(char* a,char* b,char* c)
{
int i,j,k,max,min,n,temp;
char *s,*pmax,*pmin;
max=strlen(a);
min=strlen(b);
if (max<min)
{
temp=max;
max=min;
min=temp;
pmax=b;
pmin=a;
}
else
{
pmax=a;
pmin=b;
}
s=(char*)malloc(sizeof(char)*(max+1));
s[0]='0';
for (i=min-1,j=max-1,k=max; i>=0; i--,j--,k--)
s[k]=pmin[i]-'0'+pmax[j];
for (; j>=0; j--,k--)
s[k]=pmax[j];
for (i=max; i>=0; i--)
if (s[i]>'9')
{
s[i]-=10;
s[i-1]++;
}
if (s[0]=='0')
{
for (i=0; i<=max; i++)
c[i-1]=s[i];
c[i-1]='\0';
}
else
{
for (i=0; i<=max; i++)
c[i]=s[i];
c[i]='\0';
}
free(s);
} char a[360][360]; int main()
{
int i,x,y,flag1,flag2;
char t1[105],t2[105]; strcpy(a[1],"1");
strcpy(a[2],"2");
for(i=3;i<360;i++)
add(a[i-1],a[i-2],a[i]); while(cin>>t1>>t2)
{
if(strcmp(t1,"0")==0&&strcmp(t2,"0")==0) break; flag1=0;flag2=0;
int len1=strlen(t1);
int len2=strlen(t2);
for(i=1;i<360;i++)
{
if(flag1==0&&strlen(a[i])==len1)
{
if(strcmp(a[i],t1)>=0)
{
flag1=1;
x=i;
}
}
if(flag1==0&&strlen(a[i])>len1)
{
flag1=1;
x=i;
} if(flag2==0&&strlen(a[i])==len2)
{
if(strcmp(a[i],t2)>=0)
{
flag2=1;
y=i;
if(strcmp(a[i],t2)>0)
y--;
}
}
if(flag2==0&&strlen(a[i])>len2)
{
flag2=1;
y=i-1;
}
}
cout<<y-x+1<<endl;
}
return 0;
}