找出斐波那契数列的第 N 项

Question

我正在编写一些使用多个函数的代码。一种是生成直到用户输入的第 N 项的斐波那契数列。另一个功能是在序列中找到 largest/last 个数字。

我目前可以很好地打印出序列，但我的主要问题是我找不到打印出序列中 last/largest 整数的方法。

这是我想要得到的输出：

Enter a number: 9
The series is: 0 1 1 2 3 5 8 13 21 
the maximum input is 21

在查找最后一个数字的函数中，我不确定从哪里开始，因为我假设打印输出是一个整数，所以我想不出一种方法来访问最后一个整数。

这是我的代码：

#include <iostream>
#include <ctime>
#include <time.h>

using namespace std;

int printSequence(int x);
int maxInput(int n);

int main()
{
    int x;
    cout << "Enter an integer: " << endl;
    cin >> x;

    printSequence(x);

    cout << maxInput(x) << endl;

    return 0;
}

int printSequence(int x)
{
    int t1 = 0, t2 = 1, temp = 0;

    for (int i = 1; i <= x; ++i)
    {
        if (i == 1)
        {
            cout << t1 << ", ";
            continue;
        }
        if (i == 2)
        {
            cout << t2 << ", ";
            continue;
        }
        temp = t1 + t2;
        t1 = t2;
        t2 = temp;

        cout << temp << ", ";
    }
    cout << endl;

    return temp;
}

int maxInput(int x)
{
    x = x % 60;
    return (printSequence(x) % 10);
}

Answer 1

这是一个更简单的使用黄金比例的方法，单个值的时间复杂度为O(1)，整个序列的时间复杂度为θ(n)，O(1) space 复杂度，只存储最后计算的值，这就是你需要的：

#include <iostream>
#include <cmath>

int fibonacci(int n) // find nth value in the fibonacci sequence
{
    double ratio = (1 + sqrt(5)) / 2; // golden ratio
    return round(pow(ratio, n) / sqrt(5));
}

int printSequenceAndReturnMax(int x) // print the sequence and return max
{
    int value = 0;
    std::cout << "The series is: " << value << " ";
    for (int i = 1; i < x; i++)
    {
        value = fibonacci(i);
        std::cout << value << " ";
    }
    return value;
}

void maxInput(int value) // pass max value as parameter
{
    std::cout << "\nThe maximum input is: " << value << "\n"; // print it
}

int main()
{
    int x;
    std::cout << "Enter an integer: ";
    std::cin >> x;
    int max = printSequenceAndReturnMax(x); // will have the max value
    maxInput(max);
}

结果：

Enter an integer: 9
The series is: 0 1 1 2 3 5 8 13 21
The maximum input is: 21

Answer 2

修改后的代码如下：

#include <iostream>
#include <ctime>
#include <time.h> 

using namespace std;

int printSequence(int x);

int maxInput(int n);

int main() {

    int x;
    cout<<"Enter an integer: "<< endl;
    cin>> x;

    int max = printSequence(x);
    // max is the last Integer in Set
    cout<<"the maximum input is: "<<max<< endl;


    return 0;
}

int printSequence(int x){

    int t1 = 0, t2 = 1, temp = 0;

    for (int i = 1; i <= x; ++i) {

        if(i == 1) {
            cout << t1 << ", ";
            continue;
        }
        if(i == 2) {
            cout << t2 << ", ";
            continue;
        }
        temp = t1 + t2;
        t1 = t2;
        t2 = temp;
        
        cout << temp;
        if(i!=x)cout << ", ";

    }
    cout<<endl;

    return temp;
}

描述：
您已经 return 来自函数调用 temp 的最后一个数字 printSequence 因此您可以将其用作最终整数。

另一个解决方案：
最好让你的 printSequence void 函数只打印，在循环结束时你可以将 temp 值设置为全局 int 以将其用作序列中的最大整数/最后一个整数。
在这里您可以使用 maxx 作为您的 final/last 变量。

如：

#include <iostream>
#include <ctime>
#include <time.h> 

using namespace std;

void printSequence(int x);
int maxx;

int main() {

    int x;
    cout<<"Enter an integer: "<< endl;
    cin>> x;
    printSequence(x);
    // max is the last Integer in Set
    cout<<"the maximum input is: "<<maxx<< endl;


    return 0;
}

void printSequence(int x){
    
    int t1 = 0, t2 = 1, temp = 0;

    for (int i = 1; i <= x; ++i) {

        if(i == 1) {
            cout << t1 << ", ";
            continue;
        }
        if(i == 2) {
            cout << t2 << ", ";
            continue;
        }
        temp = t1 + t2;
        t1 = t2;
        t2 = temp;
        
        cout << temp;
        if(i!=x)cout << ", ";

    }
    cout<<endl;
    maxx = temp;
    
}

输出：

另一个输出：

Answer 3

这是一个超快速的低内存占用解决方案。

它将轻松满足您的所有要求。而且，使用标准库中的算法非常灵活。

因此，我们将使用适合 64 位 unsigned long long 值的所有斐波那契数的编译时预计算。

但首先是一些理论。

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

使用 Binet's formula 您可以计算出第 93 个斐波那契数是最后一个适合 64 位无符号值的数。

现在，在编译期间计算 93 个值是一项非常简单的任务。并且不会产生任何运行时开销。内存消耗为 752 字节！完全可以接受。

我们首先将计算斐波那契数的默认方法定义为 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 一个 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 项

Find the Nth term of the fibonacci sequence

c++

integer

loops

input

function