9 способов генерации чисел Фибоначчи на C++


Это код на C++, который состоит из 9 различных функций, которые генерируют числа Фибоначчи. Хотя все функции дисплея аналогичного результата, упор делается на практике используют различные способы.

Я хотел бы знать лучшие способы / техники для улучшения существующего кода (особенно, 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;
}


Комментарии
2 ответа

Мое первое замечание заключается в том, что я не видел самый очевидный способ. Простой рекурсивный алгоритм (хотя этак делает печать их в порядок сложнее).

fibo_1

Массивы имеют фиксированный размер во время компиляции

Динамически размера массива не является частью стандарта.

int x[n];  // Not allowed unless n is `constexpr`.

Хотя многие компиляторы поддерживают это расширение, его не технически часть стандарта и, таким образом, лучше избегать в предпочтении использования std::vector.

Мемоизация

т. е. хранение промежуточных значений.
Это не реально полезной или эффективной, если вы не планируете повторно использовать значения. Если вы просто используете их для вычисления следующего значения, то вы могли бы потенциально использовать две переменные (два предыдущих значений.

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

Я бы переписал так:

    for (int index = 2; index < n; index++, f_index_minus_2 = f_index_minus_1, f_index_minus_1 = f){    
f = f_index_minus_1 + f_index_minus_2;
std::cout << "-" << f;
}

fibo_2

Это в основном fib0_1, но с использованием цикла while. Ничего не имею против цикла while, но я предпочитаю for(;;) петли сделать петлю инициализации и приращения все в одном месте.

fib0_3

Здесь вы используете очень сложная рекурсия. Я не думаю, что я мог придумать, что ответить. Так умные.

fibo_4

Это в основном такие же, как fibo_1 но используя std::vector а не массива. А такие у меня есть один меньше точки как вектор лучше структуру использовать здесь.

fibo_5

Это fibo_4 но без создания сначала весь массив. Я предпочитаю это fibo_4 но чтобы убедиться, что вы не попали любые вопросы с изменением размера вектора вдоль вашего пути вы должны зарезервировать место для всех значений.

std::vector<int> f;
f.reserve(n);
f.push_back(0);
f.push_back(1);

fibo_6

Здесь вы просто удалите дополнительную локальную переменную val и явно с помощью вектора.

Я предпочитаю использовать значение. Это делает код проще читать (и, следовательно, более выразительным). Маловероятно, что переменная будет длиться в машинный код и компилятор, скорее всего, оптимизировать 5/6 в один и тот же код.

fibo_7

Очевидно, что это способ, чтобы вычислить факториал числа, без того, чтобы перебрать все другие факториалы на пути. Поэтому использование его в этом контексте просто делает код труднее читать. Если вы собираетесь перебрать код просто использовать простой метод. Этот метод идеально подходит, если вы просто хотите найти факториал n без работы из другого факториалов.

Это значение никогда не изменяется и одинаков каждый раз, когда функция вызывается. Так что вы можете вычислить его один раз и хранить его.

    float sqr5 = std::sqrt(5);

// Write like this.
static const sqrt5 = = std::sqrt(5); // const non mutable.
// static calculated first time the
// function is called but never again.

fibo_8

Не знаю, почему вы делаете это.

fibo_9

Не понимаю этого вообще.

Я бы написал так.

// Memoization separate from function.
// This means you can re-use already calculated values without
// having to do it again.
std::vector<int> fib = {0,1}; // You can fill in more default values.

// Separate calculating the value from printing the value.
// This allows you to calculate and access the values
// without having to print a stream of numbers.
void calcFib(int n)
{
while(fib.size() < n) {
fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
}
}

// Finally printing.
// It makes sure there are enough values to print (with may do nothing)
// Then it uses standard algorithms to loop over the array and print it
// to a provided stream. Note we don't assume a stream but will default
// to std::cout if none is provided.
void printFib(int n, std::ostream& out = std::cout)
{
if (n < 1) {
return;
}
calcFib(n);

// Print all but the last value.
// each value suffixed by "-"
auto end = std::next(std::begin(fib), n - 1);
std::copy(std::begin(fib), end,
std::ostream_iterator<int>(out, "-"));

// Print the last value (no suffix).
// Note: end is guaranteed in the range as we used (n-1) above
std::cout << *end;
}

3
ответ дан 12 марта 2018 в 04:03 Источник Поделиться

Ваш код, кажется, работает хорошо, и он-то хорошо проверял (хотя надо сравнить выходы функция визуально). Некоторые детали может быть улучшено:

Отступы и интервалы

Вмятины, похоже, немного в нескольких местах.

Кроме того, несколько пустых строк, кажется, в местах, где это не очень уместно/полезно.

Именования

Имена функций, таких как fibo_N не очень легко понять. Было бы легко найти имена более значимые, такие как fibo_recursive.

Бесполезно переменной Temp

Используя 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;
}
}

Это будет завершено

1
ответ дан 12 марта 2018 в 04:03 Источник Поделиться