我正在尝试编写C代码,它将打印出前100万个Fibonacci数字.
实际问题是我想得到10位F(1,000,000)
我理解序列是如何工作的,以及如何编写代码来实现它,但是F(1,000,000)非常大,我正在努力寻找一种方法来表示它.
这是我正在使用的代码:
#include<stdio.h>
int main()
{
unsigned long long n, first = 0, second = 1, next, c;
printf("Enter the number of terms\n");
scanf("%d",&n);
printf("First %d terms of Fibonacci series are :-\n",n);
for ( c = 0 ; c < n ; c++ )
{
if ( c <= 1 )
next = c;
else
{
next = first + second;
first = second;
second = next;
}
printf("%d\n",next);
}
return 0;
}
我正在long long尝试确保有足够的位来存储数字.
这是第一个100数字的输出:
First 100 terms of Fibonacci series 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
-1408458269
...
截断输出,但你可以看到问题,我相信生成的数字的大小导致值溢出为负.我不明白如何以诚实的方式阻止它.
有人能指出我如何真正处理这个大小的数字吗？
我没有尝试打印第一百万,因为如果打印失败,打印F(100)就没有多大希望了F(1,000,000).
你想要Fib(1000000)的最后10位数.阅读更多关于斐波那契数字的信息(并阅读两次).
不用多想,你可以使用一些像GMPlib这样的bignum库.你可以使用一些 bigint变量来循环计算Fib(1000000)(你当然不需要一个百万的数组,但是你手上的手指数量少于变量).当然,你不会打印所有的斐波那契数字,只有最后的1000000 个(因此今天便宜的笔记本电脑有足够的内存,并且会在不到一个小时内吐出这个数字).正如约翰科尔曼所回答的那样,它有大约200K的数字(即2500行,每行80位). mpz_tmpz_tmpz_t
(顺便说一下,当想到一个产生一些大输出的程序时,你会更好地猜测 - 输出的典型大小和获得它的典型时间;如果它不适合你的桌面空间 - 或你的台式计算机 - ,你有一个问题,也许是一个经济问题:你需要购买更多的计算资源)
请注意,有效的bignum算法是一个难题.bignum算法存在聪明的算法,它比你想象的天真算法更有效.
实际上,你不需要任何重要的东西.阅读一些关于模运算的数学教科书.和(或乘积)的模数与模量的和(相应的乘积)一致.使用该属性.一个10位整数适合64位,int64_t所以有些人认为你不需要任何bignum库.
(我想稍微多思考一下,你不需要任何计算机或任何C程序来计算它.一个便宜的计算器,一支铅笔和一张纸应该足够了,而且根本不需要计算器.)
编程时(或解决数学练习时)要学习的教训是考虑问题并尝试在开始编码之前重新表述问题.J.Pitrat(法国的人工智能先驱,现已退休,但仍在他的计算机上工作)有几个有趣的博客条目:是否有可能定义问题？, 当唐纳德和杰拉德满足罗伯特等.
理解和思考问题(以及子问题!)是软件开发的一个有趣部分.如果您从事软件开发工作,首先会要求您解决实际问题(例如,制作销售网站或自动吸尘器),您需要考虑将问题转化为可编码的问题.电脑.要有耐心,你需要十年时间来学习编程.
根据比奈公式，第 n 个斐波那契数大约是黄金比例（大约 1.618）的 n 次方，然后除以 5 的平方根。对数的简单使用表明，第 100 万个斐波那契数有超过 200,000 位数字。因此，前一百万个斐波那契数之一的平均长度超过 100,000 = 10^5。因此，您试图打印 10^11 = 1000 亿个数字。我认为你需要的不仅仅是一个大的 int 库来做到这一点。
另一方面——如果你想简单地计算百万分之一的数字，你可以这样做——尽管最好使用一种不计算所有中间数字的方法（简单地计算而不是打印它们）对于足够大的 n)，仍然不可行。众所周知（参见此），第 n 个斐波那契数是矩阵的 n 次幂的 4 个条目之一[[1,1],[1,0]]。如果您使用平方取幂（这也适用于矩阵乘法，因为矩阵乘法是关联的）和一个好的大 int 库 - 计算百万分之一的斐波那契数变得非常可行。
[进一步编辑]：这是一个计算非常大的斐波那契数的 Python 程序，修改后现在接受一个可选的模数。在幕后，它使用了一个很好的 C bignum 库。
def mmult(A,B,m = False):
#assumes A,B are 2x2 matrices
#m is an optional modulus
a = A[0][0]*B[0][0] + A[0][1]*B[1][0]
b = A[0][0]*B[0][1] + A[0][1]*B[1][1]
c = A[1][0]*B[0][0] + A[1][1]*B[1][0]
d = A[1][0]*B[0][1] + A[1][1]*B[1][1]
if m:
return [[a%m,b%m],[c%m,d%m]]
else:
return [[a,b],[c,d]]
def mpow(A,n,m = False):
#assumes A is 2x2
if n == 0:
return [[1,0],[0,1]]
elif n == 1: return [row[:] for row in A] #copy A
else:
d,r = divmod(n,2)
B = mpow(A,d,m)
B = mmult(B,B,m)
if r > 0:
B = mmult(B,A,m)
return B
def Fib(n,m = False):
Q = [[1,1],[1,0]]
return mpow(Q,n,m)[0][1]
n = Fib(999999)
print(len(str(n)))
print(n % 10**10)
googol = 10**100
print(Fib(googol, googol))
输出（添加空格）：
208988
6684390626
3239047153240982923932796604356740872797698500591032259930505954326207529447856359183788299560546875
请注意，您所谓的第 100 万个斐波那契数，我称为第 999,999 个——因为以 1 作为第一个斐波那契数开始更为标准（如果您想将其算作斐波那契数，则将 0 称为第 0 个）。第一个输出数字确认数字中有超过 200,000 个数字，第二个给出最后 10 个数字（这不再是一个谜）。最后一个数字是 googolth Fibonacci 数的最后 100 位数字——在几分之一秒内计算出来。我还没有能够做一个 googolplex :)
要"获取F(1,000,000)的最后10位数",只需%在计算时应用余数函数next并使用正确的格式说明符:"%llu".
没有必要对比10个最低有效数字更重要的数字求和.
// scanf("%d",&n);
scanf("%llu",&n);
...
{
// next = first + second;
next = (first + second) % 10000000000;
first = second;
second = next;
}
// printf("%d\n",next);
printf("%010llu\n",next);
我的输出(x最后5位数字不给出最终答案)
66843xxxxx