問題描寫敘述:
? ? ? ? ? ? 設(shè)有n(n = 2^k)位選手參加網(wǎng)球循環(huán)賽，循環(huán)賽共進(jìn)行n-1天，每位選手要與
? ? ? ? 其它n-1位選手比賽一場(chǎng)，且每位選手每天必須比賽一場(chǎng)，不能輪空。試按此要求
? ? ? ? 為比賽安排日程。


? ? 編程思想:
? ? ? ? ? ? 如果n位選手被順序編號(hào)為1,2,3,...,n，比賽的日程表是一個(gè)n行n-1列的表格，
? ? ? ? i行j列的表格內(nèi)容是第i號(hào)選手在第j天的比賽對(duì)手。
? ? ? ? ? ? 依據(jù)分而治之的原則，可從當(dāng)中一半選手(2^(n-1位)的比賽日程，導(dǎo)出全體n位
? ? ? ? 選手的日程，終于細(xì)分到僅僅有兩位選手的比賽日程出發(fā)。
? ? ? ? ? ? 可如果僅僅有8位選手參賽，若1至4號(hào)選手之間的比賽日程填在日程表的左上角
? ? ? ? (4行3列)，5至8號(hào)選手之間的比賽日程填在日程表的左下角(4行3列)；那么左下角的
? ? ? ? 內(nèi)容可由左上角的相應(yīng)項(xiàng)加上數(shù)字4得到。至此，剩余的右上角(4行4列)是為編號(hào)小的
? ? ? ? 1至4號(hào)選手與編號(hào)大的5至8號(hào)選手之間的比賽日程安排。比如，在第4天，讓1至4號(hào)選
? ? ? ? 手分別與5至8號(hào)選手比賽，以后各天，依次由前一天的日程安排，讓5至8號(hào)選手“循環(huán)
? ? ? ? 輪轉(zhuǎn)”就可以。
? ? ? ? 最后，比賽日程表的右下角的比賽日程表可由，右上角的相應(yīng)項(xiàng)減去數(shù)字
? ? ? ? 4得到。
? ? 編程圖例:
? ? ? ??
? ? ===================================================================
? ? |*| 選手 ? ?1天 ? ? ? ?2天 ? ? ? ?3天 ? ? ? ?4天 ? ? ? ?5天 ? ? ? ?6天 ? ? ? ?7天 ? ?|*|
? ? ===================================================================
? ? |*| ? ?1號(hào) ? ?| ? ?2 ? ?| ? ?3 ? ?| ? ?4 ? ?|| ? ?5 ? ?| ? ?6 ? ?| ? ?7 ? ?| ? ?8 ? ?|*|
? ? |*| ? ?2號(hào) ? ?| ? ?1 ? ?| ? ?4 ? ?| ? ?3 ? ?|| ? ?6 ? ?| ? ?7 ? ?| ? ?8 ? ?| ? ?7 ? ?|*|
? ? |*| ? ?3號(hào) ? ?| ? ?4 ? ?| ? ?1 ? ?| ? ?2 ? ?|| ? ?7 ? ?| ? ?8 ? ?| ? ?5 ? ?| ? ?6 ? ?|*|
? ? |*| ? ?4號(hào) ? ?| ? ?3 ? ?| ? ?2 ? ?| ? ?1 ? ?|| ? ?8 ? ?| ? ?5 ? ?| ? ?6 ? ?| ? ?5 ? ?|*|
? ? ========[左上角]========================[右上角]===================
? ? |*| ? ?5號(hào) ? ?| ? ?6 ? ?| ? ?7 ? ?| ? ?8 ? ?|| ? ?1 ? ?| ? ?4 ? ?| ? ?3 ? ?| ? ?2 ? ?|*|
? ? |*| ? ?6號(hào) ? ?| ? ?5 ? ?| ? ?8 ? ?| ? ?7 ? ?|| ? ?2 ? ?| ? ?1 ? ?| ? ?4 ? ?| ? ?3 ? ?|*|
? ? |*| ? ?7號(hào) ? ?| ? ?8 ? ?| ? ?5 ? ?| ? ?6 ? ?|| ? ?3 ? ?| ? ?2 ? ?| ? ?1 ? ?| ? ?4 ? ?|*|
? ? |*| ? ?8號(hào) ? ?| ? ?7 ? ?| ? ?6 ? ?| ? ?5 ? ?|| ? ?4 ? ?| ? ?3 ? ?| ? ?2 ? ?| ? ?1 ? ?|*|

? ? ========[左下角]========================[右下角]===================

#define MAXN 64 //日程表數(shù)組 int calendar[MAXN + 1][MAXN]; void Round_Robin_Calendar() {int i,j,m,number,p,q;printf("輸入選手個(gè)數(shù)：(注意:2^k) ");scanf("%d",&number);//預(yù)置兩位選手的比賽日程表://第i位選手第j天與第calendar[i][j]位選手比賽calendar[1][1] = 2; //第1位選手第1天與第2位選手比賽calendar[2][1] = 1; //第2位選手第1天與第1位選手比賽m = 1;p = 1;while(m < number){m ++;//p = p + p;p += p;q = 2 * p; //為2^m位選手安排比賽日程//填充日程表的左下角for(i = p + 1;i <= q;i++)for(j = 1;j<= p - 1;j++)calendar[i][j] = calendar[i - p][j] + p; //左下角的內(nèi)容 = 左上角的相應(yīng)項(xiàng)加上數(shù)字4[]//填充日程表的右上角//填充日程表的右上角的第1列calendar[1][p] = p + 1; for(i = 2;i <= p;i++)calendar[i][p] = calendar[i - 1][p] + 1;//填充日程表的右上角的其它列,參照前一列填充當(dāng)前列[循環(huán)輪轉(zhuǎn)算法]for(j = p + 1;j < q;j++){for(i = 1;i < p;i++)calendar[i][j] = calendar[i + 1][j - 1];calendar[p][j] = calendar[1][j - 1];}//填充日程表的右下角for(j = p;j < q;j++)for(i = 1;i <= p;i++)calendar[calendar[i][j]][j] = i; //關(guān)鍵語句for(i = 1;i <= q;i++){for(j = 1;j < q;j++)printf("%4d",calendar[i][j]);printf(" ");}printf(" ");} } //:====================“循環(huán)賽日程安排”問題的分而治之解決算法====================int main(int argc, char* argv[]) {Round_Robin_Calendar();printf(" 應(yīng)用程序執(zhí)行結(jié)束！ ");return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/blfshiye/p/4369001.html

總結(jié)

以上是生活随笔為你收集整理的分治法之循环赛日程表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。