阶乘相关的算法及其C++实现

  次阅读 作者:智能小宝 来源:互联网 2016-01-26 10:30 我要评论(0)

有关阶乘的算法,不外乎两个方面:一是高精度计算;二是与数论相关。

一、 高精度计算阶乘

这实际上是最没有技术含量的问题,但是又会经常用到,所以还是得编写,优化它的计算。

首先看小于等于12的阶乘计算(计算结果不会超出32位范围):

int factorial(int n) {

if (n == 1 || n == 0)

return 1;

return factorial(n-1)*n;

}

这个递归程序简单明了,非常直观,然而一旦n > 12,则超过32位int型的范围出现错误结果,所以上面这个递归程序仅适合n <= 12的阶乘计算,为了计算较大n的阶乘,需要将高精度乘法算法纳入到阶乘计算中来,高精度乘法过程可以如下简单的描述:(其中A * B = C,A[0], B[0], C[0]分别存储长度)

for (i = 1; i <= A[0]; i++)

for (j = 1; j <= B[0]; j++) {

C[i+j-1] += A[i]*B[j];// 当前i+j-1位对应项 + A[i] * B[j]

C[i+j] += C[i+j-1]/10;// 它的后一位 + 它的商(进位)

C[i+j-1] %= 10;// 它再取余即可

}

C[0] = A[0] + B[0];

while (C[0] > 1 && C[C[0]] == 0) C[0]--;// 去头0,获得实际C的长度

有了这个高精度乘法之后,计算阶乘就可以简单的迭代进行:

for (i = 2; i <= n; i++) {

将i转换成字符数组;

执行高精度乘法:将上一次结果乘上i

}

二、 与数论有关

由于阶乘到后面越来越大,巧妙的利用数论求得一些有趣的数字(数值)等成为阶乘算法的设计点,下面给出几道相关的问题与分析:

(1)计算阶乘末尾第一个非0数字:

这是一个比较经典的问题,比较复杂的算法是利用一个艰难的数学公式,可惜我不会,从网上的资料学习中,整理出下面这个简单易懂的算法

观察n!,可以发现在乘的过程中,对于任意 n > 1,n!的末尾第一个非0数字都是偶数。我们只需保留最后一位非零数。当要乘的数中含有因数5时,我们可以把所有的因数5都当作8来乘。这是因为:

x2*5= 10(舍)或 60,最后一位非零数为6。而恰好2*8=16,末位为6。

x4*5= 70(舍)或 20,最后一位非零数为2。而恰好4*8=32,末位为2。

x6*5= 30(舍)或 80,最后一位非零数为8。而恰好6*8=48,末位为8。

x8*5= 90(舍)或 40,最后一位非零数为4。而恰好8*8=64,末位为4。

(对于n > 1时,最后一位不会出现 1, 7, 3, 9,而永远是2, 4, 6, 8的循环出现)

因此,在迭代作乘法时,主要就是计算因子5的数量,同时可见因子5的个数以4为循环节(即只需要取它的数量对4取模)。那么对于不同情况下的因子5的数量,可以通过res[5][4] = {{0,0,0,0}, {2,6,8,4}, {4,2,6,8}, {6,8,4,2}, {8,4,2,6}}来得到,使用nonzero[i]表示i的阶乘的最后一位,那么:

如果t是偶数,则直接乘:nonzero[i] = (nonzero[i-1]*t)%10。

否则nonzero[i] = res[((nonzero[i-1]*t)%10)/2][five];

其中t是除掉所有因子5的结果,five为因子5数量对4的模。

(2)。 阶乘末尾有多少个0

分析发现,实际上形成末尾0,就是因子5的数量,而计算1~n之间包含一个因子i的个数的简单算法就是:

cnt = 0; while (n) { n /= i; cnt += n; }

因此,直接将i换成5,就可以得到因子5的数量,也即n!末尾0的数量。

(3)。 返回阶乘左边的第二个数字

简单算法:用实数乘,超过100就除以10,最后取个位即可。因为整数部分的个位就是阶乘结果左边的第二个数字。相关题目:

本站文章信息来源于网络以及网友投稿,本站只负责对文章进行整理、排版、编辑,是出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。如果您有什么意见或建议,请联系QQ28-1688-302!

人工智能实验室
相关文章相关文章
  • 无人驾驶汽车如何改变城市生活?听听他们怎么说

    无人驾驶汽车如何改变城市生活?听听他们怎么说

  • 英国研发“杀生”机器人 通过生命体获取能量

    英国研发“杀生”机器人 通过生命体获取能量

  • 未来两年人工智能要怎么走?看这篇就够了

    未来两年人工智能要怎么走?看这篇就够了

  • 韩春雨称已能重复实验结果 近期将有消息公布

    韩春雨称已能重复实验结果 近期将有消息公布

网友点评网友点评
阅读推荐阅读推荐

据国外媒体报道,在过去两年内,聊天机器人(chatbot)、人工智能以及机器学习的研发和采用取得了巨大进展。许多初创公司正利用人工智能和...

霍金 视觉中国 图 英国著名物理学家霍金(Stephen Hawking)再次就人工智能(AI)发声,他认为:对于人类来说,强大AI的出现可能是最美妙的...

文|郑娟娟 今年,人工智能(AI) 60岁了。在AI60岁的时候,笔者想要介绍一下AI100,一个刚刚2岁的研究项目,但它的预设寿命是100年,甚至更长...

AlphaGo与李世石的人机大战,为大众迅速普及了人工智能的概念。 但对谷歌而言,除了下围棋,现在的人工智能进展到哪一步了?未来,人工智能...