关于阶乘算法

您所在的位置:网站首页 求阶乘代码 关于阶乘算法

关于阶乘算法

#关于阶乘算法| 来源: 网络整理| 查看: 265

以BUCTOJ里碰到的一道题目为例引出两个问题:

题目1:给定一个数n,问n的阶乘的十进制表示中末尾有几个0?

题目2:给定一个数n,问n的阶乘的二进制表示中末尾有几个0?

1.数字相乘得出后缀0,必须要偶数乘以5,显然一个偶数的因子中,因子5的个数是小于因子2的个数的,所以计算后缀0的个数只需要计算有几个因子5(因为要取因子2和因子5中个数较小的那一个)

然后进行分情况讨论:

被5整除,但不被25整除:一个因子5

被25整除,但不被125整除:两个因子5

被125整除,但不被625整除:三个因子5

以此类推...

所有因子5的个数等于被5整除,但不被25整除 + 被25整除,但不被125整除 + ...

实际计算时,能被25整除的也能被5整除,所以只是简单的加上能被25整除的数的个数而没有乘以2(25中含有两个因子5),因为前面计算能被5整除的数时已经算过一次。

计算图如下:

1~2之间为因子个数为1,被5整除,但不被25整除

2~3之间为因子个数为2,被25整除,但不被125整除

 实际实现起来的代码:

int res = 0; while(n>=5){ n/=5; res+=n; } cout


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3