2

我最近偶然发现了这个 Project Euler Problem #25：

第 12 项 F12 是第一个包含三位数字的项。

斐波那契数列中包含 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达到second极限unsigned long。如果您想要一个蛮力解决方案 - 考虑使用biginteger 库之类的东西或自己编写一个。

于 2014-02-13T08:35:58.670 回答