How to use Fibonacci sequence algorithm in C++

How to use the Fibonacci sequence algorithm in C

The Fibonacci sequence is a very classic sequence, and its definition is that each number is The sum of the first two numbers. In computer science, using the C programming language to implement the Fibonacci sequence algorithm is a basic and important skill. This article will introduce how to use C to write the Fibonacci sequence algorithm and provide specific code examples.

1. Recursive method

Recursion is a common method of Fibonacci sequence algorithm. In C, the Fibonacci sequence algorithm can be implemented concisely using recursion. The following is an example code for calculating Fibonacci numbers using the recursive method:

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1)
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int num;
    cout << "请输入你要计算的斐波那契数列的项数：";
    cin >> num;
    cout << "斐波那契数列的第" << num << "项为：" << fibonacci(num) << endl;
    return 0;
}

In the above code, we define a function fibonacci to calculate the ##th Fibonacci number sequence #n items. If n, return n directly; otherwise, use the recursive formula fibonacci(n) = fibonacci(n-1) fibonacci(n-2) to calculate the result.

2. Iterative method

In addition to the recursive method, we can also use iterative methods to calculate the Fibonacci sequence. Here is a sample code for calculating Fibonacci numbers using the iterative method:

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1)
        return n;

    int a = 0;
    int b = 1;
    int temp;
    for (int i = 2; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

int main() {
    int num;
    cout << "请输入你要计算的斐波那契数列的项数：";
    cin >> num;
    cout << "斐波那契数列的第" << num << "项为：" << fibonacci(num) << endl;
    return 0;
}

In the above code, we use a loop to calculate each term of the Fibonacci sequence starting from the first two numbers. We use three variables

a, b and temp, a and b respectively store two adjacent numbers, and temp is used to temporarily save calculation results. During the loop, we continuously update the values ​​of a and b until i loops to the target number of items n.

3. Comparing the efficiency of recursive and iterative methods

In actual programming, we need to consider the efficiency of the Fibonacci sequence algorithm. We can perform a performance comparison between recursive and iterative methods. The following is a simple evaluation code example:

#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;

int fibonacci_recursive(int n) {
    if (n <= 1)
        return n;
    else
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}

int fibonacci_iterative(int n) {
    if (n <= 1)
        return n;

    int a = 0;
    int b = 1;
    int temp;
    for (int i = 2; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

int main() {
    int num;
    cout << "请输入你要计算的斐波那契数列的项数：";
    cin >> num;

    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    int result_recursive = fibonacci_recursive(num);
    high_resolution_clock::time_point t2 = high_resolution_clock::now();
    auto duration_recursive = duration_cast<microseconds>(t2 - t1).count();

    high_resolution_clock::time_point t3 = high_resolution_clock::now();
    int result_iterative = fibonacci_iterative(num);
    high_resolution_clock::time_point t4 = high_resolution_clock::now();
    auto duration_iterative = duration_cast<microseconds>(t4 - t3).count();

    cout << "递归方法计算结果：" << result_recursive << endl;
    cout << "递归方法计算时间：" << duration_recursive << "微秒" << endl;
    cout << "迭代方法计算结果：" << result_iterative << endl;
    cout << "迭代方法计算时间：" << duration_iterative << "微秒" << endl;

    return 0;
}

Run the above code and enter the number of items in the Fibonacci sequence to compare the calculation results and time of the recursive method and the iterative method.

Summary:

This article introduces how to calculate the Fibonacci sequence using recursive and iterative methods in C, and provides specific code examples. Both recursive and iterative methods can calculate the Fibonacci sequence efficiently. In practical applications, we need to choose a suitable method according to specific needs and consider the efficiency of the algorithm.

The above is the detailed content of How to use Fibonacci sequence algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!