本文共 1364 字，大约阅读时间需要 4 分钟。
| Time Limit: 1000MS | | Memory Limit: 65536K |
| Total Submissions: 10748 | | Accepted: 3982 |
Description
Recall 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].
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<=10
100. 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
解题思路：
用一个字符串数组记录位数小于101的所有fibs，然后对于给定的a，b，求出满足条件的个数；
#include #include #include using namespace std;char fibs[10005][102];void add(int n){ int len_a=strlen(fibs[n-1]),len_b=strlen(fibs[n-2]); int p=len_a-1,q=len_b-1; int a[102],left=0; for (int i=0;i<102;i++){ a[i]=left; if (p>=0) a[i]+=fibs[n-1][p--]-'0'; if (q>=0) a[i]+=fibs[n-2][q--]-'0'; left=a[i]/10; a[i]%=10; } int i; for (i=101;i>=0;i--){ if (a[i]!=0) break; } int k=0; while (i>=0){ fibs[n][k++]=a[i--]+'0'; } fibs[n][k]=0;}bool cmp(char *a,char *b){ int len_a=strlen(a),len_b=strlen(b); if (len_a>len_b) return true; if (len_a b[n]-'0') return true; if (a[n]-'0'
转载地址：http://kfbqb.baihongyu.com/