时间戳

首页 > 解决方案 > 我的代码有什么问题？第 N 个斐波那契数

c++ - 我的代码有什么问题？第 N 个斐波那契数

问题描述

  public:
  
    long long int lookup[100]={-1};
    long long int nthFibonacci(long long int n){
        // code here
    
        if(lookup[n]==-1){
            if(n<=1) lookup[n]=n;
            else lookup[n]=nthFibonacci(n-1)+nthFibonacci(n-2);
        }
        return lookup[n];
    }
};

这是我的代码。它为输入 2 提供输出 0，而不是应该提供 1。

标签： c++recursiondynamicdynamic-programmingfibonacci

解决方案

好的，我们正在谈论斐波那契数字和记忆。

超快速和紧凑的解决方案是使用编译时记忆。因此，在编译期间预先计算适合 64 位无符号位的所有可能值。

斐波那契数列的一个重要特性是值呈指数级增长。因此，所有现有的整数数据类型构建都会很快溢出。

使用比内特的公式，您可以计算出第 93 个斐波那契数是最后一个适合 64 位无符号值的数。

在编译期间计算 93 个值是一项非常简单且快速的任务。

那么，该怎么做呢？

我们首先将计算斐波那契数的默认方法定义为constexpr函数。迭代和非递归。

// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) noexcept {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 1 };

    // calculating Fibonacci value 
    while (index--) {
        // get next value of Fibonacci sequence 
        unsigned long long f3 = f2 + f1;
        // Move to next number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}

这样，斐波那契数可以在编译时轻松计算。std::array然后，我们用所有斐波那契数填充 a 。我们还使用 aconstexpr并使其成为带有可变参数包的模板。

我们使用std::integer_sequence为索引 0、1、2、3、4、5、... 创建一个斐波那契数。

这很简单，并不复杂：

template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};

该函数将输入一个整数序列 0,1,2,3,4,... 并返回std::array<unsigned long long, ...>具有相应斐波那契数的 a。

我们知道我们最多可以存储 93 个值。因此我们创建了一个下一个函数，它将使用整数序列 1,2,3,4,...,92,93 调用上述函数，如下所示：

constexpr auto generateArray() noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

而现在，终于，

constexpr auto FIB = generateArray();

将为我们提供一个名为 FIB 的编译时间std::array<unsigned long long, 93>，其中包含所有斐波那契数。如果我们需要第 i 个斐波那契数，那么我们可以简单地写FIB[i]. 运行时不会进行计算。

我认为没有更快或更简单的方法来计算第 n 个斐波那契数。

请参阅下面的完整程序：

#include <iostream>
#include <array>
#include <utility>
// ----------------------------------------------------------------------
// All the following will be done during compile time

// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 1 };

    // calculating Fibonacci value 
    while (index--) {
        // get next value of Fibonacci sequence 
        unsigned long long f3 = f2 + f1;
        // Move to next number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}
// We will automatically build an array of Fibonacci numberscompile time
// Generate a std::array with n elements 
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};

// Max index for Fibonaccis that for in an 64bit unsigned value (Binets formula)
constexpr size_t MaxIndexFor64BitValue = 93;

// Generate the required number of elements
constexpr auto generateArray()noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

// This is an constexpr array of all Fibonacci numbers
constexpr auto FIB = generateArray();
// ----------------------------------------------------------------------

// Test
int main() {

    // Print all possible Fibonacci numbers
    for (size_t i{}; i < MaxIndexFor64BitValue; ++i)

        std::cout << i << "\t--> " << FIB[i] << '\n';

    return 0;
}

使用 Microsoft Visual Studio Community 2019 版本 16.8.2 开发和测试。

另外用 clang11.0 和 gcc10.2 编译和测试

语言：C++17

推荐阅读