1、問題描述：設有n個運動員要進行網球循環賽。設計一個滿足以下要求的比賽日程表:(1)每個選手必須與其他n-1個選手各賽一次；(2)每個選手一天只能賽一次；(3)當n是偶數時，循環賽進行n-1天。當n是奇數時，循環賽進行n天。分析過程：這個問題的解搜索空間是一個n的全排列。要求的解是其中的n個排列，滿足條件：第列n個元素值按增序排列；每行每列沒有相同的數。也是一個幻方(除對角線的和不作要求)的問題。1.n=1（表1）匚2.n=2（表2）1 |22 13 .n=3,(1)添加一個虛擬選手4#,構成n+1=4(2) 4/2=2,分兩組，每組各自安排(12),(34)(3)每組跟另一組分別比賽(拷貝)這

2、是四個人比賽的安排(表3)4人賽程把虛選手置為0(表4)3人賽程這是三個人比賽的安排4 .n=4,見表35 .n=5,(1)加一個虛選手，n+1=6。安排好6個人的比賽后，把第6個人用0表示即得5人的(2)分成兩組(123)(456),各3名選手(3)依照表4,安排第1組；按表5安排第2組(除0元素外，者切口3)(表5)4560(4)把表5排于表4下方（表6）(5)把同一天都有空的兩組安排在一起比賽(按這種安排，肯定每天只有一對空組，？)（表7）122136455463345312612645(6)第一組的(1 2 3)和第2組的(4 5 6)分別比賽。 但是由于(1,4), (2, 5),

3、(3 6)已經比賽過 了，所以在后面的安排中不能再安排他們比賽。4 56首先，1#只能和5#或6#比賽(a)若1# 5#,由于3#和6#已經比賽過，所以只能安排(b)若1# 6#,由于2#和5#已經比賽過，只能安排： 這樣安排后前三行的后兩列，后三行的后兩列由上面的三行來定：(表8) 6人賽程尸:2#- 6#, 3#-4# 2#- 4#, 3#- 5#表8就是6名選手的比賽日程安排。將其中的6號作為虛擬選手，把6換成0,即得5名選手的賽程安排表:（表9） 5人賽程6n=6,見表8。7n=7,添加1,n+1=8。8名選手的安排，由4名選手（表3）構成（表10）8人賽程12345678214365

4、87341278564321876556781234658721437856341287654321將其中的8改成0,即得7名選手的賽程安排。（表11）7人賽程8n=8,見表1010 n=10。（表 12）9n=9,由n+1=10人，將虛選手10號置為0來得到10人的比賽，分兩組（12345）和（678910）各5人。前5人比賽的安排如表,123450.215304301,2454503254-20i13第2組的5人比賽就是將前5人比賽選手（非0）號對應加5（表13）678910076108098067L9109_1006871097068然后兩組合弁（表14）12345021_5304301

5、245450132542_0136_789100761080980679109.10068.7.1097068找兩組中同一天中沒有安排比賽的，安排他們比賽:（表15）由于兩組中：12345678910按列對應的已經比賽過一次：16,2-7,38,49,5-10。后面再安排兩組選手分別比賽的時候，就不考慮已經比賽過的組合。安排兩組選手分別比賽的時候，依照這樣的規則：1#按遞增順序依次跟沒有比賽過的第2組選手比賽（7,8,9,10各一天）。若1#和X1比賽，則2號從610號中從X1之后開始按增序中找第一個沒有比賽過的選手，跟他比賽（如果X1 = 10,則2號從6 號開始按增序找）。3、4、5號也如

6、此找。結果如表16所示：（表16）10人的賽程安排12345678910215374891063812459106745913210678542101367896789101543276：1082915438367:910215491046873215109756843218,6人比賽時，也有此規律）觀察表16的右上角，發現如下規律（表610 (即n/2+1n )循環遞增（取到最大值 10之后，下一個數字又從6開始取值；而且不包含左上角的塊同一行中取過【規則一】：每一行數值從左到右循環遞增；每一列上也是的值）。第一行第m+1（下標從0開始）列的值為（m+1）+1,依次向右遞增；要先處理。其他行

7、上的值要依賴于它的這個取值。兩兩之間進行的，所以右下角由右上角決定（比賽的【規則二】：右下角的塊：因為比賽是對手是兩個人，因此對應的安排要成對）OK,至此，問題就好解決了，只要按照這個規律填數字，就可以得到一種合理的安排。由于我們不是求全部的安排，所以，只要得到這么一個解就可以了。9人比賽，則將表16中的10全部用0代替即得。（表17）9人的賽程安排n/2來得到，然后左下角拷貝到右上角；左0外都加n/2）,然后把同一天都有空的選手由上面的分析，可以總結出如下算法:名選手的賽程安排問題：如果n為偶數，可分為兩個n/2人的組，分別比賽，然后兩組間比賽。1.1 如果n/2為偶數，左下角為左上角加上角

8、拷貝到右下角；1.2 如果n/2為奇數，先安排左下角（除安排比賽。然后，右上角要按規則一來完成，右下角由規則二來定。2如果n為奇數，則加1個選手使n+1成為偶數。轉化成偶數名選手的賽程安排問題來循環賽日程安排問題 - 采用分治法*/int * 指針數組，/int 數組，一維數組保存二維數組的數據/ 問題的規模。初始化時會設定解決。最后把虛擬選手n+1號所在位置上的值置為0。即完成安排。/*exp6_09_3.cpp#include<stdlib.h>#include<stdio.h>int*A;int*schedule;intN=1;/isodd:判斷x是否奇數，是則返

9、回1，否則0intisodd(intx)returnx&1;/print:打印賽程voidprint()inti,j,row,col;if(isodd(N)row=N;col=N+1;elserow=N;col=N;printf("第1列是選手編號n");for(i=0;i<row;i+)for(j=0;j<col;j+)printf("%4d",Aij);printf("n");/*init：初始化，設置問題規模N值，分配內存，用schedule指向；把A構造成一個二維數組*/voidinit()inti,n;c

10、harline100='0'printf("請輸入選手人數：");fgets(line,sizeof(line),stdin);if(N<=0)exit(-1);if(isodd(N)n=N+1;elsen=N;/schedule是行化的二維數組schedule=(int*)calloc(n*n,sizeof(int);A=(int*)calloc(n,sizeof(int*);if(!schedule|A=NULL)exit(-2);for(i=0;i<n;i+)/把A等價為二維數組Ai=schedule+i*n;Ai0=i+1;/初始化這個數

11、組的第一列return;/*replaceVirtual:把第m號虛的選手去掉(換0)*/做voidreplaceVirtual(intm)inti,j;for(i=0;i<m-1;i+)/行：對應選手號1m-1for(j=0;j<=m;j+)/列:比行要多1Aij=(Aij=m)?0:Aij;return;/*copyeven:m為偶數時用,由前1組的m位選手的安排，來構成第2組m位選手voidcopyeven(intm)if(isodd(m)return;inti,j;for(j=0;j<m;j+)/1.求第2組的安排(+m)for(i=0;i<m;i+)i+mj=

12、Aij+m;for(j=m;j<2*m;j+)/兩組間比賽的安排for(i=0;i<m;i+)/2.第1組和第2組Aij=Ai+mj-m;/把左下角拷貝到右上角for(i=m;i<2*m;i+)/3.對應的，第2組和第1組Aij=Ai-mj-m;/把左上角拷貝到右下角return;/*copyodd:m為奇數時用,由前1組的m位選手的安排，來構成第2組m位選手的賽程安排，以及兩組之間的比賽安排。這時和m為偶數時的處理有區別。*/voidcopyodd(intm)inti,j;for(j=0;j<=m;j+)/1.求第2組的安排(前m天)for(i=0;i<m;i+

13、)/行if(Aij!=0)Ai+mj=Aij+m;else/特殊處理：兩個隊各有一名選手有空，安排他們比賽Ai+mj=i+1;Aij=i+m+1;/ 安排兩組選手之間的比賽(后m-1天)/for(i=0,j=m+1;j<2*m;j+)Aij=j+1;/2.1號選手的后m-1天比賽A(Aij-1)j=i+1;/3.他的對手后m-1天的安排/以下的取值要依賴于1號選手的安排，所以之前先安排1號的賽程for(i=1;i<m;i+)/第1組的其他選手的后m-1天的安排(j觀察得到的規則一：向下m+12*m循環遞增/2.Aij=(Ai-1j+1)%m=0)?Ai-1j+1:m+(Ai-1j+

14、1)%m;/3.對應第2組的對手也要做相應的安排A(Aij-1)j=i+1;return;/*makecopy:當前有m位(偶數)選手，分成兩組，每組由m/2位選手構成由第一組的m/2位選手的安排來構成第二組的比賽安排，第一組與第二組的比賽安排。要區分m/2為奇數和偶數兩種情況/m/2 為奇數/m/2 為偶數*/voidmakecopy(intm)if(isodd(m/2)copyodd(m/2);elsecopyeven(m/2);voidtournament(intm)if(m=1)A00=1;return;elseif(isodd(m)tournament(m+1);replaceVirtual(m+1);return;elsetournament(m/2);makecopy(m);/如果m為奇