『淘汰賽』是很常見的一種比賽方式, 兩兩比賽一場,輸者被淘汰,勝者晉級下一輪, 晉級者繼續兩兩比賽一場,輸者淘汰,勝者晉級下一輪, 如此重複一直到最後比出冠軍為止;
淘汰賽特別適用於有很多組參賽隊伍時, 每一輪都會讓參賽隊伍少一半,可以比其他方式快分出冠軍。
請問,在有 2048 組參賽隊伍時, 淘汰賽總共要比幾場就能分出冠軍呢? (注意題目是問幾場比賽,不是問幾輪喔!)
2047 場
這題如果用第一輪 2048/2=1024 場,第二輪 1024/2=512 場,...等差級數的總和來算, 也是可以算出來,但緩慢許多,沒有辦法快問快答;
但如果換個角度想: 每一場比賽都會淘汰掉一個輸家, 要能分出冠軍,就是要把冠軍之外的 2047 組都淘汰掉, 所以就是要比 2047 場。