时间戳

首页 > 解决方案 > 找到适合 int 的最大斐波那契数的最快方法是什么？

c++ - 找到适合 int 的最大斐波那契数的最快方法是什么？

问题描述

我承认这个问题有点学术。但是，我相信该解决方案显示出对（C++）数字的一些洞察力。

请注意，第 N 个斐波那契数可以用递归计算

int Fibonacci(int N)
{
    if (N==1 || N==2) {
        return 1;
    }
    return Fibonacci(N-1) + Fibonacci(N-2);
}

对于这个问题，上述蛮力方法不是答案。这是因为第 N 个斐波那契数可以通过以下方式非递归计算：

long int Fibonacci(int N)
{
    double num1 = pow((1+sqrt(5))/2.0,N);
    double num2 = pow((1-sqrt(5))/2.0,N);

    return (num1-num2)/sqrt(5);
}

标签： c++algorithmnumeric

解决方案

方法1（不是最快的）：

使用非递归方法计算第 N 个斐波那契数可以找到适合 int 的最大斐波那契数，代码如下：

#include <iostream>
#include <limits.h>
#include <math.h>
#include <chrono>

long int Fibonacci(int n)
{
    double num1 = pow((1+sqrt(5))/2.0,n);
    double num2 = pow((1-sqrt(5))/2.0,n);

    return (num1-num2)/sqrt(5);
}
 
int main()
{
    auto start = std::chrono::system_clock::now();

    int IndexMax = 1;
    while (Fibonacci(IndexMax)<INT_MAX) 
    {
        ++IndexMax;
    }
    --IndexMax;
    auto end = std::chrono::system_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    std::cout << "IndexMax = " << IndexMax << std::endl;
    std::cout << "Fibonacci_two(IndexMax): " << Fibonacci(IndexMax) << std::endl;
    std::cout << "calculation time: " << elapsed.count() << " microseconds" << std::endl;
}

可以在线运行方法一的代码，看到如下输出：

IndexMax = 46
Fibonacci_two(IndexMax): 1836311903
calculation time: 33 microseconds

但是还有一种更快的方法：

方法二：

根据维基百科，可以反转第 N 个斐波那契数的显式公式。有了这个技巧，我们可以实现一个更快的方法：

#include <iostream>
#include <limits.h>
#include <math.h>
#include <chrono>

long int Fibonacci(int n)
{
    double num1 = pow((1+sqrt(5))/2.0,n);
    double num2 = pow((1-sqrt(5))/2.0,n);

    return (num1-num2)/sqrt(5);
}

double Fibonacci_invert(double Fn)
{
    double num1 = Fn*sqrt(5.0);
    double num2 = sqrt(5.0*Fn*Fn+4.0);
    double phi = (1.0 + sqrt(5.0))/2.0;

    return round(log((num1+num2)/2.0)/log(phi));
}

int main()
{
    auto start = std::chrono::system_clock::now();

    int IndexMax = Fibonacci_invert(INT_MAX);
    int FibonacciMax = Fibonacci(IndexMax);

    auto end = std::chrono::system_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    std::cout << "IndexMax: " << IndexMax << std::endl;
    std::cout << "FibonacciMax: " << FibonacciMax << std::endl;
    std::cout << "calculation time: " << elapsed.count() << " microseconds" << std::endl;
}

多亏了Eric Postpischil，需要注意的Fibonacci_Invert是，通常不是找到不大于其参数的最大斐波那契数的正确函数。

您可以在线运行方法 2 的代码以查看以下输出：

IndexMax: 46
FibonacciMax: 1836311903
calculation time: 23 microseconds

推荐阅读