poj 2413 How many Fibs? 大数累加模板+字符串模拟大数比较大小

发布时间：2020-12-14 03:51:29 所属栏目：大数据来源：网络整理

导读：How many Fibs? Time Limit: ?1000MS ? Memory Limit: ?65536K Total Submissions: ?10202 ? Accepted: ?3789 Description Recall the definition of the Fibonacci numbers:? f1 := 1 f2 := 2 fn := f n-1 + f n-2 (n=3) Given two numbers a and b,calcula

How many Fibs?

Time Limit:?1000MS	?	Memory Limit:?65536K
Total Submissions:?10202	?	Accepted:?3789

Description

Recall the definition of the Fibonacci numbers:?

f1 := 1 

f2 := 2 

fn := f_n-1 + f_n-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 ¹⁰⁰. 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

这个问题还是很有意思的，我们要求出在某个范围内的fibs,我一开始以为是要找规律，不过fibs真心想不到什么规律可循，应该是要求出某个范围内的数据出来，所以之前先打表求出所有2000内的数，我估计2000内的数可以大于10^100，

估计应该是可以的，然后我们进行比较就可以了，就是大数模板+字符串模拟数字比较大小，足以做出此题目了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
char s[10000][1000];
void revision(char s[])
{
    char b[1000];
    int i,j;
    int l=strlen(s);
    j=0;
    for(i=l-1;i>=0;i--)
    {
        b[j++]=s[i];
    }
    b[j]='';
    strcpy(s,b);


}
void sum(char a[],char b[],char s[])
{
    char c[1000];
    char d[1000];
    char e[1000];
    int i,j;
   /* memset(c,'',sizeof(c));
    memset(d,sizeof(d));
    memset(e,sizeof(e));*/
    for(i=0;i<1000;i++)
    {
        c[i]=d[i]=e[i]='';
    }
    strcpy(c,a);
    strcpy(d,b);
    int la=strlen(c);
    int lb=strlen(d);
    revision(c);
    revision(d);
    for(i=0;i<la;i++)
    {
        c[i]=c[i]-'0';
    }
    for(i=0;i<lb;i++)
    {
        d[i]=d[i]-'0';
    }
    int lc=la>lb?la:lb;
    int jin=0;
    int sh;
    for(i=0;i<lc;i++)
    {
        sh=c[i]+d[i]+jin;
        e[i]=sh%10;
        jin=sh/10;
    }
    if(jin==1)
    {
     e[i]=jin;
     i++;
    }
    int ll=i;
    for(i=0;i<ll;i++)
    {
        e[i]=e[i]+'0';
    }
    e[ll]='';
    revision(e);
    strcpy(s,e);
}
int compare(char a[],char b[])
{
    int la=strlen(a);
    int lb=strlen(b);
    if(la>lb)
    return 1;
    else
    if(la<lb)
    return -1;
    else
    return  strcmp(a,b);

}
int main()
{

   int i,j,k;
   strcpy(s[1],"1");
   strcpy(s[2],"2");
   char a[1000];
   char b[1000];
   for(i=3;i<=2000;i++)
   {
       sum(s[i-1],s[i-2],s[i]);
   }
   //printf("fhdjkfs");
   /* for(i=1;i<=7;i++)
    {
        printf("%s  ",s[i]);
    }
    */
    //for(i=1;i<=10;i++)
    //printf("%d i   %sn",i,s[i]);
    while(scanf("%s %s",a,b),strcmp(a,"0")!=0||strcmp(b,"0")!=0)
    {
        int num=0;
        for(i=1;i<=2000;i++)
        {
            if(compare(a,s[i])<=0)
            {
                if(compare(b,s[i])>=0)
                {
                   num++;
                }
                else
                break;
            }

        }

        printf("%dn",num);
    }




  return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!