在C++中生成Fibonacci数的9种方法

Question

这是由9个不同的函数组成的C++代码，这些函数生成斐波那契数。虽然所有的功能都显示出相同的结果，但强调的是使用不同的方法或方法。

我想知道更好的方法/技术来改进现有的代码(特别是使用Fibonacci矩阵恒等式的fibo_9函数，并且首先定义一个matrix_mul，它将两个平方(array)矩阵相乘，并将结果保存为vector。还有fibo_3，它使用递归方法)。

Github项目：nWays

// Author : anbarief@live.com
// Since 10 March 2018

#include <iostream>
#include <string>
#include <vector>
#include <cmath>


void fibo_1(int n){

    int f[n];

    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

        f[index] = f[index-1] + f[index-2];
        std::cout << "-" << f[index];

    }

}

void fibo_2(int n){

    int f[n]; int index=2;

    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    while (index < n) {

        f[index] = f[index-1] + f[index-2];
        std::cout << "-" << f[index];
        index = index + 1;

    }

}

int fibo_3(int n, int a = 0, int b = 1){

    std::cout << a << "-";

    if (n == 2){

    std::cout << b;

    return 0;

    }

    return fibo_3(n-1, b, a+b);

}

void fibo_4(int n){

    std::vector<int> f(n, 0);
    f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

        f[index] = f[index-1] + f[index-2];
        std::cout << "-" << f[index];

    }

}

void fibo_5(int n){

    std::vector<int> f(2, 0);
    f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

        int val = f[index-1] + f[index-2];

        f.push_back(val);
        std::cout << "-" << val;

    }

}

void fibo_6(int n){

    std::vector<int> f(2, 0);
    f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

        int val = f[index-1] + f[index-2];

        f.push_back(val);
        std::cout << "-" << f.back();

    }

}

void fibo_7(int n){

    float f[n];
    float sqr5 = std::sqrt(5);
    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

        f[index] = (1/sqr5)*(pow(0.5,index))*(pow(1+sqr5,index) - pow(1-sqr5,index));

        std::cout << "-" << f[index];

    }


}

void fibo_8(int n){

    float f[n];
    float sqr5 = std::sqrt(5);
    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

    if (index%2==0){
        f[index] = (1/sqr5)*(pow(0.5,index))*(pow(1+sqr5,index) - pow(1-sqr5,index));
    }
    else{
        f[index] = f[index-1] + f[index-2];
    };
        std::cout << "-" << f[index];

    }

}

std::vector<int> matrix_mul(int A[2][2], int B[2][2]){
    std::vector<int> res(4,  0);

    res[0] = A[0][0]*B[0][0] + A[0][1]*B[1][0];
    res[1] = A[0][0]*B[0][1] + A[0][1]*B[1][1];
    res[2] = A[1][0]*B[0][0] + A[1][1]*B[1][0];
    res[3] = A[1][0]*B[0][1] + A[1][1]*B[1][1];

    return res;
}

void fibo_9(int n){

    float f[n];
    int A[2][2], B[2][2];
    std::vector<int> M(4,0);

    f[0] = 0; f[1] = 1; f[2] = 1;

    A[0][0] = 1; A[0][1] = 1;
    A[1][0] = 1; A[1][1] = 0;

    B[0][0] = 1; B[0][1] = 1;
    B[1][0] = 1; B[1][1] = 0;


    std::cout << f[0] << "-" << f[1] << "-" << f[2];

    for (int index = 1; index < n-2; index++){
    // 2x2 Matrix multiplication 
        M = matrix_mul(B, A);
        B[0][0] = M[0]; B[0][1] = M[1];
        B[1][0] = M[2]; B[1][1] = M[3];

        f[3] = M[0];
        std::cout << "-" << f[3]; 
    }

}


int main(){

    int n = 20;

    std::string ex_1 = "fibo_1 : Using simple for-loop and fn = fn-1 + fn-2.";
    std::cout << '\n' << ex_1 << '\n';
    fibo_1(n);

    std::string ex_2 = "fibo_2 : Similar as fibo_1, but with while-loop.";
    std::cout << '\n' << ex_2 << '\n';
    fibo_2(n);

    std::string ex_3 = "fibo_3 : Using recursive method, with backward n.";
    std::cout << '\n' << ex_3 << '\n';
    fibo_3(n);

    std::string ex_4 = "fibo_4 : Similar as fibo_1, but using vector as container.";
    std::cout << '\n' << ex_4 << '\n';
    fibo_4(n);

    std::string ex_5 = "fibo_5 : Similar as fibo_4, using f.push_back method to add new Fibo number.";
    std::cout << '\n' << ex_5 << '\n';
    fibo_5(n);

    std::string ex_6 = "fibo_6 : Similar as fibo_5, but using f.back() to show the element.";
    std::cout << '\n' << ex_6 << '\n';
    fibo_6(n);

    std::string ex_7 = "fibo_7 : Using the analytical Fibo formula.";
    std::cout << '\n' << ex_7 << '\n';
    fibo_7(n);

    std::string ex_8 = "fibo_8 : Using combination of both Analytical formula, and the ususal fn = fn-1 + fn-2.";
    std::cout << '\n' << ex_8 << '\n';
    fibo_8(n);

    std::string ex_9 = "fibo_9 : Using Matrix identity of Fibonacci numbers, Fn = A^(n) F_init.";
    std::cout << '\n' << ex_9 << '\n';
    fibo_9(n);


    return 0;
}

Answer 1

您的代码似乎工作得很好，并且在某种程度上测试得很好(尽管需要比较功能输出)。还有一些细节可以改进：

压痕与间距

在几个地方，压痕似乎有点不对劲。

此外，一些空白行似乎是在一些地方，它不是很有意义/帮助。

命名

像fibo_N这样的函数名称不太容易理解。很容易找到更有意义的名称，比如fibo_recursive。

无用温度变量

使用std::string ex_X变量进行打印并不会增加太多。你可以用std::cout << your_literal_string;。

在此阶段，代码如下所示：

// Author : anbarief@live.com
// Since 10 March 2018

#include <iostream>
#include <string>
#include <vector>
#include <cmath>


void fibo_for(int n){
    int f[n];
    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){
        f[index] = f[index-1] + f[index-2];
        std::cout << "-" << f[index];
    }
}

void fibo_while(int n){
    int f[n]; int index=2;
    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    while (index < n) {
        f[index] = f[index-1] + f[index-2];
        std::cout << "-" << f[index];
        index = index + 1;
    }
}

int fibo_recursive(int n, int a = 0, int b = 1){
    std::cout << a << "-";

    if (n == 2){
        std::cout << b;
        return 0;
    }

    return fibo_recursive(n-1, b, a+b);
}

void fibo_vector(int n){
    std::vector<int> f(n, 0);
    f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){
        f[index] = f[index-1] + f[index-2];
        std::cout << "-" << f[index];
    }
}

void fibo_push_back(int n){
    std::vector<int> f(2, 0);
    f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){
        int val = f[index-1] + f[index-2];
        f.push_back(val);
        std::cout << "-" << val;
    }
}

void fibo_push_back_then_back(int n){
    std::vector<int> f(2, 0);
    f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){
        int val = f[index-1] + f[index-2];
        f.push_back(val);
        std::cout << "-" << f.back();
    }
}

void fibo_analytical(int n){
    float f[n];
    float sqr5 = std::sqrt(5);
    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){
        f[index] = (1/sqr5)*(pow(0.5,index))*(pow(1+sqr5,index) - pow(1-sqr5,index));
        std::cout << "-" << f[index];
    }
}

void fibo_combi_of_analytical_and_something(int n){
    float f[n];
    float sqr5 = std::sqrt(5);
    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

        if (index%2==0){
            f[index] = (1/sqr5)*(pow(0.5,index))*(pow(1+sqr5,index) - pow(1-sqr5,index));
        }
        else{
            f[index] = f[index-1] + f[index-2];
        };
        std::cout << "-" << f[index];
    }
}

std::vector<int> matrix_mul(int A[2][2], int B[2][2]){
    std::vector<int> res(4,  0);

    res[0] = A[0][0]*B[0][0] + A[0][1]*B[1][0];
    res[1] = A[0][0]*B[0][1] + A[0][1]*B[1][1];
    res[2] = A[1][0]*B[0][0] + A[1][1]*B[1][0];
    res[3] = A[1][0]*B[0][1] + A[1][1]*B[1][1];

    return res;
}

void fibo_matrix(int n){
    float f[n];
    int A[2][2], B[2][2];
    std::vector<int> M(4,0);

    f[0] = 0; f[1] = 1; f[2] = 1;

    A[0][0] = 1; A[0][1] = 1;
    A[1][0] = 1; A[1][1] = 0;

    B[0][0] = 1; B[0][1] = 1;
    B[1][0] = 1; B[1][1] = 0;


    std::cout << f[0] << "-" << f[1] << "-" << f[2];

    for (int index = 1; index < n-2; index++){
        // 2x2 Matrix multiplication 
        M = matrix_mul(B, A);
        B[0][0] = M[0]; B[0][1] = M[1];
        B[1][0] = M[2]; B[1][1] = M[3];

        f[3] = M[0];
        std::cout << "-" << f[3]; 
    }
}


int main(){
    int n = 20;

    std::cout << "\nfibo_for : Using simple for-loop and fn = fn-1 + fn-2.\n";
    fibo_for(n);

    std::cout << "\nfibo_while : Similar as fibo_for, but with while-loop.\n";
    fibo_while(n);

    std::cout << "\nfibo_recursive : Using recursive method, with backward n.\n";
    fibo_recursive(n);

    std::cout << "\nfibo_vector : Similar as fibo_for, but using vector as container.\n";
    fibo_vector(n);

    std::cout << "\nfibo_push_back : Similar as fibo_vector, using f.push_back method to add new Fibo number.\n";
    fibo_push_back(n);

    std::cout << "\nfibo_push_back_then_back : Similar as fibo_push_back, but using f.back() to show the element.\n";
    fibo_push_back_then_back(n);

    std::cout << "\nfibo_analytical : Using the analytical Fibo formula.\n";
    fibo_analytical(n);

    std::cout << "\nfibo_combi_of_analytical_and_something : Using combination of both Analytical formula, and the ususal fn = fn-1 + fn-2.\n";
    fibo_combi_of_analytical_and_something(n);

    std::cout << "\nfibo_matrix : Using Matrix identity of Fibonacci numbers, Fn = A^(n) F_init.\n";
    fibo_matrix(n);

    return 0;
}

你不需要数组

您不需要跟踪所有的计算值，只需要跟踪最后的2。您可以编写如下内容：

void fibo_for(int n){ 
    int prev = 0; int curr = 1; 
    std::cout << prev << "-" << curr;

    for (int index = 2; index < n; index++){
        int tmp = curr; curr+= prev; prev = tmp;
        std::cout << "-" << curr;
    }
}

这件事即将完成