我的代码出了什么问题?第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

好的，我们讨论的是斐波那契数和记忆。

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

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

使用Binet的公式，您可以计算出第93个Fibonacci数是最后一个适合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，。。。并返回具有相应Fibonacci数的CCD_ 5。

我们知道我们最多可以存储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的编译时CCD_ 6，包含所有Fibonacci数。如果我们需要第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

Answer 2

如果n<=1(这也应该是你比较的情况(。对于Fibonacci，您只需要为第一种情况返回n。

我在这里重写了你的代码

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