求100！中尾后包含多少个零。

         原题并未让我们算出100！的结果，只需要算出尾后0的个数就行了，这是走向正确之路的第一步。
其次，我们能知道尾后出现一个零，即10必定是这个数的因子，尾后有多少个零就意味着能整除10多少次。
10=2*5，而100=1*2*3*4*。。。*100，其中2必定比5多，问题就变成了100！能整除5多少次。
次数不需要求出100！是多少，只要把1-100能整除5的次数加起来即可。

 

public class TailsZero {
  public static void main(String[] args) {
    int sum = 0;
    for (int i = 5; i <= 10000; i+=5) {
      int count = getDivisorCount(i, 5);
      sum += count;
    }

    System.out.println("100阶乘尾后0的个数为：" + sum);
  }  

  /**
   * 遞歸方式版本
   * 取得除数在被除数中的可整除次数，如5在25中的可整除个数为2
   * @param Dividend 被除数
   * @param divisor 除数
   * @return
   */
  public static int getDivisorCount(int Dividend, int divisor) {
    if (Dividend == 0) {
      return 0;
    }

    int count = 0;

    if (Dividend % divisor == 0) {
      count = 1;
      count += getDivisorCount(Dividend / divisor, divisor);
    }

    return count;
  }
  
  /**
   * 非遞歸方式版本
   * 取得除数在被除数中的可整除次数，如5在25中的可整除个数为2
   * @param Dividend 被除数
   * @param divisor 除数
   * @return
   */
  public static int getDivisorCount2(int Dividend, int divisor) {
    int count = 0;
    int oldDivisor=divisor;

    while (Dividend % divisor == 0) {
      count ++;
      divisor*=oldDivisor;
    }

    return count;
  }

}

 

评论

1 楼 chinsans 2010-07-17  

恩 恩