`
- 浏览:
901953 次
-
/**//*
标题:<<系统设计师>>应试编程实例-[分而治之算法程序设计]
作者:成晓旭
时间: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|*|
========[左下角]========================[右下角]===================
*/
#defineMAXN64
//日程表数组
intcalendar[MAXN+1][MAXN];
voidRound_Robin_Calendar()
...{
inti,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(" ");
}
}
//:====================“循环赛日程安排”问题的分而治之解决算法====================
intmain(intargc,char*argv[])
...{
Round_Robin_Calendar();
printf(" 应用程序运行结束! ");
return0;
}
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
“循环赛日程安排”问题的分而治之解决算法.pdf
经典算法 分而治之算法.rar 经典算法 分而治之算法.rar
本章将首先介绍怎样在算法设计领域应用这一古老的策略,然后将利用这一策略解决如下问题:最小最大问题、矩阵乘法、残缺棋盘、排序、选择和一个计算几何问题——找出二维空间中距离最近的两个点。 本章给出了用来...
数据结构与算法中算法部分有关于分而治之算法的PPT教程
ES6的JavaScript算法思想实现之分而治之,动态规划,贪心算法和回溯算法 贪心算法和动态规划.pdf
14分而治之算法[汇编].pdf
用分而治之方法可以很好地解决残缺棋盘问题。
这是用分治法解决循环赛日程安排问题,分治法的最主要的特征就是分而治之
C语言的算法
分而治之的算法分而治之的算法分而治之的算法分而治之的算法
这是《算法设计与分析》中的一个程序,方法是用分而治之,作用是快速排序。
大整数相乘问题利用分而治之算法--来源于平时的作业
字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法...
分而治之的思想解决求一个数组的最大子集,有效的降低了时间复杂度,值得学习。
分而治之是一种使用递归解决问题的算法,主要的技巧是将一个大的复杂的问题划分为多个子问题,而这些子问题可以作为终止条件,或者在一个递归步骤中得到解决,所有子问题的解决结合起来就构成了对原问题的解决 ...
针对该问题,提出了基于分而治之的快速多维尺度定位算法DMDS-MAP,剔除参与转换的冗余数据,可有效提高原始MDS-MAP算法的定位速度。DMDS-MAP算法将距离矩阵进行划分,选取对角阵作为子矩阵以剔除冗余数据,通过奇异...
在人工智能时代,已经部署了高度复杂的算法来提供分析、检测模式、优化解决方案、加速操作、促进自我学习、最大程度地减少人为错误和偏见并促进技术产品和服务的改进。 尽管有这些巨大的好处,算法和智能机器并没有...
常用算法大全-分而治之算法.doc