先选先赢问题

一，问题描述

说有偶数个数字，alex和lee两个人比赛，每次轮流从第一个数字或最后一个数字中拿走一个（偶数个数字，所以他俩拿的数字个数相同），最后比谁拿的数字总和大。题目是让我们设计一个算法，对于任意给定的一系列数字，判断如果alex先选，是否一定赢（所有数加起来是奇数，所以不存在平局）？比如有，

[4,3,5,9,11,6,2,1]
alex拿掉开头的4，剩下，

[3,5,9,11,6,2,1]
lee再拿掉开头的3，剩下

[5,9,11,6,2,1]
以此类推。

二，问题分析

首先这里问的是“是否一定赢”，我先举个反例，[4,4,6,8,2,3]，这个先选序列是[4,6,3]，后选是[4，8，2]，后面讨论胜率问题。

三，实验

就随便写一写直接贴代码吧：

 1 import random
 2 import datetime
 3 import matplotlib.pyplot as plt
 4 
 5 starttime = datetime.datetime.now()
 6 lenth_list = 10
 7 iterations = 100
 8 
 9 A,L = 0,0
10 x = []
11 winrate = []
12 for n in range(1,101):
13     x.append(n*iterations)
14     for i in range(0,n*iterations):
15 
16         list = []
17         for i in range(0, lenth_list):
18             n = random.randint(0, lenth_list)
19             list.append(n)
20         # print(list)
21 
22         Alex = []
23         Lee = []
24 
25         while len(list) > 0:
26             min_num = 0
27             max_num = len(list)-1
28             #print(max_num)
29             if list[min_num] > list[max_num]:
30                 #print("Alex")
31                 Alex.append(list[min_num])
32                 list.remove(list[min_num])
33             else:
34                 Alex.append(list[max_num])
35                 list.remove(list[max_num])
36 
37             #print("changdu",len(list))
38 
39             if list[min_num] > list[max_num-1]:
40                 Lee.append(list[min_num-1])
41                 list.remove(list[min_num-1])
42                 #print("Lee")
43             else:
44                 Lee.append(list[max_num-1])
45                 list.remove(list[max_num-1])
46         if sum(Alex) > sum(Lee):
47             A = A + 1
48         else:
49             L = L + 1
50         print(sum(Alex),sum(Lee))
51     #print("The win-rate of second man:",L/(A+L)*100,"%")
52     winrate.append(L/(A+L)*100)
53 print(x)
54 print(winrate)
55 print(len(winrate))
56 endtime = datetime.datetime.now()
57 print (endtime - starttime)
58 
59 plt.plot(x, winrate, label='First choose first win')
60 #plt.plot(x2, y2, label='Second Line')
61 plt.xlabel('Iterations')  #横坐标标题
62 plt.ylabel('Winrate for second man')  #纵坐标标题
63 #plt.title('Interesting Graph
Check it out',loc="right")   #图像标题
64 #plt.title('Interesting Graph
Check it out')
65 plt.legend()    #显示Fisrt Line和Second Line（label）的设置
66 plt.savefig('C:/Users/zhengyong/Desktop/1.png')
67 plt.show()

图示：

四，结论

这是我在知乎看到的一个问题，这里之所以把这个问题拿出来讲呢，是因为我认为先选不一定先赢（虽然赢面很大），所以特地用生成随机数的方法去验证了一下，发现确实不上先选的一定赢，这里根据长度为10的数组分别迭代100到10000次得到相应的数据，发现，第二个人还是有赢面的，基本稳定在5.5%左右。