2

所以我写了一个递归程序，现在询问用户他们想要执行的许多斐波那契数。我遇到的问题是，在第 45 个数字之后，它给了我一个带有“-”的数字，并且它的数字不适合序列。我怎样才能改变它给我正确的号码？这是执行计算的代码的递归部分：

void fibonacci (int a, int b, int n, int count)
{
    if(n < count) 
    {
        cout<<a+b<<endl;
        fibonacci(b, a+b, n+1, count);
    }
}

这是序列的输出：

How many numbers do you want the Fibonacci sequence to process: 50
The starting numbers for the sequence are: 0, 1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543
-298632863
-1109825406

我需要进行哪些更改才能将 -# 更改为实数？

4

4 回答 4

9

您遇到了问题，因为您使用的数据类型 int是 32 位，并且只能在 2^31-1 = 2147483647 时保存值signed（默认，使用 31 位，占用 1 位以指示有符号性，这也解释了负数），2^32-1 = 4294967295 当unsigned. 您可以在此处使用 64 位数据类型（long long在大多数情况下），但稍后也会遇到此问题（我认为大约是第 94 个斐波那契数）。

这个问题的“真正”解决方案是编写自己的数值计算方法并使用自己的数字表示形式，即字符数组。您还可以寻找使用“bignum”库的各种可能性之一。您应该在一些 SO 问题中找到有关此的更多信息，例如this one。

于 2011-03-31T17:07:00.613 回答
1

将变量声明为 asunsigned int将允许您进行更多交互，但无论如何您都会遇到问题。使用 a 扩展变量的大小long long int仍然会延迟您的问题。你无法解决这个问题，因为迟早你会超过你可以表示的最大数量，无论你选择什么数据类型

于 2011-03-31T17:11:09.353 回答
0

整数只保存 32 位数据，最大值为 2,147,483,647。您的返回值“溢出”。使用 ulong 数据类型，它包含 64 位，最大值为 18,446,744,073,709,551,615。

于 2011-03-31T17:10:44.683 回答
0

使用 double 类型，因为 int 类型会很快溢出，以便计算中等大小的斐波那契数。大数应使用双浮点中的指数表示法。

由于您在每次下一次循环迭代中使用先前的数字上移一个，因此递归调用使用 fibonacci(a, a+b, n+1, count) 而不是 fibonacci(b,a+b,n +1，计数）。我编写了自己的递归函数，它的递归性较低，这将说明为什么要使用不同的递归调用来使逻辑更清晰。

我写的递归函数显示了非浮点数在斐波那契数中溢出的速度。

// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <conio.h>
using std::cout;
using std::endl;

int fibonacci(double n, int count) {
    char ch;
    static double lastnminus1, lastnminus2;
    if (n == 1) {
     lastnminus1 = 1;
     lastnminus2 = 0;
    }
    cout << lastnminus1 + lastnminus2 << endl;
    double temp = lastnminus1;
    lastnminus1 = lastnminus1 + lastnminus2;
    lastnminus2 = temp;
    if (static_cast<int>(n) % 24 == 0) { 
        cout << "press a key" << endl;
        ch = getch();
    }
    if ( n < count)
        fibonacci(n+1,count);

    return 0;
}

int main()
{
    fibonacci(1,200);
    return 0;
}
于 2018-08-11T07:31:05.850 回答