c++算法阶乘N！



问题描述

1、给定一个整数N，阶乘N！末尾有多少个0

2、求N！的二进制表示中最低位1的位置

1、给定一个整数N，阶乘N！末尾有多少个0

举例：10！＝3 628 800，则 N！的末尾有两个0

思路：

即，知道 Z ，就知道N！中含有0的个数

方法一：求出1~N中每一个数被5整除的因子的个数，比较笨

代码：

 

  1. //统计 1-N 中被5整除的因子的总个数
  2. int FindZeroNum(int N)
  3. {
  4.     int nCount = 0;
  5.     for (int i = 5;i < N + 1;i++)
  6.     {
  7.         int nCur = i;
  8.         while(nCur % 5 == 0)//统计nCur中被5整除的因子的个数，即有几个5
  9.         {
  10.             nCount++;
  11.             nCur /= 5;
  12.         }
  13.     }
  14.     return nCount;
  15. }

 

方法二：


举例：N = 25 ，即1~25

5的倍数(5,10,15,20,25)贡献一个5

25的倍数贡献一个5

虽然25可以贡献两个5，但是已经在5的倍数中贡献一次了，所以这里就统计一次

也就是说，对于每一个5 ^M,N只统计一次5，虽然它本身有多个5的质因数，但是已经在前面M-1计算过，所以只需统计一次即可

代码

 

  1. int FindZeroNum(int N)//每次迭代，就求出多少个5^M贡献5
  2. {
  3.     int nCount = 0;
  4.     while(N)
  5.     {
  6.         N = N / 5; //1-N能奉献多少个5
  7.         nCount += N;
  8.     }
  9.     return nCount;
  10. }

 

2、求N!的二进制表示中最低位1的位置

举例：N = 3，N！ = 6，6的 二进制1010 最低位1在第二位

问题分析

方法一：


代码

 

  1. int FindLowestOne(int nNum)
  2. {
  3.     assert(nNum > 0);
  4.     int nCount = 0;
  5.     int N = nNum;
  6.     while(N)
  7.     {
  8.         N = N >> 1;
  9.         nCount += N;
  10.     }
  11.     return nCount + 1;
  12. }

 

代码说明：

假设是8! 有1 2 3 4 5 6 7 8

第一次循环： 则它有 2 4 6 8四个具有2的质因数

第二次循环： 2 4 6 8变为 1 2 3 4 则只有 2 4具有2的质因数

第三次循环：2 4 变为 1 2 则只有2 具有2的质因数

方法二：


代码

 

  1. /*nNum的二进制中包含1的个数*/
  2. int FindOneNum(int nNum)
  3. {
  4.     int nCount = 0;
  5.     while(nNum)
  6.     {
  7.         nCount++;
  8.         nNum = nNum & (nNum - 1);
  9.     }
  10.     return nCount;
  11. }
  12. /*nNum中最低1的位置*/
  13. int FindLowestOne(int nNum)
  14. {
  15.     assert(nNum > 0);
  16.     return nNum - FindOneNum(nNum) + 1;
  17. }

 

思考题

给定正整数N，判断其是否为2的方幂

问题等价于：判断 N 的二进制表示中是否只有一位为1

方法：

  1. 即为判断条件：N >0 且 N & (N-1) = 0