杭电 1316 How Many Fibs?

Problem 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 100
1234567890 9876543210
0 0

Sample Output

5
4

Source

University of Ulm Local Contest 2000

Recommend

Eddy

此题与大菲波数那题有些类似，我在处理的时候，都是先用一个二维数组存储大菲波数。不同的是，本题需要对用个用数组存储的所谓大数进行比较，需要写一个大数比较的函数，通过该函数的返回值来判断两个大数的大小，以下是代码：

View Code

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 
  5 int fib[700][105];
  6 
  7 void add( int *num1, int *num2, int *num3 )
  8 {
  9      int i;
 10      memset(num3, 0, 105 * sizeof(int));
 11      for( i = 0; i < 105; i++ )
 12      {
 13           num3[i] += (num1[i] + num2[i]);
 14           if( num3[i] >= 10 )
 15           {
 16               num3[i+1]++;
 17               num3[i] = num3[i] % 10;
 18           } 
 19      }
 20 }
 21 int compare( int *num1, int *num2 )
 22 {
 23     //for( i = 104; i >= 0; i-- )
 24     int i, len1, len2, temp;
 25     for( i = 104; i >= 0; i-- )
 26          if( num1[i] != 0 )
 27              break;
 28     len1 = i;
 29     for( i = 104; i >= 0; i-- )
 30          if( num2[i] != 0 )
 31              break;
 32     len2 = i;
 33     if( len1 > len2 )
 34         return 1;
 35     else if( len1 == len2 )
 36     {
 37          temp = len1;
 38          while( (num1[temp] == num2[temp])&&( temp != -1 ) )
 39                 temp--;
 40          if( temp == -1 )
 41              return 0;
 42          else 
 43               return (num1[temp]- num2[temp]);
 44     }
 45     else
 46          return -1;
 47 }
 48 
 49 int main(int argc, char *argv[])
 50 {
 51     int i, len1, len2, cnt, left, right, n;
 52     char s1[105], s2[105];
 53     int  num1[105], num2[105];
 54     memset(fib[0], 0, 110 * sizeof(int));
 55     memset(fib[1], 0, 110 * sizeof(int));
 56     fib[0][0] = 1;
 57     fib[1][0] = 1;
 58     for( i = 2; i < 700; i++ )
 59          add(fib[i-2], fib[i-1], fib[i]);
 60     while( scanf( "%s %s", s1, s2 ) != EOF )
 61     {
 62            //printf( "%s %s\n", s1, s2 );
 63            if( (strcmp( s1, "0" )==0)&&(strcmp( s2, "0" )==0) )
 64                break;
 65            len1 = strlen(s1);
 66            len2 = strlen(s2);
 67            //printf( "%d %d\n", len1, len2 );
 68            memset(num1, 0, 105 * sizeof(int));
 69            memset(num2, 0, 105 * sizeof(int));
 70            cnt = 0;
 71            for( i = len1 - 1; i >= 0; i-- )
 72                 num1[cnt++] = s1[i] - '0';
 73            /*for( i = 0; i < cnt; i++ )
 74                 printf( "%d", num1[i] );
 75            printf( "\n" );*/
 76            cnt = 0;
 77            for( i = len2 - 1; i >= 0; i-- )
 78                 num2[cnt++] = s2[i] - '0';
 79             /*for( i = 0; i < cnt; i++ )
 80                 printf( "%d", num2[i] );
 81            printf( "\n" );*/
 82            left = -1;
 83            for( i = 1; i < 700; i++ )
 84            {
 85                 if( (compare( fib[i], num1 ) >= 0)&&( left == -1 ) )
 86                     left = i;
 87                 if( compare( fib[i], num2 ) > 0 )
 88                 {
 89                     right = i;
 90                     break;
 91                 }
 92            }
 93            //printf( "%d %d\n", left, right );
 94            printf( "%d\n", right - left );   
 95            /*while( scanf( "%d", &n ) != EOF )
 96            {
 97                   for( i = 104; i >= 0; i-- )
 98                        if( fib[n][i] != 0 )
 99                            break;
100                   for( ; i >= 0; i-- )
101                        printf( "%d", fib[n][i] );
102                   printf( "\n" );
103            }*/
104     }
105   //system("PAUSE");    
106   return 0;
107 }