本文共 2870 字，大约阅读时间需要 9 分钟。
**How Many Fibs?**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5366 Accepted Submission(s): 2088Problem DescriptionRecall the definition of the Fibonacci numbers: f1 := 1 f2 := 2 fn := fn-1 + fn-2 (n >= 3) Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a, b]. InputThe input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a = b = 0. Otherwise, a <= b <= 10^100. The numbers a and b are given with no superfluous leading zeros.OutputFor each test case output on a single line the number of Fibonacci numbers fi with a <= fi <= b. Sample Input10 1001234567890 98765432100 0Sample Output54
题目大意：给你两个数a和b，求a和b之间有几个斐波那契数，包括a和b
解题思路：因为本题是一个很大的数，所以就用字符串，然后再加一个二分就好了。。。。
请看代码：/*2015 - 8 - 13 下午Author: ITAK今日的我要超越昨日的我，明日的我要胜过今日的我，以创作出更好的代码为目标，不断地超越自己。*/#include#include #include using namespace std;const int N = 105;char data[1000][N+2];char a[N+2],b[N+2];int cmp(char *s1, char *s2){ for(int i=0; i<=N; i++) { if(i == N) return s1[i] - s2[i]; if(s1[i] != s2[i]) return s1[i] - s2[i]; }}int Find_up(int i, char *x){ int low=0, high=i; while(low <= high) { int mid = (high+low)/2; int val = cmp(x, data[mid]); if(val > 0) low = mid + 1; if(val == 0) return mid - 1; if(val < 0) high = mid - 1; } return high;}int Find_down(int i, char *x){ int low=0, high=i; while(low <= high) { int mid = (high+low)/2; int val = cmp(x, data[mid]); if(val > 0) low = mid + 1; if(val == 0) return mid + 1; if(val < 0) high = mid - 1; } return low;}int main(){ data[0][105] = 1; data[1][105] = 2; int i = 2; int p = 105; while(data[i-1][5] <= 1) { for(int j=105; j>=p; j--) data[i][j] = data[i-1][j] + data[i-2][j]; for(int j=105; j>=p; j--) { int c = data[i][j]/10; if(c > 0) { data[i][j] %= 10; data[i][j-1] += c; } } if(data[i][p-1] > 0) p--; i++; } while(~scanf("%s%s",a,b)) { if(a[0]=='0' && b[0]=='0') break; int lena = strlen(a)-1; int lenb = strlen(b)-1; int k; for(int d=lena,k=N; d>=0; d--,k--) { a[k] = a[d] - '0'; a[d] = 0; } for(int d=lenb,k=N; d>=0; d--,k--) { b[k] = b[d] - '0'; b[d] = 0; } int L = Find_up(i-1, a); int R = Find_down(i-1, b); printf("%d\n",R-L-1); memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); } return 0;}
转载地址：http://pqovx.baihongyu.com/