c++ - 打印第 n 个斐波那契数 [最多 1000 位]

Question

已关闭。此问题不符合 Stack Overflow guidelines 。目前不接受答案。

---

要求提供代码的问题必须表现出对所解决问题的最低限度的了解。包括尝试的解决方案、为什么它们不起作用以及预期结果。另请参阅:Stack Overflow question checklist

已关闭 9 年前。

Improve this question

如何在C/C++中计算第n个斐波那契数？斐波那契数列最多可包含 1000 位数字。我可以生成最多 2^64 (unsigned long long) 的数字。由于这是数量的限制，所以我猜测必须有其他方法来做到这一点 - 我不知道。

编辑:

此外，它必须在不使用任何外部库的情况下完成。

Answer 1

既然你还没有表明你已经开始，我会给出一些提示。

一千位数字很多。比 C 或 C++ 中任何内置数字类型所能容纳的数量还要多。

解决这个问题的一种方法是使用任意精度的数学库。这将具有基本上可以为您提供数字中所需数量的结构。

另一种方法是滚动你自己的缓存和携带:

unsigned short int term1[1024];  // 1024 digits from 0-9
unsigned short int term2[1024];  // and another

unsigned short int sum[1024];    // the sum

addBigNumbers(&term1, &term2, &sum);   // exercise for the reader

我希望 addBigNumbers 的算法是这样的:

Start at the ones digit (index 0)
Add term1[0] and term2[0]
Replace sum[0] with the right digit of term1[0] + term2[0] (which is ... ?)
Keep track of the carry (how?) and use it in the next iteration (how?)
Repeat for each digit

现在，由于您正在计算斐波那契数列，因此您将能够重复使用这些大数字来计算序列中的下一项。您可能会发现，不要复制它们，而只需更改重复调用 addBigNumbers 时的项和总和，速度会更快。