Description

给你如下Fibonacci 数的定义：
F1 = 1 
F2 = 2 
Fn = Fn-1 + Fn-2 (n >= 3) 
给你两个数a与b，现要求你计算在a与b之间（包括a、b）有多少个Fibonacci 数

输入格式

有多行，每行有两个数a、b，使用空格分隔，a <= b <= 10^100（即最大10的100次方）
最后一行为两个0

输出格式

除了最后一行，其它每一行要求输出在a与b之间的Fibonacci 数的个数，一行一个

输入样例

10 100
1234567890 9876543210
0 0

输出样例

5
4

作者

admin

这题刚开始做时懵逼了好久，后来别人提示了下才会做。。。各种坑。。。（代码注释里讲解解题步骤）

  1 /*#include <cstdio>
  2 #include <cstring>
  3 #define N 1000
  4 
  5 using namespace std;
  6 char f[N+5][N];
  7 //
  8 //高精度加法
  9 void big_plus(char a[],char b[],int t)
 10 {
 11     int c[N],d[N];
 12     memset(c,0,sizeof(c));memset(d,0,sizeof(d));//数组全部清0。
 13     int len_a,len_b,i,j,k;
 14     //
 15     i=1;
 16     len_a=strlen(a);len_b=strlen(b);
 17     //
 18     //将字符数组转为整型数组，逆方向。
 19     for(k=len_a-1;k>=0;k--)
 20         c[i++]=a[k]-'0';
 21     j=1;
 22     for(k=len_b-1;k>=0;k--)
 23         d[j++]=b[k]-'0';
 24     //
 25     k=len_a>len_b?len_a:len_b;
 26     for(i=1;i<=k;i++)//将每一位相加，满十进位。
 27     {
 28         c[i+1]+=(c[i]+d[i])/10;
 29         c[i]=(c[i]+d[i])%10;
 30     }
 31     //
 32     if(c[k+1]) //判断最高位是否有进位
 33         k=k+1;
 34     j=0;
 35     for(i=k;i>=1;i--) //将整型数组转变为字符数组存到f数组里。
 36         f[t][j++]=c[i]+'0';
 37 }
 38 //
 39 
 40 int big_cmp(char a[],char b[])//高精度 数字比较。a>b返回1，a=b返回0，a<b返回-1。
 41 {
 42     int i,len_a,len_b;
 43     len_a=strlen(a);
 44     len_b=strlen(b);
 45     //
 46     if(len_a>len_b)
 47         return 1;
 48     else if(len_a<len_b)
 49         return 0;
 50     else
 51     {
 52         for(i=0;i<len_a;i++)
 53         {
 54             if(a[i]>b[i])
 55                 return 1;
 56             else if(a[i]<b[i])
 57                 return 0;
 58             else continue;
 59         }
 60     }
 61     return -1; //上面的return均未执行，则说明a==b。
 62 }
 63 int main()
 64 {
 65     int i,j;
 66     char f1[N],f2[N];
 67     memset(f,'',sizeof(f));
 68     f[1][0]='1'; f[2][0]='2';
 69     //
 70     //下面循环累加，打表法。
 71     for(i=3;i<=N;i++)
 72     {
 73         big_plus(f[i-2],f[i-1],i);
 74     }
 75     //
 76     while(scanf("%s%s",f1,f2))
 77     {
 78         int cnt=0;
 79         if((f1[0]-'0')==0||(f2[0]-'0')==0)
 80             break;
 81         //
 82         for(i=1;i<=N;i++)//这个循环用来找f1的位置
 83         {
 84             if(big_cmp(f[i],f1)==-1)
 85             {
 86                 cnt=1;
 87                 i++;
 88                 break;
 89             }
 90             if(big_cmp(f[i],f1)>0)
 91             {
 92                 cnt=0;
 93                 break;
 94             }
 95         }
 96         for(j=i;j<=N;j++)//这个循环用来找f2的位置
 97         {
 98             if(big_cmp(f[j],f2)<=0)
 99                 ++cnt;
100             else
101                 break;
102         }
103         //
104         printf("%d
",cnt);
105     }
106 
107 
108     return 0;
109 }
110 */
111 
112 #include<cstdio>
113 #include<cstring>
114 #define N 1000
115 char fb[N+5][N];//存储前1000项的fb
116 //高精度数比较 返回1表示a>b  返回-1表示a=b   0表示a<b
117 int big_cmp(char a[],char b[])
118 {
119     int i,len_a,len_b;
120     len_a=strlen(a);
121     len_b=strlen(b);
122     if(len_a>len_b) return 1;//先比长度
123     else if(len_a<len_b) return 0;
124     else//长度相同的时候再从高位开始逐一比较
125     {
126         for(i=0; i<len_a; i++)
127         {
128             if(a[i]>b[i]) return 1;
129             else if(a[i]<b[i]) return 0;
130             else continue;
131         }
132     }
133     return -1;//全部比较完毕，以上return未生效      就是 a=b
134 }
135 //高精度加法
136 void big_plus(char a[],char b[],int t)
137 {
138     int c[N],d[N];
139     memset(c,0,sizeof(c));  //数组全部清0。
140     memset(d,0,sizeof(d));
141     int len_a,len_b,i,j,k;
142     i=1;
143     len_a=strlen(a);
144     len_b=strlen(b);
145     //字符数组转为整形数组 ，逆置存放
146     for(k=len_a-1; k>=0; k--)
147         c[i++]=a[k]-'0';
148     j=1;
149     for(k=len_b-1; k>=0; k--)
150         d[j++]=b[k]-'0';
151 
152     k=len_a>len_b?len_a:len_b;
153     for(i=1; i<=k; i++)   //将每一位相加，满十进位。
154     {
155         c[i+1]+=(c[i]+d[i])/10;
156         c[i]=(c[i]+d[i])%10;
157     }
158     if(c[k+1]) k=k+1; //判断最高位是否有进位
159 
160     j=0;
161     for(i=k; i>=1; i--)   //将整形数组，转化为字符数组存在fb数组
162         fb[t][j++]=c[i]+'0';
163 }
164 int main()
165 {
166     int i,j;
167     char s1[N],s2[N];
168     memset(fb,'',sizeof(fb));
169     fb[1][0]='1';
170     fb[2][0]='2';
171     //下面循环累加，打表法。
172     for(i=3; i<=N; i++)
173         big_plus(fb[i-2],fb[i-1],i);
174 
175     while(scanf("%s%s",s1,s2))
176     {
177         int cnt=0;
178         if(!((s1[0]-'0')||(s2[0]-'0'))) break;
179         for(i=1; i<=N; i++)
180         {
181             //查找a的位置 i
182             if(big_cmp(fb[i],s1)==-1)
183             {
184                 cnt=1;
185                 i++;
186                 break;
187             }
188             if(big_cmp(fb[i],s1)>0)
189             {
190                 cnt=0;
191                 break;
192             }
193         }
194         for(j=i; j<=N; j++)
195             if(big_cmp(fb[j],s2)<=0) cnt++;
196             else break;
197         printf("%d
",cnt);
198     }
199     return 0;
200 }