Python程式：計算錦標賽中比賽場數

假設我們有一個數字 n。因此，在一個錦標賽中有 n 支隊伍，該錦標賽有一些規則：

  • 如果當前隊伍數量為偶數，則每支隊伍與另一支隊伍合併。總共進行 (n/2) 場比賽，其中 (n/2) 支獲勝隊伍將進入下一輪。

  • 如果隊伍數量為奇數，則隨機選擇一支隊伍進入錦標賽，其餘隊伍進行合併。總共進行 (n-1)/2 場比賽，(n-1)/2+1 支隊伍作為獲勝隊伍進入下一輪。

我們需要找到獲得最終獲勝者所需的比賽總場數。

因此，如果輸入為 n = 10，則輸出為 9，因為

  • 最初將進行 5 對 5 的分組，其中 5 支隊伍晉級

  • 現在將一支隊伍晉級到下一輪，並進行 2 對 2 的分組，所以 3 支隊伍晉級

  • 現在將一支隊伍晉級到下一輪，並進行 1 對 1 的分組，所以 2 支隊伍晉級

  • 進行 1 對 1 的分組，並有一支隊伍作為獲勝者晉級。

為了解決這個問題，我們將遵循以下步驟：

  • ans := 0

  • 當 n 不等於 1 時，執行以下操作

    • f := (n/2) 的向下取整

    • remainder := n 模 2

    • ans := ans + f

    • n := f + remainder

  • 返回 ans

示例（Python）

讓我們看看下面的實現以獲得更好的理解：

 線上演示

def solve(n):
   ans = 0
   while n != 1:
      f = n//2
      remainder = n % 2
      ans += f
      n = f + remainder

   return ans

n = 10
print(solve(n))

輸入

10

輸出

9

更新於：2021年5月18日

2K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告