斐波那契数-动态数组

Kulis 发表于 Dev

后台

我想写斐波纳契数程序，在函数中使用动态数组。如果要在函数中初始化数组，必须在哪里删除该数组？这是代码：

#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;
}

拉索尔

您不必初始化数组！更好的动态斐波那契表示法可能是这样的：

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;
}

然后您可以使用此方法获得第n个fib号。它是O（log（n）），所以它是如此有效。

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;
}