c++ - 如何存储非常大的斐波那契数的输出？

Question

我正在为第 n 个斐波那契数编写一个程序。我使用递归和内存制作了以下程序。主要问题是 n 的值可以达到 10000，这意味着 10000 的斐波那契数将超过 2000 位长。

通过一些谷歌搜索，我发现我可以使用数组并将解决方案的每一位存储在数组的一个元素中，但我仍然无法弄清楚如何在我的程序中实现这种方法。

#include<iostream>

using namespace std;

long long int memo[101000];
long long int n;
long long int fib(long long int n)
{
    if(n==1 || n==2)
        return 1;
    if(memo[n]!=0)
        return memo[n];
    return memo[n] = fib(n-1)  + fib(n-2);
}
int main()
{
    cin>>n;
    long long int ans = fib(n);
    cout<<ans;
}

我该如何实现该方法，或者是否有其他方法可用于实现如此大的值？

Answer 1

我认为应该指出的一件事是，还有其他方法可以实现 fib，这对于像 C++ 这样的东西来说更容易计算

考虑下面的伪代码

function fib (n) {
  let a = 0, b = 1, _;
  while (n > 0) {
    _ = a;
    a = b;
    b = b + _;
    n = n - 1;
  }
  return a;
}

这不需要内存，您不必担心因太多递归调用而炸毁堆栈。递归是一种非常强大的循环结构，但它是最好留给 Lisp、Scheme、Kotlin、Lua(以及其他一些语言)等语言的 fubu 事物之一，它们如此优雅地支持它。

这并不是说在 C++ 中不可能消除尾部调用，但除非您明确地针对它进行优化/编译，否则我怀疑您使用的任何编译器是否会默认支持它。

至于计算特别大的数字，您将不得不通过添加 The Hard Way 来发挥创意，或者依赖任意精度的算术库，例如 GMP .我敢肯定还有其他库。

---

添加 The Hard Way™

还记得小时候刚从铝箔纸上取下来的时候，你是如何加大数字的吗？

5岁数学

  1259601512351095520986368
+   50695640938240596831104
---------------------------
                          ?

好吧，你必须添加每一列，从右到左。当一列溢出到两位数时，请记住将那个 1 移到下一列。

                 ... <-<b>0</b><b>0</b><b>1</b>
  1259601512351095520986368
+   50695640938240596831104
---------------------------
                  ... <-<b>4</b><b>7</b><b>2</b>

第 10,000 个斐波那契数有数千位长，因此它不可能适合任何 C++ 提供的开箱即用的整数。因此，在不依赖库的情况下，您可以使用字符串或单位数字数组。要输出最终数字，您必须将其转换为字符串。

( woflram alpha: fibonacci 10000 )

按照这种方式，您将执行几百万个个位数的加法；这可能需要一段时间，但对于任何现代计算机来说都应该是轻而易举的事。该上类了!

---

这是 JavaScript 中 Bignum 模块的示例

const Bignum =
  { fromInt: (n = 0) =>
      n < 10
        ? [ n ]
        : [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]

  , fromString: (s = "0") =>
      Array.from (s, Number) .reverse ()

  , toString: (b) =>
      b .reverse () .join ("")  

  , add: (b1, b2) =>
    {
      const len = Math.max (b1.length, b2.length)
      let answer = []
      let carry = 0
      for (let i = 0; i < len; i = i + 1) {
        const x = b1[i] || 0
        const y = b2[i] || 0
        const sum = x + y + carry
        answer.push (sum % 10)
        carry = sum / 10 >> 0
      }
      if (carry > 0) answer.push (carry)
      return answer
    }
  }

我们可以验证上面的 Wolfram Alpha 答案是否正确

const { fromInt, toString, add } =
  Bignum

const bigfib = (n = 0) =>
{
  let a = fromInt (0)
  let b = fromInt (1)
  let _
  while (n > 0) {
    _ = a
    a = b
    b = add (b, _)
    n = n - 1
  }
  return toString (a)
}

bigfib (10000)
// "336447 ... 366875"

展开下面的程序以在浏览器中运行它

const Bignum =
  { fromInt: (n = 0) =>
      n < 10
        ? [ n ]
        : [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]
        
  , fromString: (s = "0") =>
      Array.from (s) .reverse ()
      
  , toString: (b) =>
      b .reverse () .join ("")  
      
  , add: (b1, b2) =>
    {
      const len = Math.max (b1.length, b2.length)
      let answer = []
      let carry = 0
      for (let i = 0; i < len; i = i + 1) {
        const x = b1[i] || 0
        const y = b2[i] || 0
        const sum = x + y + carry
        answer.push (sum % 10)
        carry = sum / 10 >> 0
      }
      if (carry > 0) answer.push (carry)
      return answer
    }
  }
  
const { fromInt, toString, add } =
  Bignum

const bigfib = (n = 0) =>
{
  let a = fromInt (0)
  let b = fromInt (1)
  let _
  while (n > 0) {
    _ = a
    a = b
    b = add (b, _)
    n = n - 1
  }
  return toString (a)
}

console.log (bigfib (10000))