某中学将举行乒乓球比赛,小明他们班有5人先进行淘汰赛,选出一人参加学校的决赛,班主任杨老师计算了一下比赛的次数:"嗯,由于5是奇数,所以第一轮有一个队员轮空,第二轮中还得出现一次轮空,一共需要进行4场比赛.选拔出一个队员后,学校共有37个班级参加决赛,也采用淘汰赛,你知道需要多少场比赛吗?你还没有算出来吗?哈哈!还在画表格呀?告诉你吧,每场比赛淘汰一名队员,一共要淘汰36名队员,所以要进行36场比赛.不过,如果你想轻易地算出轮空的次数却没有这么容易,那么,怎样计算轮空的次数呢?,请看如下的分析:
不知道你注意了没有,如果比赛人数正好是2的幂,那么轮空次数就是0,也就是说,如果比赛人数是2,4,8,16,32等等,就不会出现轮空,如果不是这样类型的数,则至少要有一次轮空.假设有n个队员参赛,如果是奇数,那么第一轮就有一名队员要轮空,从第二轮开始的轮空数与(n+1)/2个队员参赛的轮空数是一样的,所以这时总的轮空数是:(用L(n)表示n个队员参赛的轮空数)
L(n)=1+L((n+1)/2)
如果n是偶数,那么,第一轮没有轮空,从第二轮开始的轮空数与n/2个队员参赛的轮空数是一样的,所以有:
L(n)=L((n)/2)
我们可以统一处理以上两个公式:
L(n)=a
0+L((n+a
0)/2)
其中a
0为1或为0取决于n的奇偶性,下面的a1,a2,a3...也一样,假定2
k<n<2
k+1,并且规定n>=2,因为最后总是冠亚军决赛,所以最后一场比赛总是2名队员.继续往下推,我们有:
L(n)=a
0+a
1+L(a
0/4+a
1/2+n/4)
=a
0+a
1+a
2+L(a
0/8+a
1/4+a
2/2+n/8)
=a
0+a
1+a
2+...+a
k-1+L(a
0/2
k+a
2/2
k-1+...+a
k-1/2+n/2
k)
k-1 k-1
= ∑a
s+L(1/2
k∑a
s2
s+n/2
k)
s=0 s=0
由于最后总有:
k-1
1/2
k∑a
s2
s+n/2
k=2
s=0
即:
k-1
∑a
s2
s=2
k+1-n
s=0
我们看到,L(n)=a
0+a
1+a
2+...+a
k-1
所以,只要将2
k+1-n化成二进制表示,其系数和就是轮空数,也就是其中1的个数.对于n=37,我们可以算出2
k+1-n=64-37=27=11011,其中有4个1,所以共有四次轮空.
来源：
