注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

力的博客

小歇一会 heiheidemaolv

 
 
 

日志

 
 

编程之美-阶乘末尾0的个数  

2014-05-07 21:35:32|  分类: 热门面试题 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

这个题目是编程之美一书中给出的题目。

给定一个整数N,那么N的阶乘N!末尾有多少个0? 比如:N=10,N!=3628800,N!的末尾有2个0。

1) 递推

考虑阶乘的计算很容易溢出,直接计算阶乘肯定不合适。而每次相乘是否会有新的0产生,只和前一个阶乘的最后K位(注意是非0的位)有关。因此只记录 前一个阶乘0的个数和最后d的K位,就可推出后面的。K其实和当前计算的N有关。我们只需保证 K>=N的位数  就可以了,并保证 计算不会溢出。所以这个算法要保证 N < 10^5

代码如下:

01int countZero(int N) {
02    int ans = 0;
03    int maxInt = 1000000000;//10^9
04    int  tmpn = N;
05    while(tmpn){
06        maxInt /= 10;
07        tmpn /= 10;
08    }
09    int lastBit = 1; //保存上一个阶乘 的最后 K位数字
10    for (int i = 2; i <= N; i++) {
11        int cnt = 0;//新增加的0的个数
12        int tmp = lastBit * i;
13 
14        while ((tmp % 10) == 0) {
15            tmp /= 10;
16            cnt++;
17        }
18        //防止计算溢出
19        if (tmp > maxInt)
20            tmp = tmp % maxInt;
21        lastBit = tmp;
22        ans += cnt;
23    }
24    return ans;
25}
26 
27int main() {
28    cout << countZero(25) << endl;
29    cout << countZero(356) << endl;
30    return 0;
31}

 

2)数学解法

编程之美一书给出两个例如质因数的性质的解法。考虑哪些组合可以得到10即可,考虑哪些数相乘能得到10N!= K * 10M其中K不能被10整除,则N!末尾有M0。

N!进行质因数分解: N!=2X*3Y*5Z…,因为10=2*5,所以M25的个数即XZ有关。每一对25都可以得到10,故M=min(X,Z)。因为能被2整除的数出现的频率要比能被5整除的数出现的频率高,所以M=Z。其实也很好推出,1-9 中两两相乘,末位有0的话必须要有5,其它的数则是2的倍数。

01int countZero(int N)
02  {
03    int ret = 0;
04    int j;
05    for(int i=1; i<=N; i++)
06    {
07      j = i;
08      while(0==j%5)
09       {
10            ret++;
11            j /= 5;
12       }
13     }
14     return ret;
15   }

当然还有一种解法:

    Z =[N/5] + [N/52] + [N/53] + …

    [N/5] 表示不大于N的的数中5的倍数贡献一个5, [N/52] 表示不大于N的数中52的倍数在贡献一个5……

01int countZero(int N)
02 {
03  int ret = 0;
04  while(N)
05  {
06    ret += N/5;
07    N /= 5;
08  }
09  return ret;
10 }
  评论这张
 
阅读(72)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018