-2
劃分和算法問題:每個玩家必須對n-1個對手中的每一個玩對戰一次,每天最多隻有一場比賽顯示如果n是2,那麼有可能設計一個比賽需要n-1天。通過給出一個算法,輸入n並輸出每個n-1天的玩家配對列表,到目前爲止,我知道如果n必須大於2,並且我們使用類似於合併分類算法算法每n-1天輸入n和輸出對
劃分和算法問題:每個玩家必須對n-1個對手中的每一個玩對戰一次,每天最多隻有一場比賽顯示如果n是2,那麼有可能設計一個比賽需要n-1天。通過給出一個算法,輸入n並輸出每個n-1天的玩家配對列表,到目前爲止,我知道如果n必須大於2,並且我們使用類似於合併分類算法算法每n-1天輸入n和輸出對
在d
天(其中d
範圍從1
至n-1
),玩家k
(其中k
範圍從0
至n-1
)中扮演球員k xor d
。
這個算法有些簡單的事實:
n
是2
,1 <= d <= n-1
和0 <= 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)
但你如何轉換到這僞代碼和心不是的運行時間是O(N^2)??。也就是你描述它的方式,它看起來不像分而治之算法或合併排序。是對的嗎? –
@jsmith問題中存在實際的工作代碼 - 如果您願意,可以將其視爲僞代碼。是的,運行時間爲O(n^2),因爲該問題要求在n-1天內有n個玩家的時間表 - 這已經是O(n^2)個輸出行。你說得對,算法不使用分而治之的方法,也不像合併排序。 –