網(wǎng)球循環(huán)賽日程表

1、一、 問題表述：設(shè)有n個運(yùn)動員要進(jìn)行網(wǎng)球循環(huán)賽。設(shè)計一個滿足以下要求的比賽日程表，(1) 每個選手必須與其他n-1個選手各賽一次；(2) 每個選手一天只能賽一次；(3) 當(dāng)n是偶數(shù)時，循環(huán)賽進(jìn)行n-1天，當(dāng)n是奇數(shù)時，循環(huán)賽進(jìn)行n天二、 分析問題題目是要n名運(yùn)動員進(jìn)行循環(huán)比賽。當(dāng)n為偶數(shù)時，正好每天都可以兩兩一組，與其余的n-1個選手比賽，只需n-1天； 而當(dāng)n為奇數(shù)，每天將有一個選手輪空，比賽將持續(xù)n天?？梢圆捎玫乃惴ㄈ缦拢?. 算法一：使用分治法當(dāng)n為偶數(shù)時，可以講問題分為兩個部分n/2; 然后繼續(xù)劃分，知道最后剩余兩名選手單獨(dú)比賽。當(dāng)n為奇數(shù)時，增設(shè)一個虛擬選手，運(yùn)動員為n+1個，將問題

2、轉(zhuǎn)化為是偶數(shù)的情形。當(dāng)選手與虛擬選手比賽時，表示輪空，因此只需要關(guān)注n為偶數(shù)的情形。a) 當(dāng)n/2為偶數(shù)時，與n = 2k情形類此。b) 當(dāng)n/2為奇數(shù)時，增設(shè)一個虛擬的選手，遞歸返回的將有輪空的選手，可以講在前面n/2輪比賽的選手與后面n/2輪空的選手進(jìn)行比賽。2. 算法二：利用邊是奇數(shù)的正多邊形。特點(diǎn)：以多邊形中的任意一個頂點(diǎn)畫對稱軸，其余偶數(shù)對頂點(diǎn)相互對稱。N名選手編號為1n，將其畫成一個正多邊形。a) 所以當(dāng)n為奇數(shù)時，第一天1號休息，其余以一號為對稱軸，兩兩對稱打比賽，第二天開始一次輪流休息，其余一休息的那個人編號為對稱軸，兩兩比賽。這樣比賽可進(jìn)行n天。如圖：此時n=9，為奇數(shù)，從0

3、開始每天有一個人輪空對稱軸對稱軸b) 當(dāng)n為偶數(shù)時，取出編號最大的，其他的組成一個正多邊形，n號一次順序與1,2，。n-1號選手比賽，其他與a）相同。如圖所示：（圖中是從0開始編號）99 N=2k時 9三、 理論分析算法及實現(xiàn)1. 算法一：使用分治法a) 算法的思路：按分治策略，可以將所有的選手對分為兩組（如果n是偶數(shù)，則直接分為n/2每組，如果n是奇數(shù)，則取（n+1）/2每組），n個選手的比賽日程表就可以通過為（n/2或（n+1）/2）個選手設(shè)計的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進(jìn)行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單。這時只要讓這兩個選手進(jìn)行比賽就可以

4、了。下圖給出的是六個選手的比賽日程表，其中第一列表示1-6個選手，第二列到第六列表示各個選手在第一天到第五天的所遇到的選手。1 2 3 4 5 62 1 5 3 6 43 6 1 2 4 54 5 6 1 3 25 4 2 6 1 36 3 4 5 2 1在這里算法設(shè)計的難點(diǎn)就是分開治理后的合并問題。這里我就結(jié)合上面給出的6個選手的示例來進(jìn)行表述。首先，將6個選手分為對等的兩組，每組3個選手。每組增設(shè)一個虛擬的選手，然后再遞歸的將3個選手分為對等兩組，每組2個選手。在2個選手情況下，這兩個選手比賽?？梢缘玫絻蓚€選手的日程安排表是：1 22 1接下來的任務(wù)是合并這兩組2個選手的日程表得到3個選手

5、的日程安排表，這里我先假設(shè)有4個選手參加比賽則：1 22 13 44 3接下來的比賽里，第二天讓1和3比賽，2和4比賽；第三天讓1和4比賽，2和3比賽，即讓前一組的選手，循環(huán)的和后一組的選手比賽，可得到比賽日程安排表是：1 2 3 42 1 4 33 4 1 24 3 2 1這里要得到的是3個選手的日程安排表，則第4個選手是假想的選手將其用0來表示則得到3個選手的日程安排表：1 2 3 02 1 0 33 0 1 2接下來的任務(wù)是合并這兩個3個選手的日程安排表得到6個選手的日程安排表，這里我們的兩組選手前3天的比賽情況如下：1 2 3 02 1 0 33 0 1 24 5 6 05 4 0 6

6、6 0 4 5其中第一天選手3和選手6都沒有對手，讓他們兩個比賽；第二天選手2和選手5沒有對手，讓他們兩個比賽，；第三天選手1和選手4沒有對手，讓他們兩個比賽。這就可以得到合并后6個選手前三天的比賽日程安排表：1 2 3 42 1 5 33 6 1 24 5 6 15 4 2 66 3 4 5將在前三天比過賽的兩組的選手對應(yīng)的列出來：1 2 34 5 6在這里可以看到合并的兩組中3和6，2和5，1和4都已經(jīng)比過了，這里就跳過這些選手的比賽，然后兩個組循環(huán)比賽即：1 2 35 6 4和1 2 36 4 5這樣就得到了6個選手的比賽完整的日程安排表：1 2 3 4 5 62 1 5 3 6 43

7、6 1 2 4 54 5 6 1 3 25 4 2 6 1 36 3 4 5 2 1b) 證明算法的正確性：（1） 在n=2時，就這兩個選手比賽，比賽只進(jìn)行一天，這也是算法的初始情況，算法成立。（2） 在n=k時，如果k為偶數(shù)，則將k個選手分為k/2的兩組，這樣按問題的要求k個選手共比賽k-1天，k/2個選手如果是偶數(shù)則比賽（k/2）-1天，在合并的時候兩組k/2個選手循環(huán)比賽需要k/2天，則先分組后合并共需要（k/2）-1+（k/2）=k-1天；k/2個選手如果是奇數(shù)則比賽k/2天，在合并的時候兩組中每個選手都相對應(yīng)的比賽過了一次，所以兩組k/2個選手循環(huán)比賽需要（k/2）-1天，則先分組后

8、合并共需要（k/2）+（k/2）-1=k-1天。（3） k為奇數(shù)的情況和k為偶數(shù)的情況類似。c) 算法的描述和架構(gòu)：分治法主要就是用 當(dāng)n=2k時 void tournament(int n)if(n = 1)a11 = 1;return;Tournament(n/2); Copy(n);主要是將左上角的遞歸計算出的小塊中的所有數(shù)字按照其相對位置抄寫到右下角，將左上角小塊中的所有數(shù)字加n/2后按照其相對位置抄寫到左下角，將左下角小塊中的所有數(shù)字按照相對位置抄到右上角。問題：n或者n/2可能不是偶數(shù)，此時就要虛擬增加一個隊員。if(odd(n) /如果是奇數(shù)tournament(n + 1);r

9、eturn;elsetournament(n/2); /是偶數(shù)時，遞歸調(diào)用，返回時合并makecopy(n);合并環(huán)節(jié)是最重要的，如果是n偶數(shù)的話，如上面的函數(shù)copy（n），但是如果是奇數(shù)，需要調(diào)用copyodd（n）void copyodd(int n)int m = n /2;int i,j;for(i = 1; i <= m; i+) /i的范圍是<=m，所以超出m的范圍就不算了 for(j = 1; j <= m + 1; j+) if(aij > m) /如果有輪空的話，就讓前n/2輪空的選手去后n/2輪空的選手比賽 aij = m + i;am + ij

10、= i;elseam + ij = aij +m; for(j = 2; j <=m; j+) int k,r = i;if(i + j - 1 > m) k = i + j -1;elsek = m + i + j - 1;arm + j = k; akm + j = r;其中后n/2天比賽中，是前n/2選手和后n/2的選手比賽，這點(diǎn)很值得推敲。架構(gòu)： Tournament（n）輸入運(yùn)動員的個數(shù) nN為奇N = n +1N為偶Tournament（n/2）N =1 makecopy(n)N為偶N為奇Copy(n)Copyodd(n)2. 算法二：利用邊是奇數(shù)的正多邊形。在第二部分

11、圖解中已經(jīng)比較詳細(xì)描述過，最難想到的一個規(guī)律是，對稱之后如何轉(zhuǎn)換，如下圖；9以n=10為例子，比如以1對稱軸，0和2對稱，8和3對稱，7和4對稱，6和5對稱，除了 arj = k, akj = r之外，還有什么規(guī)律呢？ 經(jīng)過多次畫圖之后發(fā)現(xiàn)，當(dāng)對稱軸變?yōu)?時，3和0對稱，8和5對稱，7和6對稱，轉(zhuǎn)變相鄰的對稱軸，原來對稱點(diǎn)的位置改變了兩個距離。以前8和3對稱，現(xiàn)在8和5對稱，增加了兩個，以前7和4對稱，現(xiàn)在7和6對稱； 但是以前3和8對稱，現(xiàn)在是和0對稱啊，8到1可不是增加了2啊，是的，但是再想循環(huán)的數(shù)的個數(shù)是9，8+2=10, 10%9 =1啊，所以這樣一想就可以豁然開朗了。所以就有：由第一

12、列可知， ai1=n-i+1;所以對應(yīng)的 ai+jj = ai+jj-1 + 2 = ai+j1 + 2*（i-1）=n+i-j-1于是產(chǎn)生了如下算法：當(dāng)n為偶數(shù)時：void tournament_even(int n)int i, j, m;m = n -1; /如上圖所示，取出編號最大的數(shù)，構(gòu)成奇多邊形for(i = 1; i <= m; i+)aii = n;for(j = 1; j <= m/2; j+) ani = i;int r = (i + j) % m;if(r =0)r = m;int k = (i + n - j -1) % m;if(k = 0)k = m;a

13、ri = k;aki = r;由對稱規(guī)律，知道對稱軸一旁的頂點(diǎn)的對應(yīng)點(diǎn)，則比賽對手也同樣明確了。所以j只需要取m/2一半就夠了。所以對稱軸是i時， aii=n;在需要知道對稱軸這側(cè)的一般就可以了 即： jß1 to jßm/2的ai+ji就可以了，所以就有了同理當(dāng)n為奇數(shù)時相似。void tournament_odd(int n)int i, j;for(i = 1; i<=n; i+)aii = -1;for(j = 1; j <= n/2; j+)int r = (i + j) % n;if(r = 0)r = n;int k = (i + n - j) % n;if(k =0)k = n;ari