鱼C论坛

 找回密码
 立即注册
查看: 7894|回复: 15

[技术交流] python小练习(017):田忌赛马

[复制链接]
发表于 2016-11-22 09:01:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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

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

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

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

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

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

评分

参与人数 1鱼币 +5 收起 理由
SixPy + 5 热爱鱼C^_^

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-11-22 09:14:39 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2016-11-22 21:30 编辑

解答:(还是用了动态规划的思路:依次和齐威王的最强马进行比较,如果田忌的最强马大过齐威王的最强马就对阵,如果比不过,就用最差马对阵,保留优势马。)
  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
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-11-22 10:00:47 | 显示全部楼层
可能之前的小练习难度有点高,参与的人不是很积极。

难度并不高~
只是你的题目千篇一律~ 都是遍历型C风格代码。
也许是你从vb转过来时带来的习惯~
要充分利用python的特性,写一些简洁高效的代码~
同时分析算法的核心思想~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

嗯,有道理。
可能跟我个人兴趣也有些关系,比如说一些数学问题的解法或算法,还有自己行业(医药)关注的一些方面的东西。
下次找一些更有趣的题目或者更贴近大家使用的一些小项目。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-11-22 11:01:44 | 显示全部楼层
  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. print(b)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-11-22 11:10:10 | 显示全部楼层

如果列表很长,会不会影响效率?
还有如果我想尽可能赢的局数多,应该怎么优化?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-11-22 21:31:03 | 显示全部楼层
解答更新完成
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-3 10:55:48 | 显示全部楼层
谢谢楼主!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-9 02:47:59 | 显示全部楼层
  1. #小练习017 田忌赛马

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

  5.     winer = []
  6.     loser = []

  7.     turnTorace = []
  8.    
  9.     for each_a in a:
  10.         for each_b in b:
  11.             if each_b > each_a:
  12.                 winer.append(each_b)
  13.             else:
  14.                 loser.append(each_b)
  15.         if len(winer):
  16.             turnTorace.append(winer[len(winer) - 1])
  17.             b.remove(winer[len(winer) - 1])
  18.         else:
  19.             turnTorace.append(loser[len(loser) - 1])
  20.             b.remove(loser[len(loser) - 1])
  21.         winer.clear()
  22.         loser.clear()

  23.     print(turnTorace)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-9 10:09:37 | 显示全部楼层
本帖最后由 余欲渔 于 2017-2-9 10:21 编辑
  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. >>>
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-9 10:21:06 | 显示全部楼层
本来也想着引入C列,觉得每次把最后面的挪到前面来,比一轮大小。不过感觉列表很大的时候引入C列效率会高很多
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-18 10:17:03 | 显示全部楼层
  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. if __name__ == '__main__':
  25.     horse_match([10,8,7,6,5,3,2],[15,11,9,8,6,5,1])
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-6-9 16:10:21 From FishC Mobile | 显示全部楼层
本帖最后由 qaz123765 于 2017-6-9 22:27 编辑
  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. k=0
  7. j=0
  8. while j<7:
  9.     if b[k]<a[j]:
  10.         c.append(a[j])
  11.         bp=b.pop()
  12.         c.append(bp)
  13.         j+=1
  14.     else:
  15.         c.append(a[j])
  16.         c.append(b[k])
  17.         j+=1
  18.         k+=1
  19.         
  20. print(c)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-1-17 12:40:51 | 显示全部楼层

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

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

  5. def toWin(a, b):
  6.     length = len(a)
  7.     a = sorted(a, reverse = True)
  8.     b = sorted(b, reverse = True)
  9.     b = b[-1:-(length//2+1):-1]+b[:length//2+1]
  10.     count = 0
  11.     for i in range(length):
  12.         if b[i] > a[i]:
  13.             count += 1
  14.     if count > length//2:
  15.         print(b)
  16.     else:
  17.         print('无法获胜。')

  18. toWin(a,b)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-2-15 19:36:53 | 显示全部楼层
感觉应该有平一局 稍微修改了一点点代码
  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)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-11-20 11:53:49 | 显示全部楼层
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')
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 02:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表