Числа Фибоначчи - динамический массив

Question

Я хочу написать программу чисел Фибоначчи, используя динамический массив в функции. Если я хочу инициализировать массив в функции, где я должен удалить этот массив? Вот код:

#include <iostream> 

using namespace std; 

int* fibo(int); 

int main() 
{ 
    int *fibonacci, n; 
    cout << "Enter how many fibonacci numbers you want to print: "; 
    cin >> n; 
    fibonacci = fibo(n); 
    for (int i = 0; i<n; i++) 
     cout << fibonacci[i] << " "; 

    //for (int i = 0; i < n; i++) 
     //delete w_fibo[i]; 
    //delete[] w_fibo; 

    return 0; 
} 

int* fibo(int n) 
{ 
    int* w_fibo = new int[n]; 
    if (n >= 0) 
     w_fibo[0] = 1; 
    if (n >= 1) 
     w_fibo[1] = 1; 

    for (int i = 1; i < n; i++) 
     w_fibo[i + 1] = w_fibo[i] + w_fibo[i - 1]; 

    return w_fibo; 
} 

Answer 1

Вам не нужно инициализировать массив! лучше динамическое представление Фибоначчи может выглядеть так:

int fib2 (int n) { 
int i = 1, j = 0; 
    for (int k = 0; k < n; k++) { // The loop begins to work real after one loop (k == 1). Sounds interesting! 
    j += i;     // Adds the produced number to the last member of the sequence and makes a new sentence. 
    i = j - i;    // Produces the number that should be added to the sequence. 
    } 
return j; 
} 

и вы можете получить п-го числа Фибоначчи, используя этот метод. Это O (журнал (п)), так что это так efficient.`

int fib3 (int n) { 

int i = 1, j = 0, k = 0, h = 1, t=0;  
while (n > 0) { 

    if (n % 2) {          // | 
     t = j * h;          // | 
     j = i * h + j * k + t; 
     i = i * k + t; 
    } 
    t = h * h; 
    h = 2 * k * h + t; 
    k = k * k + t; 
    n /= 2; 
    } 
    return j; 
} 

Answer 2

Если выделить std::vector<int> внутри fibo() и резервного достаточно памяти, а затем вернуть его по значению, распределение памяти позаботятся для вас компилятором:

#include <iostream> 
#include <vector> 

using namespace std; 

std::vector<int> fibo(int n) 
{ 
    std::vector<int> w_fibo; 
    w_fibo.reserve(n); 

    if (n >= 0) 
     w_fibo[0] = 1; 
    if (n >= 1) 
     w_fibo[1] = 1; 

    for (int i = 1; i < n; i++) 
     w_fibo[i + 1] = w_fibo[i] + w_fibo[i - 1]; 

    return w_fibo; 
} 

int main() 
{  
    int n = 10; 
    std::vector<int> fibonacci = fibo(n); 
    for (int i = 0; i<n; i++) 
     cout << fibonacci[i] << " "; 
} 

Live Example ,

ПРИМЕЧАНИЕ: Это гарантирует, что во время C++ 11 (перемещение семантики) это неизбежно будет копироваться и, скорее всего, это произойдет в C++ 98 (копирование с использованием оптимизации возвращаемого значения).

Answer 3

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

Если вам нужен эффективный метод для получения n-го числа Фибоначчи, у нас есть процедура временной сложности O (1).

Он основан на Binet's formula, который, как мне кажется, наши друзья на math.se будут лучше доказывать, поэтому не стесняйтесь следовать этой ссылке.

сама формула, учитывая = 1,618 и Ь = -0,618 (эти приблизительные значения)

п-й член представляет собой (а^п - Ь^п) /2.236. Хороший способ обойти это (поскольку мы используем приблизительные значения) будет добавлять 0,5 и выполнять функцию пола.

math.floor(((math.pow(1.618,n)-math.pow(-0.618,n))/2.236 + 0.5)