问题描述:
设有n=2k个选手要进行网球循环赛,要求设计一个满足以下要求的比赛日程表:
(1)每个选手必须与其他n-1个选手各赛一次;
(2)每个选手一天只能赛一次。
按此要求,可将比赛日程表设计成一个 n 行n-1列的二维表,其中,第 i 行第 j 列表示和第 i 个选手在第 j 天比赛的选手。
算法分析:
假设n位选手被顺序编号为1,2,3,...,n,比赛的日程表是一个n行n-1列的表格,i行j列的表格内容是第i号选手在第j天的比赛对手。根据分而治之的原则,可从其中一半选手(2^(n-1位)的比赛日程,导出全体n位选手的日程,最终细分到只有两位选手的比赛日程出发。 可假设只有8位选手参赛,若1至4号选手之间的比赛日程填在日程表的左上角(4行3列),5至8号选手之间的比赛日程填在日程表的左下角(4行3列);那么左下角的内容可由左上角的对应项加上数字4得到。至此,剩余的右上角(4行4列)是为编号小的1至4号选手与编号大的5至8号选手之间的比赛日程安排。例如,在第4天,让1至4号选手分别与5至8号选手比赛,以后各天,依次由前一天的日程安排,让5至8号选手“循环轮转”即可。最后,比赛日程表的右下角的比赛日程表可由,右上角的对应项减去数字4得到。
编程图例: =================================================================== |*|选手1天2天3天4天5天6天7天|*| =================================================================== |*|1号|2|3|4||5|6|7|8|*| |*|2号|1|4|3||6|7|8|7|*| |*|3号|4|1|2||7|8|5|6|*| |*|4号|3|2|1||8|5|6|5|*| ========[左上角]========================[右上角]=================== |*|5号|6|7|8||1|4|3|2|*| |*|6号|5|8|7||2|1|4|3|*| |*|7号|8|5|6||3|2|1|4|*| |*|8号|7|6|5||4|3|2|1|*|
========[左下角]========================[右下角]===================
程序代码(C语言):
#include #include int calendar[100][100]; //日程表数组 void game(int k) { int p,q,m,number,i,j; number=k; p=m=1; calendar[1][1]=2; calendar[2][1]=1; while(m
如果觉得《c语言单循环赛制 循环赛日程安排问题(分治法)》对你有帮助,请点赞、收藏,并留下你的观点哦!