分享
 
 
 

“循环赛日程安排”问题的分而治之解决算法

王朝other·作者佚名  2007-09-29
窄屏简体版  字體: |||超大  

/**//*

标题:<<系统设计师>>应试编程实例-[分而治之算法程序设计]

作者:成晓旭

时间: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;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有