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].

 

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.

 

For each test case output on a single line the number of Fibonacci numbers fi with a <= fi <= b.

 

 

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

int a[][];

char str[][];

int main()

{

    char m[],n[];

    int i,j,sum;

    memset(a,,sizeof(a));//大数斐波那契，主要是了解思想

    a[][]=;

    a[][]=;

    a[][]=;

    for (i=;i<=;i++)

    {

        for (j=;j<=;j++)

        {

            a[i][j]=a[i][j]+a[i-][j]+a[i-][j];

            if (a[i][j]>)

            {

                a[i][j+]=a[i][j]/;

                a[i][j]=a[i][j]%;

            }

        }

    }

    int flag=,k;

    for(int i=;i<=;i++)

    {

        flag=;

        k=;

        for(int j=;j>=;j--)

        {

            if(flag||a[i][j])

            {

                flag=;

                str[i][k]=a[i][j]+'';

                k++;

            }

        }

        str[i][k]='\0';

    }

    flag=;

    /*for(i=100;i>=0;i--)

    {

        if(flag||a[100][i])

        {

            flag=1;

            printf("%d",a[100][i]);

        }

    }*/

    /*for(int i=40;i<=50;i++)

    printf("%s\n",str[i]);*/

    int l1,l2;

    while(scanf("%s%s",n,m)!=EOF)

    {

        sum=;

         l1=strlen(n);

         l2=strlen(m);

        if(n[]==''&&m[]=='') break;

        for(int i=;i<=;i++)

        {

            if((strlen(str[i])>l1&&strlen(str[i])<l2))//如果这个数的长度在范围之（a,b)长度之间，则这个数一定属于（a,b);

            {

                 sum++;

            }

            else if(l1==l2&&strlen(str[i])==l1&&strcmp(str[i],n)>=&&strlen(str[i])==l2&&strcmp(str[i],m)<=)//如果（a,b)两个数长度一样,则比较他们在字典中的大小。

            {

                  sum++;

            }

            else if(l1!=l2&&strlen(str[i])==l1&&strcmp(str[i],n)>=)

            {

                sum++;

            }

            else if(l1!=l2&&strlen(str[i])==l2&&strcmp(str[i],m)<=)

            {

                sum++;

            }

        }

        printf("%d\n",sum);;

    }

    return ;

}