N的阶乘末尾0的个数和其二进制表示中最后位1的位置

N的阶乘末尾0的个数和其二进制表示中最后位1的位置


问题一解法:
    我们知道求N的阶乘结果末尾0的个数也就是说我们在从1做到N的乘法的时候里面产生了多少个10,
我们可以这样分解,也就是将从0到N的数分解成因式,再将这些因式相乘,那么里面有多少个10呢?
其实我们只要算里面有多少个5就可以了?
    因为在这些分解后的因子中,能产生10的可只有5和2相乘了,由于2的个数是大于5的个数的,因此
我们只要算5的个数就可以了。那么这个题目就是算这些从1到N的数字分解成因子后,这些因子里面
5的个数。

  Python代码
  1. def factorialnumberofzero(v_value):
  2. countoffive = 0
  3. for num in range(1, v_value + 1):
  4. value = num
  5. while ((value % 2) == 0) and value:
  6. value /= 2
  7. countoffive += 1
  8. print countoffive
  9. return countoffive




问题二的解法:
    那么我们如何思考这个问题呢?
    其实很简单,我们只要算它的结果是2的多少幂的倍数就行了,假如结果是8,那么8是2的3次幂,也就是说8的最后一个1在倒数第4位。
那么如何算N!是2的多少次幂呢?
    当然我们只要算在乘的时候有从少个2相乘就可以了,还是和第一题那样分解因子相乘啊,看因子里总的2的个数。但是有没有简单的方法?
    当然有
    我们看下10! ,那么10!到底有多少个2呢?
        呵呵,首先我们将10/2=5 也就是从10到1中有5个偶数
        10、8、6、4、2
        有多少个偶数肯定有多少个2啦,然后我们将它们除以2
        5、4、3、2、1
        这5个数里面又有5/2=2个偶数。
        4、2
        我们将4、2除以2,得到
        2、1
        里面有一个2/1=1个偶数。
        2
        2/2=1  就没有了。

看算法:
    
  1. def factorialpositionoflastone(v_value):
  2. positioncount = 0
  3. while v_value:
  4. v_value >>=1
  5. positioncount += v_value
  6. print positioncount
  7. return positioncount

     


    
    
上一篇:【转】Visio绘制WEB流程图的心得


下一篇:LightOj 1138 - Trailing Zeroes (III) 阶乘末尾0的个数 & 二分