python小练习（017）：田忌赛马

jerryxjr1220

前两天的python小练习讲解了用爬虫抓取一些数据和信息的例子，传送门

可能之前的小练习难度有点高，参与的人不是很积极。

那么接下来的小练习会降低点难度，讲解一些有趣的python应用的例子，比如：田忌赛马

这题也是华为面试时候的机试题：

“ 广义田忌赛马：每匹马都有一个能力指数，齐威王先选马（按能力从大到小排列），田忌后选，马的能力大的一方获胜，若马的能力相同，也是齐威王胜（东道主优势）。”
例如：
齐威王的马的列表 a = [15,11,9,8,6,5,1]
田忌的马的候选表 b = [10,8,7,6,5,3,2]

如果你是田忌，如何在劣势很明显的情况下，扭转战局呢？
请用python写出解法，输出田忌的对阵列表 c及最终胜败的结果

jerryxjr1220

解答：（还是用了动态规划的思路：依次和齐威王的最强马进行比较，如果田忌的最强马大过齐威王的最强马就对阵，如果比不过，就用最差马对阵，保留优势马。）

a = [1,6,5,9,8,11,15]
b = [2,6,5,7,3,10,8]
a.sort(reverse=True)
b.sort(reverse=True)
c = []
for i in range(7):
        if a[i]>=b[0]:
                c.append(b.pop())
        else:
                c.append(b.pop(0))
print 'Qi Wei Wang: \t' + str(a)
print 'Tian Ji:  \t' + str(c)
win,lose = 0,0
for i in range(7):
    if a[i] < c[i]:
        win += 1
    else:
        lose += 1
print 'Tian Ji wins :' + str(win) + ' loses :' + str(lose)

输出：
Qi Wei Wang:    [15, 11, 9, 8, 6, 5, 1]
Tian Ji:        [2, 3, 10, 5, 8, 7, 6]
Tian Ji wins :4 loses :3

SixPy

可能之前的小练习难度有点高，参与的人不是很积极。

难度并不高~
只是你的题目千篇一律~ 都是遍历型C风格代码。
也许是你从vb转过来时带来的习惯~
要充分利用python的特性，写一些简洁高效的代码~
同时分析算法的核心思想~

jerryxjr1220

SixPy 发表于 2016-11-22 10:00
难度并不高~
只是你的题目千篇一律~ 都是遍历型C风格代码。
也许是你从vb转过来时带来的习惯~

嗯，有道理。
可能跟我个人兴趣也有些关系，比如说一些数学问题的解法或算法，还有自己行业（医药）关注的一些方面的东西。
下次找一些更有趣的题目或者更贴近大家使用的一些小项目。

SixPy

import numpy as np
a = np.array([15,11,9,8,6,5,1])
b = np.array([10,8,7,6,5,3,2])
while ((b - a)>0).sum()<4: # >0 表示 胜出， 只有多于3匹马胜出才算 获胜。
    np.random.shuffle(b) # 将田纪的马随机排列一次

print(b)

jerryxjr1220

SixPy 发表于 2016-11-22 11:01

如果列表很长，会不会影响效率？
还有如果我想尽可能赢的局数多，应该怎么优化？

jerryxjr1220

解答更新完成

panda小正太

谢谢楼主！

Jonin616

#小练习017 田忌赛马

def race():
    a = [15,11,9,8,6,5,1]
    b = [10,8,7,6,5,3,2]

    winer = []
    loser = []

    turnTorace = []
    
    for each_a in a:
        for each_b in b:
            if each_b > each_a:
                winer.append(each_b)
            else:
                loser.append(each_b)
        if len(winer):
            turnTorace.append(winer[len(winer) - 1])
            b.remove(winer[len(winer) - 1])
        else:
            turnTorace.append(loser[len(loser) - 1])
            b.remove(loser[len(loser) - 1])
        winer.clear()
        loser.clear()

    print(turnTorace)

余欲渔

a=[15,11,9,8,6,5,1]
b=[10,8,7,6,5,3,2]
l=len(a)
while True:
    x=0
    b=b[len(b)-1:]+b[:len(b)-1]
    for i in range(l):
        if b[i]>a[i]:
            x+=1
    if x>l/2:
        break
print(a)
print(b)
print(x)

== RESTART: C:/Users/ASUS/AppData/Local/Programs/Python/Python35-32/田忌赛马.py ==
[15, 11, 9, 8, 6, 5, 1]
[3, 2, 10, 8, 7, 6, 5]
4
>>> 

余欲渔

本来也想着引入C列，觉得每次把最后面的挪到前面来，比一轮大小。不过感觉列表很大的时候引入C列效率会高很多

776667

def horse_match(tian,king):
    match_list = []
    tian,king = sorted(tian),sorted(king)
    win_point = 0
    while king:
        i = min(king)
        for j in tian:
            if j > i:
                match_list.append('齐威王%s vs 田忌%s'%(i,j))
                king.remove(i)
                tian.remove(j)
                win_point += 1
                break
        else:
            match_list.append('齐威王%s vs 田忌%s'%(i,min(tian)))
            king.remove(i)
            tian.remove(min(tian))
    for n in match_list:
        print(n)
    if win_point >= 4:
        print('田忌胜')
    else:
        print('齐威王胜')

if __name__ == '__main__':
    horse_match([10,8,7,6,5,3,2],[15,11,9,8,6,5,1])

qaz123765

a= [1,6,5,9,8,11,15]
b = [2,6,5,7,3,10,8]

a.sort(reverse=True)
b.sort(reverse=True)
c=[]

k=0
j=0
while j<7:
    if b[k]<a[j]:
        c.append(a[j])
        bp=b.pop()
        c.append(bp)
        j+=1
    else:
        c.append(a[j])
        c.append(b[k])
        j+=1
        k+=1
        
print(c)

shigure_takimi

# 用田忌的最烂的3匹马对阵齐威王最好的3匹马，用较好的4匹马依次对阵齐威王较劣的4匹马。
# 如果能获胜就输出，否则就是无法获胜。这个思路不知道算不算也是一种解法。

a = [15,11,9,8,6,5,1]  #  齐威王的马的列表 
b = [10,8,7,6,4,3,2]  #  田忌的马的候选表

def toWin(a, b):
    length = len(a)
    a = sorted(a, reverse = True)
    b = sorted(b, reverse = True)
    b = b[-1:-(length//2+1):-1]+b[:length//2+1]
    count = 0
    for i in range(length):
        if b[i] > a[i]:
            count += 1
    if count > length//2:
        print(b)
    else:
        print('无法获胜。')

toWin(a,b)

shmzfeng

感觉应该有平一局 稍微修改了一点点代码

#!/user/bin/python
# -*- coding=UTF-8 -*-
a = [1,6,5,9,8,11,15]
b = [2,6,5,7,3,10,8]
a.sort(reverse=True) # 从大到小倒叙排列 [15, 11, 9, 8, 6, 5, 1]
b.sort(reverse=True)
c = []
for i in range(7):
        if a[i]>b[0]:
                c.append(b.pop())
        else:
                c.append(b.pop(0))
print '齐威王: \t' + str(a)
print '田忌:  \t' + str(c)
win,lose,equal = 0,0,0
for i in range(7):
    if a[i] < c[i]:
        win += 1
    elif a[i] == c[i]:
        equal+=1
    else:
        lose += 1
print '田忌赢 :' + str(win) + ' 平：'+str(equal)+ ' 输 :' + str(lose)

gonorth

a = [1,6,5,9,8,11,15] # king
b = [2,6,5,7,3,10,8]  # general
a.sort(reverse= True)
b.sort(reverse= True)
# print (a,b, sep= '\n')

for i in range (len(a)):
    if a[i] > b[i]:
        temp = b.pop()
        b.insert(0,temp)

print (a,b,sep='\n')
count = 0
for i in range (len(a)):
    if a[i] > b[i]:
        count += 1
    if a[i] < b[i]:
        count -= 1
print (count)
if count > 0:
    print ("king is the winner")
elif count == 0:
    print ('win-win')
else:
    print ('general is the winner')