一道娱乐题，大家讨论一下玩玩吧！前两天看奥运羽毛球重播时想到的问题，让大家也娱乐一下，题目如下！某次群众
一道娱乐题，大家讨论一下玩玩吧！
前两天看奥运羽毛球重播时想到的问题，让大家也娱乐一下，题目如下！
某次群众羽毛球比赛，共256名参赛选手，比赛对于前3名设立奖品，奖金相当丰厚，为某家炸酱面馆的代金卷。
由于是群众比赛，因此不设置种子选手，所有分组都是随机的，于是就出现了下面的情况。
由于分组不确定，一些选手怕自己被过早淘汰，向组委会提出异议，希望赛程不要设为淘汰赛，而是变为循环赛，这样，才有可能选出真正的前3名。
但如果变为单循环，比赛场次将激增，恐怕神9神10上天了都比不完。
现在问题就是，你有没有什么好的办法帮助组委会，既能保证找出真正的前3名，又不会进行过多的比赛，最少需要比多少场，才能保证找出真正的前三。
[解决办法]
循环赛是不是说同组内每两个选手之间都要交手？
这个问题的本质就是要找出数组内最大的三个元素。
如果单纯追求最少的比较次数，那循环赛并不是最好的选择，对淘汰赛制修改一下（类似锦标赛排序的方法）会更好。
[解决办法]
还有种排法,
1) 256人分3人组85组, 1人轮空, 每组赛3场决出名次, 共赛了85x3=255场
2) 85组再每每两组合成6人组, 共有42组, 剩余一组与上轮轮空的一人组成4人组
6人组要赛3场就可决出前3名, 4人组要赛1场就可决出前3, 故这轮要赛区 42x3+1=127场
3) 上轮决出的43组前三名再每两组合成一组, 形成21个6人组, 还有一个3人组轮空
这轮要赛 21x3=63场
4) 上轮决出的22组前三名再每两组合成一组, 形成11个6人组
这轮要赛 11x3=33场
5) 上轮决出的11组前三名再每两组合成一组, 形成5个6人组, 还有一个3人组轮空
这轮要赛 5x3=15场
5) 上轮决出的6组前三名再每两组合成一组, 形成3个6人组
这轮要赛 3x3=9场
6) 上轮决出的3组前三名再每两组合成一组, 形成1个6人组, 还有一个3人组轮空
这轮要赛 1x3=3场
7) 上轮决出的2组前三名组合成一组, 形成1个6人组
这轮要赛 1x3=3场就可决出前3
总共赛 255+127+63+33+15+9+3+3=508场
[解决办法]
A B C D OUT Count
128 128 128 =256/2
64 64 64 64 128 =64+64
32 64 64 64 32 128 =32*4
16 48 64 64 32 112 =16+32*3
8 32 56 64 32 96 =8+24+32*2
4 20 44 60 30 80 =4+16+28+32
2 12 32 52 30 64 =2+10+22+30
1 7 22 42 26 49 =1+6+16+26
......
A-全胜，B-败1，C-败2，D-败3
这种方法最初只分了2组，还不够优，多分几组会好些，关键是分几组最优的问题
[解决办法]
[解决办法]这个题目的要求是找出前三名，且是名至实归的，则可以考虑数据结构上的n-1+log（n-1）+log（n-2）：其实就是用树产生冠军，则亚军在和冠军比赛中失败的人中产生，以此。。。。。！！！！
[解决办法]用堆排序应该可以的吧，找出第一个后，将堆顶移出，再次堆排序找出第二名，依次类推。。。
[解决办法]我觉得应该分组,然后在分组，
就象亚洲预选一样，先分组,然后取出前三，在分组继续取出前三，直到取出最后的前三
但是要设置一下种子选手，避免猛人在一个小组遇到
[解决办法][解决办法]可以这样设置比赛规则.
每次比赛,胜利者计1分,失败者不积分.
每次比赛后,统计所有选手的总分,并且排序.
下次比赛做对厮杀,配对规则是.
1. 从最高分开始,找到能与自己配对的分数最高的选手,如果有多个,则随机选取一个.
2. 选取的选手不能是曾经比赛过的,除非已经没有更低的分数的选手了.
3. 没选出一对后,在剩余的选手当中,按照上面的规则,继续选择下一对,知道所有的选手都配对完成.
在完成规定的若干轮比赛后,按照积分的高低顺序排名, 如果积分相同,则计算所有胜利场次的对手的积分总和,高的排名靠前.
比赛若干轮,一般256人的比赛轮数最少要log(256)=8轮,不过一般16轮能够比较公正的反应选手的实际水平.
优点:
1. 每个人都能赛满16场.
2. 高手与高手对决,低手与低手对垒,比赛更精彩.
3. 排名更科学,不会因为一场比赛的得失影响的最后的总成绩.
[解决办法]按贿赂的钱的多少来排，Easy，两天搞定！！！哈哈！！
[解决办法]三败制
------解决方案--------------------
要找前3名，在排序算法中，可以用冒泡法，做三遍就可以了。
总共比较n-1 + n-2 + n-3=3n-6 次
转换成比赛规则，可以对所有的参赛者进行堆排序（也就是两两对比，胜者继续比，直到剩下一个人），第一遍决出第一名，在败者中再执行同样的规则，得到第二名，再从败者中再次执行同样规则，得到第三名
[解决办法][解决办法]应该用三败淘汰制，
淘汰一个人需要三场。
如果假定胜负完全靠实力，不会有循环出现，那样第1名肯定全胜，第二名输一场，第三名输两场。
1，首先两两比，赢的进胜者主，输的进负1组
2，然后胜者组两两比，输的进负1组
负1组两两比，输的进负2组
3，继续胜者组两两比，输的进负1组
负1组两两比，输的进负2组
负2组两两比，输的淘汰
循环3，直到每组只剩1人为止
因为：第1名肯定全胜，第二名输一场，第三名输两场。
这样最多 (N-3)*3 + 2 + 1场比赛
[解决办法]3楼提到的双败制不错，冠军和亚军是名副其实的了，但是季军却很可能早早被淘汰了，改进下，分甲乙丙三组，首先全部捉对比赛，胜的进甲组，输的进乙组，再分组捉对比赛，甲组输的降级至乙组，乙组降级至丙组，丙组数的淘汰，这样下去，直到三组都只剩一个人，即为冠亚季。
9楼提到，题目的意思是比赛结果完全正确反应参赛选手实力，同意
[解决办法]这个游戏应该默认一下就是不管怎么比赛 不用考虑心理素质场地天气等等客观原因 仅就实力而言决定比赛结果 那么才能产生决出前三名的效果
那么可以继续分析
一般来讲 分组会产生的比赛场数如果是单循环 设小组人数为n 就会产生n*(n-1)/2 的比赛场数 那么 分组数目就是256/n
下面的数据是用来分析分组打循环赛后的统计（主办方一定不会在队伍够分的情况下将球队分成单数，所以我们只取256的大于死的约数）
分组数 每组人数 小组赛阶段总比赛数 剩余选手(晋级选手)
64 4 384 64×3
32 8 896 32×3
16 16 1920 16×3
8 32 3968 8×3
4 64 8064 4×3
很显然 分组数目决定了比赛场数
当然这些都是有条件的 比如 我们不管如何分组 只管取出小组前三名(这样才能保证肯定不会让前三名漏网)
所以最后一排是小组赛后剩下的选手数 结果显示前期投入也是很必要的 因为后期剩余的队伍很少了 但是从小组赛场次来看未免得不偿失了
下面的比赛我觉得要进行的淘汰赛的形式才能解决问题 当然我分析了很长时间 由于比赛的胜负关系及其不确定性 还没有结论希望大家继续发挥，共同探讨！
[解决办法]VB code我想编号1-256选手。
1-2比 如果1胜 结果排成 1 2 如果2胜 结果排成 2 - 1 假设1 胜了 排成 1-2
1-3比 如果1胜 2-3比 如果2胜 结果排成 1-2-3
如果3胜 结果排成 1-3-2
如果3胜 结果排成 3-1-2
假设结果为 1-2-3
3-4比 如果4胜 2-4比 如果4胜 1-4比 如果4胜 结果 4-1-2
如果1胜 结果 1-4-2
如果2胜 结果 1-2-4
如果3胜 结果 1-2-3
假设结果为 1-2-3
3-5比 以此类推。
[解决办法]刚翻了数据结构书，这几乎是原题，汗颜啊。手工敲一遍，以示对自己的惩戒
树形选择排序树形选择排序，又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。
首先对n个记录的关键字进行两两比较，然后在其中n/2个较小者之间再进行，两两比较，如此重复，直至选出最小关键字的记录为止。这个过程可以用一颗有n个叶子结点的完全二叉树表示。
例如，图a中的二叉树表示从8个关键字中选出最小关键字的过程。8个叶子结点中依次存放排序之前的8个关键字，每个非终端结点中的关键字均等于其左、右孩子结点中较小的关键字，则跟结点中的关键字即为叶子结点中的最小关键字。
在输出最小关键字之后，根据关系的可传递性，欲选出次小关键字，仅需将叶子结点中最小关键字（13）改为最大值，然后从该叶子结点开始，和其兄弟的关键字进行比较，修改从叶子结点到根的路径上各结点的关键字，则根节点的关键字即为此小关键字。
同理，可依次选出从小到大的所有关键字（参见图b图c）。由于含有n个结点的完全二叉树深度为 log2(n)向上取整+1，则在树形选择排序中，除了最小关键字之外，每选择一个次小关键字，仅需进行 log2(n)向上取整 次比较，因此，它的时间复杂度为 O(n * log2(n))。但是，这种排序方
法尚有辅助存储空间较多，和最大值进行多余的比较等缺点。为了弥补，威洛姆斯在1964年提出了另一种形式的选择排序——堆排序
也就是说，lz的题目选出第一名需要比255场，第二名和第三名至多各比7场。总场数<=269图a：
13
/ \
/ \
38 13
/ \ / \
38 65 13 27
/ \ / \ / \ / \
49 38 65 97 76 13 27 48
图b：
27
/ \
/ \
38 27
/ \ / \
38 65 76 27
/ \ / \ / \ / \
49 38 65 97 76 ∞ 27 48
图c：
38
/ \
/ \
38 48
/ \ / \
38 65 76 48
/ \ / \ / \ / \
49 38 65 97 76 ∞ ∞ 48
前3是 13 27 38
[解决办法]
正确答案17楼已经出来了，后面的都是废话！
[解决办法]1)取3人为种子队员.
2)其他所有人为大众队,排成队.
3)种子队单循环,决出第三,
4)种子队的第三名和大众队比赛.如果大众队胜出则把最后种子队最后一名踢走,种子队内继续决出第三.如果种子队胜出则继续下一个大众队.
5)直到大众队结束比赛.
==
呵呵,反正比赛里又不会累.
