时间戳

首页 > 解决方案 > C ++中带有记忆的斐波那契函数

c++ - C ++中带有记忆的斐波那契函数

问题描述

我试图用 C++ 做一个带有记忆的斐波那契函数。我选择了以下方法。

#include <iostream>
using namespace std;


int fibonacci(int index = 0) // Recursive // SwitchCase
{
    switch (index)
    {
    case 0:
        return 0;
    case 1:
        return 1;
    default:
        return fibonacci(index - 2) + fibonacci(index - 1);
    }
}

int fibo(int i) // Recursive & Memoisation
{
    static int const maxIndex = 2000;
    static int seq[maxIndex] = {0, 1};
    static int count = 2;
    if(i < count){return seq[i];}
    int temp = fibo(i-2) + fibo(i-1);
    count = count + 1;
    seq[i] = temp;
    return temp;
}

int main()
{
    int n = 50;
    for (int i=0; i<=n; i++)
    {cout << i << ":\t:" << fibo(i) << endl;} // Memoization
    cout << "\n\n" << endl;
    for (int i=0; i<=n; i++)
    {cout << i << ":\t:" << fibonacci(i) << endl;} // Non Memoization
    return 0;
}

我从索引 47 中注意到一些奇怪的东西。输出如下：

0:      :0  
1:      :1  
2:      :1  
3:      :2  
4:      :3  
5:      :5  
6:      :8  
7:      :13 
8:      :21 
9:      :34 
10:     :55 
11:     :89 
12:     :144
13:     :233
14:     :377
15:     :610
16:     :987
17:     :1597
18:     :2584
19:     :4181
20:     :6765
21:     :10946
22:     :17711
23:     :28657
24:     :46368
25:     :75025
26:     :121393
27:     :196418
28:     :317811
29:     :514229
30:     :832040
31:     :1346269
32:     :2178309
33:     :3524578
34:     :5702887
35:     :9227465
36:     :14930352
37:     :24157817
38:     :39088169
39:     :63245986
40:     :102334155
41:     :165580141
42:     :267914296
43:     :433494437
44:     :701408733
45:     :1134903170
46:     :1836311903
47:     :-1323752223 // <--
48:     :512559680   // <--
49:     :-811192543  // <--
50:     :-298632863  // <--


0:      :0
1:      :1
2:      :1
3:      :2
4:      :3
5:      :5
6:      :8
7:      :13
8:      :21
9:      :34
10:     :55
11:     :89
12:     :144
13:     :233
14:     :377
15:     :610
16:     :987
17:     :1597
18:     :2584
19:     :4181
20:     :6765
21:     :10946
22:     :17711
23:     :28657
24:     :46368
25:     :75025
26:     :121393
27:     :196418
28:     :317811
29:     :514229
30:     :832040
31:     :1346269
32:     :2178309
33:     :3524578
34:     :5702887
35:     :9227465
36:     :14930352
37:     :24157817
38:     :39088169
39:     :63245986
40:     :102334155
41:     :165580141
42:     :267914296
43:     :433494437
44:     :701408733
45:     :1134903170
46:     :1836311903
47:     :-1323752223 // <--
48:     :512559680   // <--
49:     :-811192543  // <--
50:     :-298632863  // <--

PS我做了非记忆方法只是为了检查数组部分是否有问题。

我不明白为什么输出包含负整数。我尝试过使用double而不是，int但输出仍然有负数。

谁能解释为什么会这样？提前致谢

标签： c++arraysfibonaccimemoizationmemoise

解决方案

所以基本上 int 有一个限制值，范围是从-2147483647到2147483647。

如果你想写更长的数字，你应该考虑使用：

  • unsigned int：只有最大值为4294967295 正
  • long long: 有最大值9223372036854775807
  • unsigned long long：只有最大值为18446744073709551615 正

还有一种解决方案：

您可以将很长的数字在几秒处分开int，然后将它们输出在一行中。

推荐阅读