快速求出淘汰賽中輪空場次-最簡單的算法

題目：如何快速求出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的冪。