来简单地数个数 思路+代码

这是一个斐波那契数列：
f1 = 1 
f2 = 2 
fn = fn-1 + fn-2     (n>=3)
蔡老板想知道，给你两个数a、b，你能否求出在区间[a,b]里有多少个斐波那契数。

多组数据输入。一行为一组输入数据，包括两个非负整数a、b（a <= b <= 10^100），当a=b=0时输入终止。

对每组输入，输出单独一行，包含一个整数表示区间[a,b]里的斐波那契数个数。

因为区间最大要到10^100，所以我先算出斐波拉契数列前700（大概可以知道一定大于10^100）用数组存好，然后查找就好了。

用了大数加法模板

#include<bits/stdc++.h>
using namespace std;
#define BASE 10
#define N 90001
int l = 0;
char res[N] = { '\0' };
int BigCmp(char * a, char * b)
{int i,j,k;int la = strlen(a),lb = strlen(b);char * temp;if(la < lb)return 1;if(la > lb)return -1;if(la == lb){for(i = 0 ; i < la ; i++){if(a[i] < b[i])return 1;else if(a[i] > b[i])return -1;}}return 0;
}void ini(char * x ,int l)
{int i;if(l < N)l++;for(i = 0 ; i < l ;i++)x[i] = '\0';
}void Clean(char * x,int l)
{for(l--; x[l] == '0';l--)x[l] = '\0';
}void rev(char * x)
{int right = strlen(x)-1;int left = 0;char temp;while(left < right){temp = x[left];x[left++] = x[right];x[right--] = temp;}
}char *  BigAdd( char * a, char * b)
{int i,j,k;int sum,la,lb,carry,flag,cmp;char *ans,*temp;ini(res,l);carry = 0;flag = 0;ans = &res[1];la=strlen(a);lb=strlen(b);if(b[0] == '0' && lb == 1){strcpy(ans,a);l = strlen(ans);return ans;}else if(a[0] == '0' && la ==1){strcpy(ans,b);l = strlen(ans);return ans;}rev(a);rev(b);if(BigCmp(a,b) == 1){temp = a;a = b;b =temp;k = la;la = lb;lb = k;}for(i = lb ; i < la ; i++)b[i] = '0';for(i = 0 ; i < la ; i++){sum = (a[i]-48) + (b[i]-48) + carry;if( sum < BASE ){ans[i] = sum + 48;carry = 0;}else{ans[i] = sum  - BASE  + 48;carry = 1;}}if(carry){ans[i] = carry + 48;i++;}Clean(ans,i);for(i = lb ; i < la ; i++)b[i] = '\0';rev(ans);rev(a);rev(b);l = strlen(ans);return ans;
}
char sum[10000][200];
char p[1000],q[1000];
int z;
void shu()
{strcpy(sum[0],"1");strcpy(sum[1],"2");int b=700;z=2;while(b--){strcpy(sum[z],BigAdd(sum[z-1],sum[z-2]));z++;}
}
int main()
{shu();while(scanf("%s %s",p,q)!=EOF){if(strcmp("0",p)==0&&strcmp("0",q)==0) break;int k=0;for(int i=0;i<z-1;i++){if((BigCmp(sum[i],p)==0||BigCmp(sum[i],p)==-1)&&(BigCmp(sum[i],q)==0||BigCmp(sum[i],q)==1))k++;}cout<<k<<endl;}return 0;
}