首页 > 代码库 > 杭电1316

杭电1316

2024-07-05 16:02:10   230人阅读

How Many Fibs?
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3804    Accepted Submission(s): 1498 

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
const int maxn=500;
const int base=1000000;
const int INF=99999999;
const int MIN=-INF;
char a[maxn][500];
char* add(char*a,char*b)//大数加法
{
    int lena=strlen(a);
    int lenb=strlen(b);
    int i,j,k;
    char c[500];
    if(lena<lenb)
    {
        strcpy(c,a);
        strcpy(a,b);
        strcpy(b,c);
    }
    int A[500]= {0},B[500]= {0};
    for(j=0,i=lena-1; i>=0; i--,j++)
        A[j]=a[i]-‘0‘;
    int lenA=j;
    for(i=lenb-1,j=0; i>=0; i--,j++)
        B[j]=b[i]-‘0‘;
    int lenB=j;
    for(i=0; i<lenB; i++)
        A[i]+=B[i];
    for(i=0; i<500; i++)
    {
        if(A[i]>9)
        {
            A[i+1]+=A[i]/10;
            A[i]%=10;
        }
    }
    for(i=500-1; i>=0; i--)if(A[i]!=0)break;
    for(j=0; i>=0; i--)
        c[j++]=A[i]+‘0‘;
    c[j]=‘\0‘;
    return c;
}
int comper(char*a,char*b)//自定义比较函数 相同是0 大于是1 小于是-1
{
    int lena=strlen(a);
    int lenb=strlen(b);
    if(lena>lenb)
        return 1;
    else if(lena<lenb)
        return -1;
    else if(lena==lenb)
    {
        for(int i=0; i<lena; i++)
            if(a[i]<b[i])
                return -1;
            else if(a[i]>b[i])
                return 1;
    }
    return 0;


}
int main()
{
    int n,m,i,j,k,t;
    a[1][0]=‘1‘;
    a[2][0]=‘2‘;
    for(i=3; i<=maxn; i++)
    {
        strcpy(a[i],add(a[i-1],a[i-2]));
    }
    //for(i=1;i<50;i++)
    //  cout<<a[i]<<endl;

    char a1[maxn],b1[maxn];
    while(cin>>a1>>b1)
    {
        int lena1=strlen(a1);
        int lenb1=strlen(b1);
        if(lena1==1&&lenb1==1&&a1[0]==‘0‘&&b1[0]==‘0‘)return 0;
        int cnt=0;
        for(i=1; i<maxn; i++)
        {
            if(comper(a[i],a1)>=0&&comper(a[i],b1)<=0)
                cnt++;
        }
        cout<<cnt<<endl;
    }

    return 0;
}






























        

            
                
                  
                
                

                    联系

                    我们