2016-03-29 50 views
-2

劃分和算法問題:每個玩家必須對n-1個對手中的每一個玩對戰一次,每天最多隻有一場比賽顯示如果n是2,那麼有可能設計一個比賽需要n-1天。通過給出一個算法,輸入n並輸出每個n-1天的玩家配對列表,到目前爲止,我知道如果n必須大於2,並且我們使用類似於合併分類算法算法每n-1天輸入n和輸出對

回答

0

d天(其中d範圍從1n-1),玩家k(其中k範圍從0n-1)中扮演球員k xor d

這個算法有些簡單的事實:

  • 如果n21 <= d <= n-10 <= k <= n-1電源然後0 <= k xor d <= n-1所以函數k, d -> k xor d是從球員和天給玩家一個有效的功能。
  • 沒有玩家曾經玩過自己,因爲k xor d = k意味着d = 0
  • 在任何給定的一天,這會產生一個配對,因爲k xor d xor d = k
  • 任何給定的玩家都不會兩次玩同一個對手,因爲k xor d = x xor d'意味着d = d'

因此每個玩家每天玩1個對手,並且超過n-1天,每個對手恰好與每個對手匹配一次。

在代碼:

def matchings(n): 
    for day in xrange(1, n): 
     print 'Day', day 
     for k in xrange(n): 
      print 'Player', k, 'plays Player', k^day 
     print 

matchings(4) 
+0

但你如何轉換到這僞代碼和心不是的運行時間是O(N^2)??。也就是你描述它的方式,它看起來不像分而治之算法或合併排序。是對的嗎? –

+0

@jsmith問題中存在實際的工作代碼 - 如果您願意,可以將其視爲僞代碼。是的,運行時間爲O(n^2),因爲該問題要求在n-1天內有n個玩家的時間表 - 這已經是O(n^2)個輸出行。你說得對,算法不使用分而治之的方法,也不像合併排序。 –