阶乘是个很有意思的东西,可能很多朋友看到关于他的计算就怕了,其实没什么,看完下面两个问题您应该有低了。
1. 给定一个 N ,求出N!末尾有多少个零,比如 N=10,N!=3628800,N!末尾有两个零。
2. 求N!的二进制表示中最低为1的位置,比如 11010010, 最低为1的位置为2。
问题一解法:
在上一个 blog 中介绍的子数组乘积最大值的问题中,有朋友考虑到溢出的问题,在这个问题中,我们从那些数相乘能得到10这个命题开始思考。比如N!=K×10m那么N!后面就有m个零。这个问题转化为将N!进行分解,如N!=2a×3b×5c 很显然 10=2×5,那么零的个数m=min(a,c), 一个数能够被2整除的机率比5要大很多因此 m=c,因此转化为求 c的问题,具体算法如:问题二解法:
1publicclass factorial {我们都知道一个数除以2可以表示为 N>>1,即向右移动一位。这个问题转化为求 N! 含有2的质因数的个数问题。完整程序:
1 staticclass PrimeFactor {1package org.blogjava.arithmetic;
本文来自:http://www.blogjava.net/Jack2007/archive/2008/10/18/235152.html