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

Question

如何在C/C++中计算第 n 个斐波那契数？斐波那契数最多可包含 1000 位数字。我可以生成高达 2^64 的数字（无符号长长）。由于这是数字的限制，所以我猜必须有其他方式来做到这一点 - 我不知道。

编辑：

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

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。

Answer 2

您可以尝试将GMP用于任意大的整数。