/*
标题：>应试编程实例-[分而治之算法程序设计] 作者：成晓旭 时间：2002年09月15日(11:58:00-13:18:00) 实现“装箱”问题的贪婪算法实现函数
*/
#include "stdio.h"#include "stdlib.h"//:====================“循环赛日程安排”问题的分而治之解决算法====================/* 作者：成晓旭 时间：2002年09月15日(11:58:38-20:00:00) 完成“循环赛日程安排”问题的分而治之解决算法 =================================================== 问题描述: 设有n(n = 2^k)位选手参加网球循环赛，循环赛共进行n-1天，每位选手要与 其他n-1位选手比赛一场，且每位选手每天必须比赛一场，不能轮空。试按此要求 为比赛安排日程。 编程思想: 假设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 |*| ========[左下角]========================[右下角]===================*/#define MAXN 64//日程表数组int calendar[MAXN + 1][MAXN];void Round_Robin_Calendar(){ int i,j,m,number,p,q; printf("输入选手个数：(注意:2^k) "); scanf("%d",&number); //预置两位选手的比赛日程表://第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; //左下角的内容 = 左上角的对应项加上数字4[] //填充日程表的右上角 //填充日程表的右上角的第1列 calendar[1][p] = p + 1; for(i = 2;i p;i++) calendar[i][p] = calendar[i - 1][p] + 1; //填充日程表的右上角的其他列,参照前一列填充当前列[循环轮转算法] 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; //关键语句 for(i = 1;i q;i++) { for(j = 1;j q;j++) printf("%4d",calendar[i][j]); printf(" "); } printf(" "); }}//:====================“循环赛日程安排”问题的分而治之解决算法====================int main(int argc, char* argv[]){ Round_Robin_Calendar(); printf(" 应用程序运行结束！ "); return 0;}Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=935878