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)