淘先锋技术网

首页 1 2 3 4 5 6 7

2.5 寻找最大的K个数

题意:无序的不相等的N个数,选出其中最大的若干个数。

看到这道题,笔者首先想到的就是堆排序,堆排序的特性使得其非常适合于这个问题。

书中解法四用到的就是堆排序算法,这个算法只需要扫描数据一次,而且仅占用K个数的空间,其他算法都无以匹敌。

大学的数据结构中都会讲到堆排序,其也是二分思想的一个经典应用。

2.6 精确表达浮点数

题意:给定一个有限小数,或者无限循环小数,求其分数表达形式。

这道题使笔者想起了很早就学过的一个证明,即证明0.999999999……等于1。

解此题的方法就是用了上面的证明的方法,具体的证明过程也不难,无非就是通过缩放的方法消去循环节。

而有限的小数直接可以表示为分数形式的,只是得做下化简的工作罢了(分子分母同时除以它们的最大公约数)。

2.7 最大公约数问题

题意:求两个数的最大公约数。

解法一,经典的辗转相除法,其实方法还是挺好的,不过后面给出不用除法的方法,也是比较有趣味的。

解法二用的是减法,虽说没用除法,但是这个效率并不见得高,因为减法一次减去的量有点少,这样迭代的次数就会明显增多。

解法三的思想是,从奇偶性出发,分为若干种情况分别讨论,复杂度明显降低。

但是,这种方法的分类有点繁琐,我们可以简化一下。

首先我们可以发现,两个数同时为偶数的情况只可能在参数刚开始传入的时候发生,一旦出现两个数不同为偶数,后面也不再会出现这种情况,所以我们可以在起始的时候先处理掉这个情况。

现在只有都为奇数和之一为奇数的情况,这里我们也只需要判断两次就可以了。

def gcd_step1(x, y):
    i = 0
    while (x|y)&1 == 0:
        i += 1
        x >>= 1
        y >>= 1
    return i

def gcd_step2(x, y):
    if x < y: return gcd_step2(y, x)
    if y == 0: return x
    if x&y&1: return gcd_step2(y, x - y)
    if x&1: return gcd_step2(x, y >> 1)
    return gcd_step2(x >> 1, y)

def gcd(x, y):
    i = gcd_step1(x, y)
    return gcd_step2(x >> i, y >> i) << i

if __name__ == '__main__':
    print gcd(100, 64)

 

 

转载于:https://www.cnblogs.com/xcoder/archive/2012/11/05/2755821.html