我使用内存来减少完成递归斐波那契所花费的时间。
但问题是它会导致整数溢出,所以数字在 50thish 数字之后没有完成。
那么如何在递归和迭代中防止整数溢出?
我听说运算符重载可以解决它..?但我不知道该怎么做。
int recursiveFib(int n) {
if (n <= 1)
return n;
else if (memo[n]!=0)
return memo[n];
else
return memo[n] = recursiveFib(n - 1) + recursiveFib(n - 2);
}
int iterativeFib(int n) {
int x = 0, y = 1, z = 0;
for (int j = 0; j < n; j++) {
z = x + y;
x = y;
y = z;
}
return x;
}
int main() {
for (int n=0; n<=200; n+=10){
cout << "when n equals to " << n << ", Recursive Fibonacci : \n";
for (int i = 0; i <= n; i++) {
cout << recursiveFib(i)<<" ";
}
for (int n = 0; n <= 200; n += 10) {
cout << "when n equals to " << n << ", Iterative Fibonacci : \n";
for (int i = 0; i <= n; i++) {
cout << iterativeFib(i) << " ";
}
结果应该是每次递增 n+10 时打印斐波那契数列,在 30 分钟内递归和迭代。
最佳答案
第 200 个斐波那契数(甚至第 50 个)大于 2^32(整数极限)。我建议您使用 unsigned long long
而不是 int
,或者甚至使用数组创建一个大整数类型,例如 here .
关于c++ - 具有整数溢出的递归斐波那契,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57817558/