二分查找+大整数加法——Poj 2413 How many Fibs?
Description
Recall the definition of the Fibonacci numbers:f1 := 1 f2 := 2 fn := fn-1 + fn-2 (n>=3)
Input
The 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<=10100. The numbers a and b are given with no superfluous leading zeros.Output
For each test case output on a single line the number of Fibonacci numbers fi with a<=fi<=b.Sample Input
10 1001234567890 98765432100 0
Sample Output
54
思路：
首先算出前480个斐波那契数（第480个斐波那契数的位数101位，满足题目要求的数据范围），然后使用二分查找确定a和b在斐波那契数列的位置，两位置做差，即为中间包含的斐波那契数个数，注意a和b也是斐波那契数时，输出结果特殊处理下。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define MAXN500#define MAXLEN110#define LAST MAXLEN-2char store[MAXN][MAXLEN];//存储MAXN个斐波那契数char *Fibs[MAXN];//存储每个斐波那契数的首地址//大整数相加char* IntAddition(char *a, char *b, char *sum){int i, j, k, first;//从末位开始，把a与b对应位的和存入sum中，暂不处理进位for (i = strlen(a)-1, j = LAST; i >= 0; i--, j--){sum[j] = a[i] - '0';}for (i = strlen(b)-1, k = LAST; i >= 0; i--, k--){sum[k] += b[i] - '0';}//获取sum中结果的首位位置first = j < k ? j : k;//处理进位for (i = LAST; i >= first; i--){sum[i-1] += sum[i] / 10;sum[i] = sum[i] % 10 + '0';}//去除前导'0'while (sum[first] == '0' && first < LAST){first++;}//返回sum的首位地址return &sum[first];}//计算485个斐波那契数void Fibonacci(void){memset(store, 0, sizeof(store));memset(Fibs, NULL, sizeof(Fibs));strcpy(store[1], "1");strcpy(store[2], "2");Fibs[1] = store[1];Fibs[2] = store[2];int i;for (i = 3; i < 485; i++){Fibs[i] = IntAddition(Fibs[i-2], Fibs[i-1], store[i]);}}int Compare(char *a, char *b){int lenA = strlen(a);int lenB = strlen(b);if (lenA == lenB){return strcmp(a, b);}return lenA > lenB ? 1 : -1;}int BinarySearch(char *num, bool &flag){int low = 1;int high = 480;while (low <= high){int mid = (low + high) / 2;int res = Compare(num, Fibs[mid]);if (res == 0){flag = true; return mid;}else if (res < 0){high = mid - 1;}else{low = mid + 1;}}return low;}int main(void){Fibonacci();char a[MAXLEN], b[MAXLEN];while (scanf("%s %s", a, b) != EOF){if (strcmp(a, "0") == 0 && strcmp(b, "0") == 0){break;}bool flagLeft = false;bool flagRight = false;//分别找出a和b在斐波那契数中的位置//当查找的数不是斐波那契数时，二分查找返回的位置是第一个比它大的斐波那契数的位置int left = BinarySearch(a, flagLeft);int right = BinarySearch(b, flagRight);//当b也是斐波那契数时，要把两位置的差值加1if (flagRight){printf("%d\n", right - left + 1);}else{printf("%d\n", right - left);}}return 0;}