时间戳

首页 > 解决方案 > 我的代码 C++ Fibo 系列有什么问题

c++ - 我的代码 C++ Fibo 系列有什么问题

问题描述

#include <iostream>

using namespace std;

int main()
{
    int num1 = 0;
    int num2 = 1;
    int num_temp;
    int num_next = 1;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        cout << num_next << "  ";
        num_next = num1 + num2;
        num1 = num2;
        num_temp = num2;
        num2 = num_next - num1;
        num1 = num_temp;
    }
    return 0;
}

预期：对于 n=9

0, 1, 1, 2, 3, 5, 8, 13, 21

实际的：

1 1 1 1 1 1 1 1 1

我必须输出第一个“n”斐波那契数，但是我认为逻辑上存在一些问题。我不知道我做错了什么。前 3 或 4 个元素是正确的，但随后出现问题......

标签： c++

解决方案

我将给出一个可能对其他用户有所帮助的附加答案。

基本信息是：不需要在运行时进行任何计算！一切都可以在编译时完成。然后，可以使用简单的查找机制。这将是最有效和最快的解决方案。

使用比内特的公式，我们可以计算出只有极少数的斐波那契数可以适合 C++unsigned long long数据类型，而 C++ 数据类型现在通常在 2021 年达到 64 位，是“最大”的可用数据类型。回旋处 93。如今，这个数字非常低。

借助现代 C++ 17（及更高版本）功能，我们可以在编译时轻松地为 64 位数据类型创建std::array所有斐波那契数。因为如上所述，只有 93 个数字。

因此，我们将只为查找数组花费 93*8= 744 BYTE的非运行时内存。这实在是微不足道。

我们可以很容易地通过写得到斐波那契数 n FIB[n]。

而且，如果我们想知道，如果一个数字是斐波那契，那么我们用它std::binary_search来查找值。因此，整个功能将是：

bool isFib(const unsigned long long numberToBeChecked) {
    return std::binary_search(FIB.begin(), FIB.end(), numberToBeChecked);
}

FIB 是一个编译时间，constexpr std::array. 那么，如何构建该数组？

我们首先将计算斐波那契数的默认方法定义为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]. 运行时不会进行计算。

整个示例程序将如下所示：

#include <iostream>
#include <array>
#include <utility>
#include <algorithm>
#include <iomanip>
// ----------------------------------------------------------------------
// 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) 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;
}
// We will automatically build an array of Fibonacci numbers at compile 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 an 64bit unsigned value (Binet's 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();

// All the above was compile time
// ----------------------------------------------------------------------


// Check, if a number belongs to the Fibonacci series
bool isFib(const unsigned long long numberToBeChecked) {
    return std::binary_search(FIB.begin(), FIB.end(), numberToBeChecked);
}

// Test
int main() {

    const unsigned long long testValue{ 498454011879264ull };

    std::cout << std::boolalpha << "Does '" <<testValue << "' belong to Fibonacci series?  --> " << isFib(testValue) << "\n\n";

    for (size_t i{}; i < 10; ++i)
        std::cout << i << '\t' << FIB[i] << '\n';

    return 0;
}

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

另外使用 gcc 10.2 和 clang 11.0.1 进行了测试

语言：C++ 17

推荐阅读