2

私は最近、この Project Euler Problem #25 に出くわしました:

第 12 項 F12 は、3 桁を含む最初の項です。

フィボナッチ数列で最初に 1000 桁になる項は?

私は C++98 を知っているだけで、他のプログラミング言語は知りません。私はそれを解決しようとし、c++ 11 のサポートを得るために変更を加えました。

働く：

#include <iostream>
#include<cstdio>
long len(long);              //finding length
int main()
{
    /* Ques: What is the first term in fibonacci series to contain 1000 digits? */
    
    int ctr=2;
    unsigned long first, second, third, n;
    first=1;
    second=1;
    std::cout<<"\t **Project EULER Question 25**\n\n";
    for(int i=2;;++i)
    {
        third=first+second;
        //  cout<<" "<<third;
        int x=len(third);
        //  cout<<" Length: "<<x;
        //  cout<<"\n";

        first=second;
        second=third;
        ctr++;
            if(x>1000)        // for small values, program works properly
        {
            std::cout<< " THE ANSWER: "<< ctr;
            system("pause");
            break;
        }

    }
}

long len(long num)
{


    int ctr=1;

    while(num!=0)
    {
        num=num/10;
                if(num!=0)
            {
                ctr++;
            }
    }

    return(ctr);
}

これが力ずくであることはわかっていますが、答えを得るためにもっと効率的にすることはできますか?

どんな助けでも大歓迎です。

編集：

PaulMcKenzieが提案した Binet の式を使用し、次のように実装します。

#define phi (1+sqrt(5))/2
int main(void)
{
   float n= ((999 + (1/2)*log10(5))/(log10(phi)));     //Line 1
   cout<<"Number is  : "<<n;
   return 0;
}

出力: 4780.187012

上記の 1 行目を次のように変更します。

float n= ((999 + log10(sqrt(5)))/(log10(phi)));

出力: 4781.859375

ここで考えられるエラーは何ですか？

4

1 に答える 1

2

unsigned long単純に 1000 桁の数字を保持することはできません。したがって、制限に達するfirstと、コードでオーバーフローが発生します。ブルート フォース ソリューションが必要な場合は、biginteger ライブラリなどの使用を検討するか、自分で作成してください。secondunsigned long

于 2014-02-13T08:35:58.670 に答える