<center>

</center>
<center>

问题 C: 来简单地数个数

时间限制: 1 Sec   内存限制: 64 MB
提交: 825   解决: 266
[ 提交][ 状态][ 讨论版] </center>

题目描述

这是一个斐波那契数列：
f1 = 1 
f2 = 2 
fn = fn-1 + fn-2     (n>=3)
蔡老板想知道，给你两个数a、b，你能否求出在区间[a,b]里有多少个斐波那契数。

输入

多组数据输入。一行为一组输入数据，包括两个非负整数a、b（a <= b <= 10^100），当a=b=0时输入终止。

输出

对每组输入，输出单独一行，包含一个整数表示区间[a,b]里的斐波那契数个数。

样例输入

10 100
1234567890 9876543210
0 0

样例输出

5
4

提示

#include<iostream>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include <cstdlib>
using namespace std;
 
#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4
 
class BigNum
{
    private:
    int a[500];
    int len;
    public:
    BigNum(){ len = 1;memset(a,0,sizeof(a)); }
    BigNum(const int);
    BigNum(const char*);
    BigNum(const BigNum &);
    BigNum &operator=(const BigNum &);
     
    friend istream& operator>>(istream&,  BigNum&);
    friend ostream& operator<<(ostream&,  BigNum&);
     
    BigNum operator+(const BigNum &) const;
    bool   operator>(const BigNum & T)const;
    void print();
};
BigNum::BigNum(const int b)     //将一个int类型的变量转化为大数
{
    int c,d = b;
    len = 0;
    memset(a,0,sizeof(a));
    while(d > MAXN)
    {
        c = d - (d / (MAXN + 1)) * (MAXN + 1);
        d = d / (MAXN + 1);
        a[len++] = c;
    }
    a[len++] = d;
}
BigNum::BigNum(const char*s)     //将一个字符串类型的变量转化为大数
{
    int t,k,index,l,i;
    memset(a,0,sizeof(a));
    l=strlen(s);
    len=l/DLEN;
    if(l%DLEN)
    len++;
    index=0;
    for(i=l-1;i>=0;i-=DLEN)
    {
        t=0;
        k=i-DLEN+1;
        if(k<0)
        k=0;
        for(int j=k;j<=i;j++)
        t=t*10+s[j]-'0';
        a[index++]=t;
    }
}
BigNum::BigNum(const BigNum & T) : len(T.len)  //拷贝构造函数
{
    int i;
    memset(a,0,sizeof(a));
    for(i = 0 ; i < len ; i++)
    a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum & n)   //重载赋值运算符，大数之间进行赋值运算
{
    int i;
    len = n.len;
    memset(a,0,sizeof(a));
    for(i = 0 ; i < len ; i++)
    a[i] = n.a[i];
    return *this;
}
 
 
BigNum BigNum::operator+(const BigNum & T) const   //两个大数之间的相加运算
{
    BigNum t(*this);
    int i,big;      //位数
    big = T.len > len ? T.len : len;
    for(i = 0 ; i < big ; i++)
    {
        t.a[i] +=T.a[i];
        if(t.a[i] > MAXN)
        {
            t.a[i + 1]++;
            t.a[i] -=MAXN+1;
        }
    }
    if(t.a[big] != 0)
    t.len = big + 1;
    else
    t.len = big;
    return t;
}
 
bool BigNum::operator>(const BigNum & T) const   //大数和另一个大数的大小比较
{ 
    int ln; 
    if(len > T.len)
    return true; 
    else if(len == T.len)
    { 
        ln = len - 1; 
        while(a[ln] == T.a[ln] && ln >= 0)
        ln--;
        if(ln<0)
        return true;
        if(ln >= 0 && a[ln] > T.a[ln])
        return true;
        else
        return false;
    } 
    else
    return false; 
}
 
void BigNum::print()    //输出大数
{
    int i;
    cout << a[len - 1];
    for(i = len - 2 ; i >= 0 ; i--)
    {
        cout.width(DLEN);
        cout.fill('0');
        cout << a[i];
    } 
    cout << endl;
}
int main(void)
{
    char a1[105];
    char b1[105];
    BigNum a,b,t1,t2,t;
    t1 = 1;t2 = 2;
    int cnt = 0;
    while(scanf("%s%s",a1,b1)!=EOF){
//        cout<<a1<<endl;
//        cout<<b1<<endl;
        t1 = 1;t2 = 2;
        cnt = 0;
        a = a1;
        b = b1;
//        cout<<b1<<endl;
//        b.print();
        if(BigNum(0)>a&&BigNum(0)>b)
        break;
        while(b>t1){
            if(t1>a){
                cnt++;
            }
            t = t1+t2;
            t1 = t2;
            t2 = t;
        }
        printf("%d\n",cnt);
    }
    return 0;
}