A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© iWilliam 中级黑马   /  2014-7-2 23:01  /  928 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 iWilliam 于 2014-7-2 23:00 编辑

刚才逛论坛,一不小心又看到了这个问题,发现貌似没有解释的很清楚的,一时心血来潮,写一哈我认为最高效的解决方案
  1.         public static int countZero(int n)
  2.         {
  3.                 int result = 0;
  4.                 while (n > 0)
  5.                         result += n /= 5;
  6.                 return result;
  7.         }
复制代码


其实最核心的,就是这一行
  1. result += n /= 5;
复制代码
搞清楚算法的思路,上面这行代码就能搞明白了
1.明确两点:
A从[1,N]中,有大约一半是偶数(能被2整除)
B末尾为零,只能是乘以10,而10只能是2*5,所以,这个问题等价于找到N!里有多少个因子5

任意小于N的数,能被5整除的话,一定存在下述关系:
N>=5*M(M=1,2,3...)
那好了,M的最大值=(int)N/5
于是得到一个数列:1,2,3,4... ... M
这个数列就是含有至少一个5的所有因数

然后,再从这个数列中找含有一个5的所有因数(实际上是找含有5*5的所有因数)得到一个新的数列:1,2,3... ...(int)N/25

以此类推,可以得到含有最多个5的数,所以要反复的除以5,于是便得到了这行代码
n /= 5
每次得到的数列项数累加:便有了result += n /= 5;

OK,这个算法本身没有问题,但是上面的代码并非完美,当N足够大时,由于N/5直接取整,反复的取整之后,丢失的余数累计会超过5,于是,会造成丢失若干“边界值”,那么最终得到的结果会偏小,如Integer.MAX_VALUE,就会丢失5个这样的边界值,只要对上面的代码略加修改便可:
  1.         public static int countZero(int n)
  2.         {
  3.                 int result = 0;
  4.                 int temp = 5;
  5.                 while (0 < temp && temp <= n)
  6.                 {
  7.                         result += n / temp;
  8.                         temp *= 5;
  9.                 }
  10.                 return result;
  11.         }
复制代码





0 个回复

您需要登录后才可以回帖 登录 | 加入黑马