编程之美笔记 2.2不要被阶乘吓倒(乘法结果中末尾0的个数,二进制表示中最低位1的位置)

2805阅读 0评论2012-03-22 developinglife
分类:C/C++

Q:

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

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

A:

1

考虑哪些数相乘能得到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

问题转化为求N!因式分解中5的指数。

int countZero(int N)

{

         int ret = 0;

         int j;

         for(int i=1; i<=N; i++)

         {

                   j = i;

                   while(0==j%5)

                   {

                            ret++;

                            j /= 5;

                   }

         }

         return ret;

}

解法2

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

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

int countZero(int N)

{

         int ret = 0;

         while(N)

         {

                   ret += N/5;

                   N /= 5;

         }

         return ret;

}

2

把一个二进制除以2的过程如下:

判断最后一个二进制是否为0:若为0将二进制数右移1位,即为商;若为1,则说明这个数是奇数,不能被2整除。

所以判断N!的二进制表示中最低位为1的位置的问题可以转换为求N!中含有质因数2的个数的问题。即位置为N!含有质因数2的个数加1.

解法1

N!中含有质因数2的个数等于:[N/2]+[N/4]+[N/8]+…

int lowestOne(int N)

{

         int ret = 1;

         while(N)

         {

                   N >>= 1;

                   ret += N;

         }

         return ret;

}

解法2

N!中含有质因数2的个数等于N减去N的二进制表示中1的数目。

以下为规律的推导:N!中含有2的质因数的个数等于[N/2]+[N/4]+[N/8]+…

对于11011即:1101+110+11+1 = (1000+100+1) + (100+10) + (10+1) + 1=

1000+100+10+1 + 100+10+1 + 1= 1111+111+1 = 10000-1 + 1000-1 + 10-1 + 1-1=

11011-(N的二进制表示中含有1的个数)

上一篇:编程之美笔记 2.1 求二进制数中的1的个数(两数不同位或相同位的个数)
下一篇:编程之美笔记 2.3 寻找发帖“水王”(数组中出现次数过半的元素)