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

Question

  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。

Answer 1

如果 n <= 1，则无需执行 lookup[n] = n（您比较的情况也应该如此）。对于斐波那契数列，您只需要 return n 用于第一种情况。

我在这里重写了你的代码

 long long int nthFibonacci(long long int n)
    {
    if (n <= 1)
       return n;
    return nthFibonacci(n-1) + nthFibonacci(n-2);
    }

Answer 2

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

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

Fibonacci 数列的一个重要属性是值呈指数级增长。因此，所有现有的整数数据类型都会很快溢出。

使用 Binet's formula 您可以计算出第 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。我们还使用 constexpr 并使其成为带有可变参数包的模板。

我们使用 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,... 和 return a std::array<unsigned long long, ...> 以及相应的斐波那契数列。

我们知道我们最多可以存储 93 个值。因此我们创建了一个 next 函数，它将使用整数序列 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

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

What is wrong with my code? Nth Fibonacci Number

c++

recursion

dynamic

dynamic-programming

fibonacci