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

jerryxjr1220

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

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

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

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

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

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

jerryxjr1220

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

1. a = [1,6,5,9,8,11,15]
   
2. b = [2,6,5,7,3,10,8]
   
3. a.sort(reverse=True)
   
4. b.sort(reverse=True)
   
5. c = []
   
6. for i in range(7):
   
7.         if a[i]>=b[0]:
   
8.                 c.append(b.pop())
   
9.         else:
   
10.                 c.append(b.pop(0))
    
11. print 'Qi Wei Wang: \t' + str(a)
    
12. print 'Tian Ji:  \t' + str(c)
    
13. win,lose = 0,0
    
14. for i in range(7):
    
15.     if a[i] < c[i]:
    
16.         win += 1
    
17.     else:
    
18.         lose += 1
    
19. 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

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

复制代码

jerryxjr1220

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

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

jerryxjr1220

解答更新完成

panda小正太

谢谢楼主！

Jonin616

1. #小练习017 田忌赛马
   
2. 
   
3. def race():
   
4.     a = [15,11,9,8,6,5,1]
   
5.     b = [10,8,7,6,5,3,2]
   
6. 
   
7.     winer = []
   
8.     loser = []
   
9. 
   
10.     turnTorace = []
    
11.    
    
12.     for each_a in a:
    
13.         for each_b in b:
    
14.             if each_b > each_a:
    
15.                 winer.append(each_b)
    
16.             else:
    
17.                 loser.append(each_b)
    
18.         if len(winer):
    
19.             turnTorace.append(winer[len(winer) - 1])
    
20.             b.remove(winer[len(winer) - 1])
    
21.         else:
    
22.             turnTorace.append(loser[len(loser) - 1])
    
23.             b.remove(loser[len(loser) - 1])
    
24.         winer.clear()
    
25.         loser.clear()
    
26. 
    
27.     print(turnTorace)

复制代码

余欲渔

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

复制代码

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

复制代码

余欲渔

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

776667

1. def horse_match(tian,king):
   
2.     match_list = []
   
3.     tian,king = sorted(tian),sorted(king)
   
4.     win_point = 0
   
5.     while king:
   
6.         i = min(king)
   
7.         for j in tian:
   
8.             if j > i:
   
9.                 match_list.append('齐威王%s vs 田忌%s'%(i,j))
   
10.                 king.remove(i)
    
11.                 tian.remove(j)
    
12.                 win_point += 1
    
13.                 break
    
14.         else:
    
15.             match_list.append('齐威王%s vs 田忌%s'%(i,min(tian)))
    
16.             king.remove(i)
    
17.             tian.remove(min(tian))
    
18.     for n in match_list:
    
19.         print(n)
    
20.     if win_point >= 4:
    
21.         print('田忌胜')
    
22.     else:
    
23.         print('齐威王胜')
    
24. 
    
25. if __name__ == '__main__':
    
26.     horse_match([10,8,7,6,5,3,2],[15,11,9,8,6,5,1])

复制代码

qaz123765

1. a= [1,6,5,9,8,11,15]
   
2. b = [2,6,5,7,3,10,8]
   
3. 
   
4. a.sort(reverse=True)
   
5. b.sort(reverse=True)
   
6. c=[]
   
7. 
   
8. k=0
   
9. j=0
   
10. while j<7:
    
11.     if b[k]<a[j]:
    
12.         c.append(a[j])
    
13.         bp=b.pop()
    
14.         c.append(bp)
    
15.         j+=1
    
16.     else:
    
17.         c.append(a[j])
    
18.         c.append(b[k])
    
19.         j+=1
    
20.         k+=1
    
21.         
    
22. print(c)

复制代码

shigure_takimi

1. 
   
2. # 用田忌的最烂的3匹马对阵齐威王最好的3匹马，用较好的4匹马依次对阵齐威王较劣的4匹马。
   
3. # 如果能获胜就输出，否则就是无法获胜。这个思路不知道算不算也是一种解法。
   
4. 
   
5. a = [15,11,9,8,6,5,1]  #  齐威王的马的列表
   
6. b = [10,8,7,6,4,3,2]  #  田忌的马的候选表
   
7. 
   
8. def toWin(a, b):
   
9.     length = len(a)
   
10.     a = sorted(a, reverse = True)
    
11.     b = sorted(b, reverse = True)
    
12.     b = b[-1:-(length//2+1):-1]+b[:length//2+1]
    
13.     count = 0
    
14.     for i in range(length):
    
15.         if b[i] > a[i]:
    
16.             count += 1
    
17.     if count > length//2:
    
18.         print(b)
    
19.     else:
    
20.         print('无法获胜。')
    
21. 
    
22. toWin(a,b)

复制代码

shmzfeng

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

1. #!/user/bin/python
   
2. # -*- coding=UTF-8 -*-
   
3. a = [1,6,5,9,8,11,15]
   
4. b = [2,6,5,7,3,10,8]
   
5. a.sort(reverse=True) # 从大到小倒叙排列 [15, 11, 9, 8, 6, 5, 1]
   
6. b.sort(reverse=True)
   
7. c = []
   
8. for i in range(7):
   
9.         if a[i]>b[0]:
   
10.                 c.append(b.pop())
    
11.         else:
    
12.                 c.append(b.pop(0))
    
13. print '齐威王: \t' + str(a)
    
14. print '田忌:  \t' + str(c)
    
15. win,lose,equal = 0,0,0
    
16. for i in range(7):
    
17.     if a[i] < c[i]:
    
18.         win += 1
    
19.     elif a[i] == c[i]:
    
20.         equal+=1
    
21.     else:
    
22.         lose += 1
    
23. 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')