MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 一道娱乐题,大家讨论一下玩玩吧!该怎么解决

一道娱乐题,大家讨论一下玩玩吧!该怎么解决

www.myexceptions.net  网友分享于:2013-04-12  浏览:13次
一道娱乐题,大家讨论一下玩玩吧!
前两天看奥运羽毛球重播时想到的问题,让大家也娱乐一下,题目如下!

某次群众羽毛球比赛,共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)捉对撕杀,进行淘汰赛,决出第一名;总共需要255场;
2)第二名只可能在被第一名直接淘汰的8人中; 8人进行淘汰赛,决出8人中的优胜者,即第二名,总共需要7场;
3)同样,第三名只可能在被第二名直接淘汰的人中…

------解决方案--------------------
可以这样设置比赛规则.
每次比赛,胜利者计1分,失败者不积分.

每次比赛后,统计所有选手的总分,并且排序.

下次比赛做对厮杀,配对规则是.
1. 从最高分开始,找到能与自己配对的分数最高的选手,如果有多个,则随机选取一个.
2. 选取的选手不能是曾经比赛过的,除非已经没有更低的分数的选手了.
3. 没选出一对后,在剩余的选手当中,按照上面的规则,继续选择下一对,知道所有的选手都配对完成.

在完成规定的若干轮比赛后,按照积分的高低顺序排名, 如果积分相同,则计算所有胜利场次的对手的积分总和,高的排名靠前.

比赛若干轮,一般256人的比赛轮数最少要log(256)=8轮,不过一般16轮能够比较公正的反应选手的实际水平.
优点:
1. 每个人都能赛满16场.
2. 高手与高手对决,低手与低手对垒,比赛更精彩.
3. 排名更科学,不会因为一场比赛的得失影响的最后的总成绩.

------解决方案--------------------
按贿赂的钱的多少来排,Easy,两天搞定!!!哈哈!!
------解决方案--------------------
三败制
------解决方案--------------------

文章评论

为什么程序员都是夜猫子
为什么程序员都是夜猫子
鲜为人知的编程真相
鲜为人知的编程真相
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
代码女神横空出世
代码女神横空出世
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
 程序员的样子
程序员的样子
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
10个调试和排错的小建议
10个调试和排错的小建议
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员的鄙视链
程序员的鄙视链
如何成为一名黑客
如何成为一名黑客
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
我的丈夫是个程序员
我的丈夫是个程序员
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员必看的十大电影
程序员必看的十大电影
程序员应该关注的一些事儿
程序员应该关注的一些事儿
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
老程序员的下场
老程序员的下场
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
程序员都该阅读的书
程序员都该阅读的书
每天工作4小时的程序员
每天工作4小时的程序员
漫画:程序员的工作
漫画:程序员的工作
总结2014中国互联网十大段子
总结2014中国互联网十大段子
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
那些争议最大的编程观点
那些争议最大的编程观点
Java程序员必看电影
Java程序员必看电影
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员和编码员之间的区别
程序员和编码员之间的区别
旅行,写作,编程
旅行,写作,编程
中美印日四国程序员比较
中美印日四国程序员比较
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有