这个C++代码有什么问题

有人能让我知道如果下面的代码有什么问题吗...... 在一个问题中，我被问到是否有任何错误的下面的斐波那契数字函数。这个C++代码有什么问题

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

其中n为0 ... 100

所以我的答案是什么，因为我什么都看不到明显的。语法看起来很好，逻辑上这是计算一个斐波那契数。我是否正确地做出了这个假设？

来源

2013-10-10 nixgadgets

对我来说这似乎很老实。注意：只是测试它？ – SinisterMJ

int可能会缩小fib（）的较大值，应该使用long来代替。 – Alex1985

+10

严重n = 100？ fib（100）== 354'224'848'179'261'915'075，而2⁶4-1只是18'446'744'073'709'551'615。 – kennytm

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

递归。没有理由。只需使用迭代。
范围溢出。 int型斜面容纳所有斐波那契数在范围[0，100]

这是FIB执行在Python使用迭代（只是因为它可以容纳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-10 10:45:23 soon

后者听起来像什么错了。是的，我编译的代码并运行它，但只是需要永远完成。也许使用无符号long long将会完成它。 – nixgadgets

并非在所有情况下。 'fib（100）'的长度是21位，但'unsigned long long'只能保存19位（如果sizeof = 64位）。 – soon

你是对的。谢谢 – nixgadgets

对不起，如果答案太晚，但你也应该研究这个函数的复杂性，以更好地理解为什么它不能正常工作。

因为功能的每项上诉调用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操作，以及假设您的计算机已经足够快速地运行10^91秒，它将需要33年来完成此操作。

但是这会导致一个堆栈溢出错误。

这是事实，FIB（100）将有超过19位，这是（近似）的最大值是长长可以持有，但这不是主要的原因，你的函数是“粘”。

良好的（也许是最好的）这里的替代是做的@soon上面所说的，使用迭代功能/算法有线性复杂（你的函数是指数，阅读更多here）。

下面是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）。

另一个非常不错的解决办法是使用2×2矩阵，它可以计算在aprox的其余FIB（N）％SOME_NUMBER。 log2（n）操作（您可以使用“通过平方运算的指数”，请参阅this）。详细了解矩阵解决方案here。

总之，你的程序不好，因为它运行在指数的复杂性，它也使用了太多的堆栈内存（即使它返回正确的值）。

希望你现在了解你的功能问题。对不起，如果这个帖子不应该在这里。

一切顺利！

来源

2013-10-11 19:27:33

这个C++代码有什么问题

回答

相关问题