## Thursday, October 28, 2010

### poj_2413_HowmanyFibs.cpp

poj2413, uva10183, spoj00536,

## Problem:

How many Fibs?
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7765 Accepted: 2860
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<=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 100
1234567890 9876543210
0 0```
Sample Output
```5
4```
Source
Ulm Local 2000

## Source Code:

#include<stdio.h>
#include<string.h>

int fib[500][101] =
{ 0 };
char start[102], end[102];
int start_num[101], end_num[101];
int count;

void Add(int A[101], int B[101], int C[101])
{
int length, i;
for (length = 100; length >= 0 && B[length] == 0; length--)
;
for (i = 0; i <= length; i++)
C[i] = A[i] + B[i];
for (i = 0; i <= length; i++)
{
C[i + 1] += C[i] / 10;
C[i] = C[i] % 10;
}
}

int Cmp(int A[101], int B[101])
{
int i;
for (i = 100; i >= 0 && A[i] == B[i]; i--)
;
if (i == -1)
return 0; //Equal;
else if (A[i] > B[i])
return 1;
else
return -1;
}

void init_fib()
{
int i;
fib[0][0] = 1;
fib[1][0] = 2;
for (i = 2; i < 500; i++)
Add(fib[i - 2], fib[i - 1], fib[i]);
}

void init()
{
int i;
int len1 = strlen(start);
int len2 = strlen(end);
for (i = 0; i < 101; i++)
start_num[i] = end_num[i] = 0;
for (i = 0; i < len1; i++)
start_num[i] = start[len1 - i - 1] - '0';
for (i = 0; i < len2; i++)
end_num[i] = end[len2 - i - 1] - '0';
}

void CalPrint()
{
int i, j;
count = 0;
for (i = 0; i < 500 && Cmp(fib[i], start_num) == -1; i++)
;
if (Cmp(fib[i], start_num) == 0)
{
count++;
j = i + 1;
}
else
j = i;
for (; j < 500 && Cmp(fib[j], end_num) <= 0; j++, count++)
;
printf("%d\n", count);
}

int main()
{
init_fib();
scanf("%s %s", start, end);
while (strcmp(start, "0") || strcmp(end, "0"))
{
init();
CalPrint();
scanf("%s %s", start, end);
}
return 0;
}