1，最大公约数问题解法三：已知x，y，求出他们的最大公约数。
     对于y和x来说，如果y=k*y1，x=k*x1。那么就有f(y,x)=k*f(y1,x1)。
     另外，如果x=p*x1，假设p是素数，并且ｙ％ｐ！＝０（即ｙ不能被ｐ整除），那么f(x,y)=f(p*x1,y)=f(x1,y)。
     最简单的方法就是取p=2。
     若x，y都是偶数，则直接右移一位，得到子问题，原问题的解将是子问题的2倍；
     若x，y中一个偶数，一个奇数，则将偶数直接右移一位，原问题的解等价于子问题的解；
     若x，y都是奇数，则采用减法（即辗转相除法的原理）将问题化解为一奇一偶。
2，求二进制数中1的个数。这是一个看起来简单的问题，本书中有个比较精妙的做法。
     解法三：第一个思想是：采用位运算，不用除法和取模运算
                第二个思想是：假设数种有M个1，则只需要做M次运算
     代码如下：
     int Count(int v){
        int num = 0;
        while(v){
            v&=(v-1);
            num++;
        }
    }
3，N！的问题：问题1：N！的末尾有多少个0（因子5的个数）。问题2：N！的末尾最开始的一个1是第几位（二进制表示时）？

posted on 2008-05-08 16:21  珂儿  阅读(372)  评论()    收藏  举报