循環(huán)賽問題分析和C語言代碼-分治法

./問題描述：設(shè)有n個運(yùn)動員要進(jìn)行網(wǎng)球循環(huán)賽。設(shè)計(jì)一個滿足以下要求的比賽日程表：〔1每個選手必須與其他n-1個選手各賽一次；〔2每個選手一天只能賽一次；〔3當(dāng)n是偶數(shù)時(shí),循環(huán)賽進(jìn)行n-1天。當(dāng)n是奇數(shù)時(shí),循環(huán)賽進(jìn)行n天。分析過程：這個問題的解搜索空間是一個n的全排列。要求的解是其中的n個排列,滿足條件：第1列n個元素值按增序排列；每行每列沒有相同的數(shù)。也是一個幻方〔除對角線的和不作要求的問題。1.n=1〔表112.n=2〔表212213.n=3,<1>添加一個虛擬選手4#,構(gòu)成n+1＝4<2>4/2＝2,分兩組,每組各自安排〔12,〔34<3>每組跟另一組分別比賽〔拷貝這是四個人比賽的安排<表3>4人賽程1234214334124321 <4>把虛選手置為0<表4>3人賽程1230210330120321這是三個人比賽的安排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>〔表54560540660450321<4>把表5排于表4下方〔表6123021033012456054066045<5>把同一天都有空的兩組安排在一起比賽<按這種安排,肯定每天只有一對空組,？>?！脖?123421533612456154266345<6>第一組的<123>和第2組的<456>分別比賽。但是由于<1,4>,<2,5>,<36>已經(jīng)比賽過了,所以在后面的安排中不能再安排他們比賽。123456首先,1#只能和5#或6#比賽。若1#－5#,由于3#和6#已經(jīng)比賽過,所以只能安排:2#－6#,3#－4#若1#－6#,由于2#和5#已經(jīng)比賽過,只能安排：2#－4#,3#－5#這樣安排后前三行的后兩列,后三行的后兩列由上面的三行來定：〔表86人賽程123456215364361245456132542613634521表8就是6名選手的比賽日程安排。將其中的6號作為虛擬選手,把6換成0,即得5名選手的賽程安排表：〔表95人賽程1234502153043012454501325420136345216n=6,見表8。7n=7,添加1,n+1=8。8名選手的安排,由4名選手〔表3構(gòu)成〔表108人賽程1234567821436587341278564321876556781234658721437856341287654321將其中的8改成0,即得7名選手的賽程安排?！脖?17人賽程12345670214365073412705643210765567012346507214370563412076543218n=8,見表10。9n=9,由n+1＝10人,將虛選手10號置為0來得到。10n=10。10人的比賽,分兩組〔12345和<678910>各5人。前5人比賽的安排如表9〔表12123450215304301245450132542013第2組的5人比賽就是將前5人比賽選手〔非0號對應(yīng)加5〔表1367891007610809806791091006871097068然后兩組合并〔表1412345021530430124545013254201367891007610809806791091006871097068找兩組中同一天中沒有安排比賽的,安排他們比賽：〔表15123456215374381245459132542101367891017610829836791091046871097568由于兩組中：12345678910按列對應(yīng)的已經(jīng)比賽過一次：1－6,2－7,3－8,4－9,5－10。后面再安排兩組選手分別比賽的時(shí)候,就不考慮已經(jīng)比賽過的組合。安排兩組選手分別比賽的時(shí)候,依照這樣的規(guī)則：1#按遞增順序依次跟沒有比賽過的第2組選手比賽〔7,8,9,10各一天。若1#和x1比賽,則2號從6~10號中從x1之后開始按增序中找第一個沒有比賽過的選手,跟他比賽<如果x1＝10,則2號從6號開始按增序找>。3、4、5號也如此找。結(jié)果如表16所示：〔表1610人的賽程安排12345678910215374891063812459106745913210678542101367896789101543276108291543836791021549104687321510975684321觀察表16的右上角,發(fā)現(xiàn)如下規(guī)律〔表8,6人比賽時(shí),也有此規(guī)律：[規(guī)則一]：每一行數(shù)值從左到右循環(huán)遞增；每一列上也是6～10〔即n/2+1~n循環(huán)遞增〔取到最大值10之后,下一個數(shù)字又從6開始取值；而且不包含左上角的塊同一行中取過的值。第一行第m+1<下標(biāo)從0開始>列的值為<m+1>+1,依次向右遞增；要先處理。其他行上的值要依賴于它的這個取值。[規(guī)則二]：右下角的塊：因?yàn)楸荣愂莾蓛芍g進(jìn)行的,所以右下角由右上角決定〔比賽的對手是兩個人,因此對應(yīng)的安排要成對；OK,至此,問題就好解決了,只要按照這個規(guī)律填數(shù)字,就可以得到一種合理的安排。由于我們不是求全部的安排,所以,只要得到這么一個解就可以了。9人比賽,則將表16中的10全部用0代替即得?！脖?79人的賽程安排1234567890215374890638124590674591320678542013678967890154327608291543836790215490468732150975684321由上面的分析,可以總結(jié)出如下算法：n名選手的賽程安排問題：如果n為偶數(shù),可分為兩個n/2人的組,分別比賽,然后兩組間比賽。如果n/2為偶數(shù),左下角為左上角加n/2來得到,然后左下角拷貝到右上角；左上角拷貝到右下角；如果n/2為奇數(shù),先安排左下角〔除0外都加n/2,然后把同一天都有空的選手安排比賽。然后,右上角要按規(guī)則一來完成,右下角由規(guī)則二來定。如果n為奇數(shù),則加1個選手使n+1成為偶數(shù)。轉(zhuǎn)化成偶數(shù)名選手的賽程安排問題來解決。最后把虛擬選手n+1號所在位置上的值置為0。即完成安排。/*exp6_09_3.cpp循環(huán)賽日程安排問題-采用分治法*/#include<stdlib.h>#include<stdio.h>int**A;//int*指針數(shù)組,int*schedule;//int數(shù)組,一維數(shù)組保存二維數(shù)組的數(shù)據(jù)intN=1;//問題的規(guī)模。初始化時(shí)會設(shè)定//isodd:判斷x是否奇數(shù),是則返回1,否則0intisodd<intx>{returnx&1;}//print:打印賽程voidprint<>{inti,j,row,col;if<isodd<N>>{row=N;col=N+1;}else{row=N;col=N;}printf<"第1列是選手編號\n">;for<i=0;i<row;i++>{for<j=0;j<col;j++>{printf<"%4d",A[i][j]>;}printf<"\n">;}}/*init：初始化,設(shè)置問題規(guī)模N值,分配內(nèi)存,用schedule指向；把A構(gòu)造成一個二維數(shù)組*/voidinit<>{inti,n;charline[100]={'\0'};printf<"請輸入選手人數(shù)：">;fgets<line,sizeof<line>,stdin>;N=atoi<line>;if<N<=0>exit<-1>;if<isodd<N>>n=N+1;elsen=N;//schedule是行化的二維數(shù)組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等價(jià)為二維數(shù)組{A[i]=schedule+i*n;A[i][0]=i+1;//初始化這個數(shù)組的第一列}return;}/*replaceVirtual:把第m號虛的選手去掉〔換做0*/voidreplaceVirtual<intm>{inti,j;for<i=0;i<m-1;i++>//行：對應(yīng)選手號1～m-1{for<j=0;j<=m;j++>//列:比行要多1A[i][j]=<A[i][j]==m>?0:A[i][j];}return;}/*copyeven:m為偶數(shù)時(shí)用,由前1組的m位選手的安排,來構(gòu)成第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++>{A[i+m][j]=A[i][j]+m;}}for<j=m;j<2*m;j++>//兩組間比賽的安排{for<i=0;i<m;i++>//2.第1組和第2組{A[i][j]=A[i+m][j-m];//把左下角拷貝到右上角}for<i=m;i<2*m;i++>//3.對應(yīng)的,第2組和第1組{A[i][j]=A[i-m][j-m];//把左上角拷貝到右下角}}return;}/*copyodd:m為奇數(shù)時(shí)用,由前1組的m位選手的安排,來構(gòu)成第2組m位選手的賽程安排,以及兩組之間的比賽安排。這時(shí)和m為偶數(shù)時(shí)的處理有區(qū)別。*/voidcopyodd<intm>{inti,j;for<j=0;j<=m;j++>//1.求第2組的安排<前m天>{for<i=0;i<m;i++>//行{if<A[i][j]!=0>{A[i+m][j]=A[i][j]+m;}else//特殊處理：兩個隊(duì)各有一名選手有空,安排他們比賽{A[i+m][j]=i+1;A[i][j]=i+m+1;}}}///////////安排兩組選手之間的比賽<后m-1天>////////////////////////for<i=0,j=m+1;j<2*m;j++>{A[i][j]=j+1;//2.1號選手的后m-1天比賽A[<A[i][j]-1>][j]=i+1;//3.他的對手后m-1天的安排}//以下的取值要依賴于1號選手的安排,所以之前先安排1號的賽程for<i=1;i<m;i++>//第1組的其他選手的后m-1天的安排{for<j=m+1;j<2*m;j++>{//2.觀察得到的規(guī)則一：向下m+1~2*m循環(huán)遞增A[i][j]=<<A[i-1][j]+1>%m==0>?A[i-1][j]+1:m+<A[i-1][j]+1>%m;//3.對應(yīng)第2組的對手也要做相應(yīng)的安排A[<A[i][j]-1>][j]=i+1;}}return;}/*makecopy:當(dāng)前有m位〔偶數(shù)選手,分成兩組,每組由m/2位選手構(gòu)成由第一組的m/2位選手的安排來構(gòu)成第二組的比賽安排,第一組與第二組的比賽安排。要區(qū)分m/2為奇數(shù)和偶數(shù)兩種情況*/voidmakecopy<intm>{if<i