足球比赛为什么会有轮空(快速求出淘汰赛中轮空场次-最简单的算法)
更新时间:2022-10-14 10:45:03题目:如何快速求出N个人参加的淘汰赛中轮空的场次数?N可以使任意数,也就是任意人数参加的比赛。
例如:37个人参加淘汰赛,那么无论怎么安排比赛顺序,总是有4场比赛有运动员会轮空。
答案是:假如m个人参加比赛,N是大于或者等于m的最小2次幂。例如对于m=37来说,N就是2^6=64。那么,令s=N-m。对于m=37来说s=27。那么轮空数Result等于s的二进制表示方法中为1的位的个数!
例如对于s=27来说,二进制为11011,那么就一定是4次轮空。而且轮空的场次也跟1出现的次数一致,也就是说,第1,2,4,5场有人轮空比赛。
总结,只需要做减法就能规避掉复杂的计算,真是巧夺天工。
由此可以推算出世界杯足球赛参赛队伍永远是2的幂,32或者64,不然肯定会有球队少打比赛,造成不公。中国只能期望共有128支球队参加比赛的日子了…………
证明方法
关键在于二进制减法(特指N-m)的结果恰好与计算轮空场次的方法的结果一致。为什么我就不知道了。
例如m=37的例子。轮空的计算方法是
第一轮 37/2=18余1
第二轮共18 1=19支队伍比赛 19/2=9余1
第三轮共9 1=10支队伍比赛 10/2=5余0(无轮空)
第四轮共5支队伍比赛 5/2=2余1
第五轮共3支队伍比赛 3/2=1余1
第六轮 自然是决赛 不轮空
所以序列应该是(11011)正好等于64-37=27的二进制形式(11011)。
下面来证明“正好”其实是“必然”的:
注意到计算m(37)的二进制形式与计算轮空序列(上述的11011)的关系:
计算m的二进制方法:
37/2=18余1
18/2=9余0
9/2=4余1
4/2=2余0
2/2=1余0
1/2=0余1
所以m=37的二进制形式为100101
与上面计算轮空的算法结果的比较是:
1 1
0 1
1 0
0 1
0 1
1
可以看出除开第一个都是为1以外其余都是互补的。这就正好形成了加法进位,最终两个二进制数加一起就是N!而且他们的互补关系是从第一个1出现的时候开始的,也就是产生进位的第一个标志开始。
为什么会这样呢?
其实是因为当计算m的二进制时,我们只是取商,而计算轮空数的时候取商 余数。所以计算二进制的除数总是比计算轮空数的除数小1,造成最后的二进制结果除开第一位以为都是互补的情况(第一位必然是一样的)。
证明从第一个1以后互补关系保持的方法:
令从第二轮起m的二进制除数为N,那么轮空数除数为N 1
1.当N为偶数的时候:
第三轮除数为
N/2=N1
N 1/2=N1余1=N1 1
可见,当N为偶数的时候,差1的关系是能维持到下一轮计算的。
2.当N为奇数时:
N/2=N-1/2余1 下一轮除数取N-1/2=N2
N 1/2=N-1/2 1 下一轮除数取N2 1
所以当N为奇数的时候关系也是维持的。
综合1,2我们可以得出,不管是什么自然数,m的二进制形式与轮空计算得到的二进制形式除开第一个进位符与之前的0一致以外,其余的都是互补的,所以两者相加必然是等于比m大的2的幂。
相关推荐
- 最新资讯
-
- 2023-05-15 test
- 2022-11-15 2夺欧洲杯4获世界杯(俱乐部的成就引领国家队的辉煌——世界杯巡礼之西班牙篇)
- 2022-11-15 谁能介绍韩国国国家足球队(韩国足球,在欧洲是什么水平?)
- 2022-11-15 篮球世界杯中国最多几强(支持杜峰下课,但是中国男篮从世界第八沦为亚洲第八这个锅不该背)
- 2022-11-15 奥运会分为田径和什么(数说奥运:少年强则国强)
- 2022-11-15 中国男足VS沙特男足动漫图片(这部足球动画让日本队踢进了世界杯)
- 2022-11-15 世界杯进球最多的赛事(历届世界杯决赛里面11大进球最多的比赛)
- 2022-11-15 nba2k20手游在哪个平台(《NBA 2K20》试玩版报告:更加平衡的篮球体验)
- 2022-11-15 萨拉赫升至第三位(萨拉赫离封王就差一个冠军了,创下4大里程碑纪录 梅罗之后第三人)
- 2022-11-15 世界杯阿根廷队服(世界杯开赛前9天,阿根廷做出重要决定!恭喜梅西,封神希望大增)
- 推荐攻略
-
-
乌克兰总统身亡(乌总统泽连斯基解除乌总检察长及国家安全局局长职务)
-
足球比赛每个半场多少分钟(足球比赛每半场几分钟)
-
2021中超今天哪里转播(今晚!中超2场对决,CCTV5 直播申花PK武汉,腾讯体育亚泰vs天津)
-
2022梅西坠机身亡事件结果(足坛变天!巴萨无缘榜首的2年:梅西告别,老马去世,2-8惨案)
-
2021全运会篮球直播赛程辽宁(4月22日央视直播:CBA总决赛;赵心童vs马奎尔,塞尔比vs颜丙涛)
-
中国最强导弹(世界洲际导弹前10排名,中国东风导弹领先美国,第一名堪称导弹王)
-
2021篮球比赛在哪里看(CCTV5直播NBA 辽篮争夺CBA总决赛冠军点 颜丙涛出战斯诺克世锦赛)
-
东航结果不敢公布了(民航局再次回应东航MU5735事故调查!查明原因有多难,多久公布?)
-