用Python写田忌赛马算法

田忌赛马问题是一道经典的算法问题，下面是使用Python实现田忌赛马的代码：

def cmp(a, b):
    if a > b:
        return 1
    elif a < b:
        return -1
    else:
        return 0

def tianji_saiche(tian, qi):
    n = len(tian)
    tian.sort()
    qi.sort()

    win = 0
    lt, rt = 0, n - 1
    for i in range(n):
        if cmp(tian[lt], qi[i]) == 1:
            win += 1
            lt += 1
        else:
            rt -= 1
    return win

tian = [2, 3, 4, 5, 6, 7, 8, 9]
qi = [1, 2, 3, 4, 5, 6, 7, 8]
print(tianji_saiche(tian, qi)) # 4

在这个代码中，我们首先定义一个比较函数`cmp`，用于比较两个数字的大小。然后我们对田忌和齐王的马进行排序，从小到大进行比较。如果田忌的马可以赢过齐王的马，则选择田忌的最差的马与齐王的马比赛，否则选择田忌的最好的马与齐王的马比赛。最后返回田忌能够赢得的马的数量。

在这个例子中，田忌的马的速度从2到9不等，齐王的马的速度从1到8不等，我们期望田忌能够赢得4匹马。