关于阶乘算法 |
您所在的位置:网站首页 › 求阶乘代码 › 关于阶乘算法 |
以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 |