0

有人可以让我知道以下代码是否有问题...在一个问题中，有人问我以下斐波那契数函数是否有问题。

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

其中 n 为 0 ... 100

所以我的答案是什么，因为我看不到任何明显的东西。语法似乎很好，从逻辑上讲，这是计算斐波那契数。我做出这个假设是否正确？

4

2 回答 2

7

这取决于你要问什么样的问题。我在这里看到两个问题：

  • 递归。没有理由这样做。只需使用迭代。
  • 范围溢出。inttype cant hold all Fibonacci numbers in range [0, 100]

这是在 Python 中使用迭代实现 fib 的示例（只是因为它可以fib(100)开箱即用）：

In [16]: def fib(n):
   ....:     curr, next = 0, 1
   ....:     for x in range(n):
   ....:         curr, next = next, curr
   ....:         next += curr
   ....:     return curr
   ....: 

In [17]: fib(100)
Out[17]: 354224848179261915075L
于 2013-10-10T10:45:23.200 回答
3

抱歉，如果答案为时已晚，但您还应该研究此功能的复杂性，以更好地理解为什么它不能正常工作。

由于对于您调用fib(n-1)和fib(n-2)的函数的每次上诉， fib( n)执行的操作数将在2^n左右。检查以下程序，它计算fib()被调用的次数：

#include <iostream>
using namespace std;

int cnt = 0;

int fib(int n) {
    cnt++;
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    cout << fib(15) << '\n';
    cout << cnt << '\n';
}

因此，如果您要调用fib(100)，它将执行大约10^18次操作，并且假设您的计算机足够快，可以在1 秒内进行10^9次操作，完成此操作大约需要33 年。

但这会导致更早的堆栈溢出错误。

确实fib(100)将有超过19 个数字，这是（大约） long long可以保持的最大值，但这不是您的函数“粘”的主要原因。

一个好的（也许是最好的）替代方案是按照上面@soon 所说的那样，使用具有线性复杂度的迭代函数/算法（你的函数是指数的，在这里阅读更多）。

这是使用C++中的大数实现的斐波那契函数代码（实际上还有更多C，但无论如何）：

#include <iostream>
using namespace std;

const int maxsize = 10000; // number of digits
int n;

// note that the digits are keep reversed in the vector
// the bigsum function is as you would use add in math
// a = a + b
void bigsum(int a[], int b[]) { // in a[0] I hold the number of digits of 'a'
    int i, t = 0;
    for (i = 1; i <= a[0] || i <= b[0] || t; ++i) { // while you still have digits to add
        t = t + a[i] + b[i]; 
        a[i] = t % 10;
        t /= 10;
    }
    a[0] = i - 1; // the new a[0]
}

int zero[maxsize];

// a = b
void copy(int a[], int b[]) {
    for (int i = 0; i <= b[0]; ++i) {
        a[i] = b[i];
    }
}

void fib(int n) {
    if (n < 0) {
        cout << "NA";
    } else if (n == 0) {
        cout << 0;
    } else if (n == 1 || n == 2) {
        cout << 1;
    } else if (n == 3) {
        cout << 2;
    } else {
        int first[maxsize], second[maxsize], third[maxsize];
        copy(first, zero); copy(second, zero); copy(third, zero);
        first[0] = first[1] = second[0] = second[1] = 1; // initializing the numbers with 1
        third[0] = 1; third[1] = 2; // initializing with 2

        for (int i = 4; i <= n; ++i) {
            copy(first, second);
            copy(second, third); // if you don't understand why these 3, try to do it on a paper
            bigsum(third, first);
        }

        for (int i = third[0]; i >= 1; --i) { // because the digits are reversed
            cout << third[i];
        }
    }
    cout << '\n';
}

int main() {
    cin >> n;
    fib(n);
}

现在fib函数适用于更高的数字（10000位，如果你想要更高的数字，只需更改maxsize值），操作总数为n * NUMBER_OF_DIGITS，大约为n^2（远小于2^n）。

另一个非常好的解决方案是使用2x2 矩阵，它允许您计算 aprox 中的余数fib(n) % SOME_NUMBER。log2(n)操作（您可以使用“平方求幂”，请参阅此）。在此处阅读有关矩阵解决方案的更多信息。

总之，您的程序并不好，因为它以指数复杂度运行，而且它使用了太多的堆栈内存（即使它返回正确的值）。

希望您现在了解您的功能问题。如果这篇文章不应该在这里，再次抱歉。

祝一切顺利！

于 2013-10-11T19:27:33.573 回答