赛马排序

aimisiyou 发表于 2021-3-19 15:52:05

有36匹马6个跑道，一次可选取6匹马进行比赛排名，用最少比赛次数算出跑最快的前6匹马？

northwolves 发表于 2021-3-20 19:09:48

将36匹马均分为 ABCDEF 6组，各组先跑一次排个序，假设为
A1B1C1D1E1F1
A2B2C2D2E2F2
A3B3C3D3E3F3
A4B4C4D4E4F4
A5B5C5D5E5F5
A6B6C6D6E6F6

各组冠军再跑一次，不妨设顺序就是A1 B1 C1 D1 E1 F1的顺序，现在已经跑了7轮，冠军=A1，亚军∈{B1, A2}，季军∈{B1, A2, C1, B2, A3}.
依次类推，前六名只在左上三角形区里，21匹马。除去冠军A1，还剩20匹。
编了个代码跑了一下，最终排名一共159种，亚军A2有50种可能，B1有109种可能。
1 A1 A2 A3 A4 A5 A6
2 A1 A2 A3 A4 A5 B1
3 A1 A2 A3 A4 B1 A5
4 A1 A2 A3 A4 B1 B2
5 A1 A2 A3 A4 B1 C1
6 A1 A2 A3 B1 A4 A5
7 A1 A2 A3 B1 A4 B2
8 A1 A2 A3 B1 A4 C1
9 A1 A2 A3 B1 B2 A4
10 A1 A2 A3 B1 B2 B3
11 A1 A2 A3 B1 B2 C1
12 A1 A2 A3 B1 C1 A4
13 A1 A2 A3 B1 C1 B2
14 A1 A2 A3 B1 C1 C2
15 A1 A2 A3 B1 C1 D1
16 A1 A2 B1 A3 A4 A5
17 A1 A2 B1 A3 A4 B2
18 A1 A2 B1 A3 A4 C1
19 A1 A2 B1 A3 B2 A4
20 A1 A2 B1 A3 B2 B3
21 A1 A2 B1 A3 B2 C1
22 A1 A2 B1 A3 C1 A4
23 A1 A2 B1 A3 C1 B2
24 A1 A2 B1 A3 C1 C2
25 A1 A2 B1 A3 C1 D1
26 A1 A2 B1 B2 A3 A4
27 A1 A2 B1 B2 A3 B3
28 A1 A2 B1 B2 A3 C1
29 A1 A2 B1 B2 B3 B4
30 A1 A2 B1 B2 B3 C1
31 A1 A2 B1 B2 C1 A3
32 A1 A2 B1 B2 C1 B3
33 A1 A2 B1 B2 C1 C2
34 A1 A2 B1 B2 C1 D1
35 A1 A2 B1 C1 A3 A4
36 A1 A2 B1 C1 A3 B2
37 A1 A2 B1 C1 A3 C2
38 A1 A2 B1 C1 A3 D1
39 A1 A2 B1 C1 B2 A3
40 A1 A2 B1 C1 B2 B3
41 A1 A2 B1 C1 B2 C2
42 A1 A2 B1 C1 B2 D1
43 A1 A2 B1 C1 C2 A3
44 A1 A2 B1 C1 C2 C3
45 A1 A2 B1 C1 C2 D1
46 A1 A2 B1 C1 D1 A3
47 A1 A2 B1 C1 D1 B2
48 A1 A2 B1 C1 D1 C2
49 A1 A2 B1 C1 D1 D2
50 A1 A2 B1 C1 D1 E1
51 A1 B1 A2 A3 A4 A5
52 A1 B1 A2 A3 A4 B2
53 A1 B1 A2 A3 A4 C1
54 A1 B1 A2 A3 B2 A4
55 A1 B1 A2 A3 B2 B3
56 A1 B1 A2 A3 B2 C1
57 A1 B1 A2 A3 C1 A4
58 A1 B1 A2 A3 C1 B2
59 A1 B1 A2 A3 C1 C2
60 A1 B1 A2 A3 C1 D1
61 A1 B1 A2 B2 A3 A4
62 A1 B1 A2 B2 A3 B3
63 A1 B1 A2 B2 A3 C1
64 A1 B1 A2 B2 B3 B4
65 A1 B1 A2 B2 B3 C1
66 A1 B1 A2 B2 C1 A3
67 A1 B1 A2 B2 C1 B3
68 A1 B1 A2 B2 C1 C2
69 A1 B1 A2 B2 C1 D1
70 A1 B1 A2 C1 A3 A4
71 A1 B1 A2 C1 A3 B2
72 A1 B1 A2 C1 A3 C2
73 A1 B1 A2 C1 A3 D1
74 A1 B1 A2 C1 B2 A3
75 A1 B1 A2 C1 B2 B3
76 A1 B1 A2 C1 B2 C2
77 A1 B1 A2 C1 B2 D1
78 A1 B1 A2 C1 C2 A3
79 A1 B1 A2 C1 C2 C3
80 A1 B1 A2 C1 C2 D1
81 A1 B1 A2 C1 D1 A3
82 A1 B1 A2 C1 D1 B2
83 A1 B1 A2 C1 D1 C2
84 A1 B1 A2 C1 D1 D2
85 A1 B1 A2 C1 D1 E1
86 A1 B1 B2 B3 B4 B5
87 A1 B1 B2 B3 B4 C1
88 A1 B1 B2 B3 C1 B4
89 A1 B1 B2 B3 C1 C2
90 A1 B1 B2 B3 C1 D1
91 A1 B1 B2 C1 B3 B4
92 A1 B1 B2 C1 B3 C2
93 A1 B1 B2 C1 B3 D1
94 A1 B1 B2 C1 C2 B3
95 A1 B1 B2 C1 C2 C3
96 A1 B1 B2 C1 C2 D1
97 A1 B1 B2 C1 D1 B3
98 A1 B1 B2 C1 D1 C2
99 A1 B1 B2 C1 D1 D2
100 A1 B1 B2 C1 D1 E1
101 A1 B1 C1 A2 A3 A4
102 A1 B1 C1 A2 A3 B2
103 A1 B1 C1 A2 A3 C2
104 A1 B1 C1 A2 A3 D1
105 A1 B1 C1 A2 B2 A3
106 A1 B1 C1 A2 B2 B3
107 A1 B1 C1 A2 B2 C2
108 A1 B1 C1 A2 B2 D1
109 A1 B1 C1 A2 C2 A3
110 A1 B1 C1 A2 C2 C3
111 A1 B1 C1 A2 C2 D1
112 A1 B1 C1 A2 D1 A3
113 A1 B1 C1 A2 D1 B2
114 A1 B1 C1 A2 D1 C2
115 A1 B1 C1 A2 D1 D2
116 A1 B1 C1 A2 D1 E1
117 A1 B1 C1 B2 B3 B4
118 A1 B1 C1 B2 B3 C2
119 A1 B1 C1 B2 B3 D1
120 A1 B1 C1 B2 C2 B3
121 A1 B1 C1 B2 C2 C3
122 A1 B1 C1 B2 C2 D1
123 A1 B1 C1 B2 D1 B3
124 A1 B1 C1 B2 D1 C2
125 A1 B1 C1 B2 D1 D2
126 A1 B1 C1 B2 D1 E1
127 A1 B1 C1 C2 A2 A3
128 A1 B1 C1 C2 A2 C3
129 A1 B1 C1 C2 A2 D1
130 A1 B1 C1 C2 C3 A2
131 A1 B1 C1 C2 C3 C4
132 A1 B1 C1 C2 C3 D1
133 A1 B1 C1 C2 D1 A2
134 A1 B1 C1 C2 D1 C3
135 A1 B1 C1 C2 D1 D2
136 A1 B1 C1 C2 D1 E1
137 A1 B1 C1 D1 A2 A3
138 A1 B1 C1 D1 A2 B2
139 A1 B1 C1 D1 A2 C2
140 A1 B1 C1 D1 A2 D2
141 A1 B1 C1 D1 A2 E1
142 A1 B1 C1 D1 B2 B3
143 A1 B1 C1 D1 B2 C2
144 A1 B1 C1 D1 B2 D2
145 A1 B1 C1 D1 B2 E1
146 A1 B1 C1 D1 C2 A2
147 A1 B1 C1 D1 C2 C3
148 A1 B1 C1 D1 C2 D2
149 A1 B1 C1 D1 C2 E1
150 A1 B1 C1 D1 D2 A2
151 A1 B1 C1 D1 D2 B2
152 A1 B1 C1 D1 D2 D3
153 A1 B1 C1 D1 D2 E1
154 A1 B1 C1 D1 E1 A2
155 A1 B1 C1 D1 E1 B2
156 A1 B1 C1 D1 E1 C2
157 A1 B1 C1 D1 E1 D2
158 A1 B1 C1 D1 E1 E2
159 A1 B1 C1 D1 E1 F1

现在只需要分析借助前7轮的结果，如何使用最少次数得到2-6名的这159种赛果了。有事外出，谁帮忙算一算

aimisiyou 发表于 2021-3-21 10:21:28

通过八次比赛可得出前6名必为三角区内的点，已有一些边（逻辑关系）

aimisiyou 发表于 2021-3-21 10:52:41

要得出前六名，是否意味着要得出这21个点的任意两点的大小关系？那么也就是C（21,2）=210条边。也就是说每次选出其中6个点，要使新增的边数尽量多，这样就达到了次数最少。

northwolves 发表于 2021-3-21 12:55:19

第七轮之后，选出前六所需每组的前N名只有以下32种情况：

1111111
2111120
3111210
4111300
5112110
6112200
7113100
8114000
9121110
10121200
11122100
12123000
13131100
14132000
15141000
16150000
17211110
18211200
19212100
20213000
21221100
22222000
23231000
24240000
25311100
26312000
27321000
28330000
29411000
30420000
31510000
32600000

第八轮可选 B1 A2、C1 B2 A3，D1,根据排名结果决定第9轮的参赛者，目测11轮可决出前六

王守恩 发表于 2021-3-25 09:24:59

aimisiyou 发表于 2021-3-21 10:21
通过八次比赛可得出前6名必为三角区内的点，已有一些边（逻辑关系）

可有相关资料提供(就是不想走太多弯路)？谢谢！
有4匹马2个跑道，一次可选取2匹马进行比赛排名，用最少比赛次数算出跑最快的前2匹马？
有9匹马3个跑道，一次可选取3匹马进行比赛排名，用最少比赛次数算出跑最快的前3匹马？
有16匹马4个跑道，一次可选取4匹马进行比赛排名，用最少比赛次数算出跑最快的前4匹马？
有25匹马5个跑道，一次可选取5匹马进行比赛排名，用最少比赛次数算出跑最快的前5匹马？
有36匹马6个跑道，一次可选取6匹马进行比赛排名，用最少比赛次数算出跑最快的前6匹马？
..........

KeyTo9_Fans 发表于 2021-3-25 09:42:42

王守恩发表于 2021-3-25 09:24
可有相关资料提供(就是不想走太多弯路)？谢谢！
有4匹马2个跑道，一次可选取2匹马进行比赛排名，用最少 ...

我们这个论坛里以前有个类似的讨论：
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=5936

aimisiyou 发表于 2021-3-25 16:04:39

本帖最后由 aimisiyou 于 2021-3-25 21:08 编辑

KeyTo9_Fans 发表于 2021-3-25 09:42
我们这个论坛里以前有个类似的讨论：
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=5936

除了复杂的逻辑推理分析，有没有其他简便的分析方法？

王守恩 发表于 2021-3-26 10:02:09

aimisiyou 发表于 2021-3-21 10:21
通过八次比赛可得出前6名必为三角区内的点，已有一些边（逻辑关系）

a1,a2,a3,a4,a5,a6
b2,b3,b4,b5,b6
c3,c4,c5,c6
d4,d5,d6
e5,e6
f6

通过 7 次比赛可得出前 6 名排名如上。
第 8 次：a4,b4,c4,d4,e5,f6。可以淘汰掉 9 匹马。
第 9 次：a2,b2,a3,b3,c3,?4。
10次好像可以了？

补充内容 (2021-4-2 07:13):
第 9 次：a2,b2,a3,b3,c3,?4。可以确认前4名。

王守恩 发表于 2021-4-2 07:09:13

aimisiyou 发表于 2021-3-21 10:21
通过八次比赛可得出前6名必为三角区内的点，已有一些边（逻辑关系）

先往前走一走，回头再来看主帖，也许会简单些。大家可有建议？谢谢！

有4匹马2个跑道，一次可选取2匹马进行比赛排名，用最少比赛次数算出跑最快的前2匹马？
有9匹马3个跑道，一次可选取3匹马进行比赛排名，用最少比赛次数算出跑最快的前3匹马？
有16匹马4个跑道，一次可选取4匹马进行比赛排名，用最少比赛次数算出跑最快的前4匹马？
有25匹马5个跑道，一次可选取5匹马进行比赛排名，用最少比赛次数算出跑最快的前5匹马？
有36匹马6个跑道，一次可选取6匹马进行比赛排名，用最少比赛次数算出跑最快的前6匹马？

页: [1]

数学研发论坛's Archiver

赛马排序