poj 2413 How many Fibs? - c++编程基础

How many Fibs?

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 10748		Accepted: 3982

Description

Recall the definition of the Fibonacci numbers:

f1 := 1 

f2 := 2 

fn := f_n-1 + f_n-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 ¹⁰⁰. 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 100
1234567890 9876543210
0 0

Sample Output

5
4

解题思路：

用一个字符串数组记录位数小于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'