数学之家

标题: 排列组合——淘汰赛——格子模型 [打印本页]

作者: castelu 时间: 2008-4-15 17:57
标题: 排列组合——淘汰赛——格子模型
例题：
中韩围棋擂台赛每方出八名棋手进行比赛，规则规定：每方先出一名选手进行比赛，胜者继续参赛，负者被淘汰，依此进行，直到一方选手全部被淘汰，则比赛结束。
求一共可能出现多少种比赛的结果？

解答：
这种比赛类似于“车轮战”，直接分析比较困难，因此引入一种格子模型。
如图：
__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
先画出16个格子，然后分别将两队队员放入
规定：格子右边的人总是把左边的人给打败，本队的人不打自己的队员
示例：
以1-8表示中方队员，以a-h表示韩方队员
其中一种任意放法是：
1 a 2 b c 3 d 4 e f g 5 6 7 8 h

这种排放情况等同于一种比赛结果，即：
a打败1
2打败a
b打败2
3打败b c
d打败3
4打败d
e打败4
5打败e f g
h打败5 6 7 8

因此，有几种排放方法就等于有几种比赛结果
问题转化
显然，只要从16个位置中选出8个位置给中方队员即可

答案为：C[sub]16[/sub][sup]8[/sup]

作者: 泡面 时间: 2008-7-3 19:33
这个方法很好啊.....
多学学

作者: jwxxixihaha123 时间: 2008-8-7 00:13
好，厉害，这也行

作者: 锟子 时间: 2008-8-7 14:28
哇，真的很难想到，不错！

作者: 巫师无视 时间: 2008-8-12 02:05
没必要这么做吧　　直接就出答案了

作者: 远知 时间: 2008-11-23 10:23
这个格子模型的专业名称叫做“栈”，是计算机中常用的一种数据结构。它的本质是一个只可以从一侧进行添加的删除的数列。题目的模型可以认为是将两个栈进行归并操作成为一个栈，有几种可能的结果。其理论发展的已经很完善。

作者: castelu 时间: 2009-1-9 18:00
原来如此，多谢指教

欢迎光临数学之家 (http://www.2math.cn/)