




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、一、 问题表述:设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表,(1) 每个选手必须与其他n-1个选手各赛一次;(2) 每个选手一天只能赛一次;(3) 当n是偶数时,循环赛进行n-1天,当n是奇数时,循环赛进行n天二、 分析问题题目是要n名运动员进行循环比赛。当n为偶数时,正好每天都可以两两一组,与其余的n-1个选手比赛,只需n-1天; 而当n为奇数,每天将有一个选手轮空,比赛将持续n天。可以采用的算法如下:1. 算法一:使用分治法当n为偶数时,可以讲问题分为两个部分n/2; 然后继续划分,知道最后剩余两名选手单独比赛。当n为奇数时,增设一个虚拟选手,运动员为n+1个,将问题
2、转化为是偶数的情形。当选手与虚拟选手比赛时,表示轮空,因此只需要关注n为偶数的情形。a) 当n/2为偶数时,与n = 2k情形类此。b) 当n/2为奇数时,增设一个虚拟的选手,递归返回的将有轮空的选手,可以讲在前面n/2轮比赛的选手与后面n/2轮空的选手进行比赛。2. 算法二:利用边是奇数的正多边形。特点:以多边形中的任意一个顶点画对称轴,其余偶数对顶点相互对称。N名选手编号为1n,将其画成一个正多边形。a) 所以当n为奇数时,第一天1号休息,其余以一号为对称轴,两两对称打比赛,第二天开始一次轮流休息,其余一休息的那个人编号为对称轴,两两比赛。这样比赛可进行n天。如图:此时n=9,为奇数,从0
3、开始每天有一个人轮空对称轴对称轴b) 当n为偶数时,取出编号最大的,其他的组成一个正多边形,n号一次顺序与1,2,。n-1号选手比赛,其他与a)相同。如图所示:(图中是从0开始编号)99 N=2k时 9三、 理论分析算法及实现1. 算法一:使用分治法a) 算法的思路:按分治策略,可以将所有的选手对分为两组(如果n是偶数,则直接分为n/2每组,如果n是奇数,则取(n+1)/2每组),n个选手的比赛日程表就可以通过为(n/2或(n+1)/2)个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行分割,直到只剩下2个选手时,比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以
4、了。下图给出的是六个选手的比赛日程表,其中第一列表示1-6个选手,第二列到第六列表示各个选手在第一天到第五天的所遇到的选手。1 2 3 4 5 62 1 5 3 6 43 6 1 2 4 54 5 6 1 3 25 4 2 6 1 36 3 4 5 2 1在这里算法设计的难点就是分开治理后的合并问题。这里我就结合上面给出的6个选手的示例来进行表述。首先,将6个选手分为对等的两组,每组3个选手。每组增设一个虚拟的选手,然后再递归的将3个选手分为对等两组,每组2个选手。在2个选手情况下,这两个选手比赛。可以得到两个选手的日程安排表是:1 22 1接下来的任务是合并这两组2个选手的日程表得到3个选手
5、的日程安排表,这里我先假设有4个选手参加比赛则:1 22 13 44 3接下来的比赛里,第二天让1和3比赛,2和4比赛;第三天让1和4比赛,2和3比赛,即让前一组的选手,循环的和后一组的选手比赛,可得到比赛日程安排表是:1 2 3 42 1 4 33 4 1 24 3 2 1这里要得到的是3个选手的日程安排表,则第4个选手是假想的选手将其用0来表示则得到3个选手的日程安排表:1 2 3 02 1 0 33 0 1 2接下来的任务是合并这两个3个选手的日程安排表得到6个选手的日程安排表,这里我们的两组选手前3天的比赛情况如下:1 2 3 02 1 0 33 0 1 24 5 6 05 4 0 6
6、6 0 4 5其中第一天选手3和选手6都没有对手,让他们两个比赛;第二天选手2和选手5没有对手,让他们两个比赛,;第三天选手1和选手4没有对手,让他们两个比赛。这就可以得到合并后6个选手前三天的比赛日程安排表:1 2 3 42 1 5 33 6 1 24 5 6 15 4 2 66 3 4 5将在前三天比过赛的两组的选手对应的列出来:1 2 34 5 6在这里可以看到合并的两组中3和6,2和5,1和4都已经比过了,这里就跳过这些选手的比赛,然后两个组循环比赛即:1 2 35 6 4和1 2 36 4 5这样就得到了6个选手的比赛完整的日程安排表:1 2 3 4 5 62 1 5 3 6 43
7、6 1 2 4 54 5 6 1 3 25 4 2 6 1 36 3 4 5 2 1b) 证明算法的正确性:(1) 在n=2时,就这两个选手比赛,比赛只进行一天,这也是算法的初始情况,算法成立。(2) 在n=k时,如果k为偶数,则将k个选手分为k/2的两组,这样按问题的要求k个选手共比赛k-1天,k/2个选手如果是偶数则比赛(k/2)-1天,在合并的时候两组k/2个选手循环比赛需要k/2天,则先分组后合并共需要(k/2)-1+(k/2)=k-1天;k/2个选手如果是奇数则比赛k/2天,在合并的时候两组中每个选手都相对应的比赛过了一次,所以两组k/2个选手循环比赛需要(k/2)-1天,则先分组后
8、合并共需要(k/2)+(k/2)-1=k-1天。(3) k为奇数的情况和k为偶数的情况类似。c) 算法的描述和架构:分治法主要就是用 当n=2k时 void tournament(int n)if(n = 1)a11 = 1;return;Tournament(n/2); Copy(n);主要是将左上角的递归计算出的小块中的所有数字按照其相对位置抄写到右下角,将左上角小块中的所有数字加n/2后按照其相对位置抄写到左下角,将左下角小块中的所有数字按照相对位置抄到右上角。问题:n或者n/2可能不是偶数,此时就要虚拟增加一个队员。if(odd(n) /如果是奇数tournament(n + 1);r
9、eturn;elsetournament(n/2); /是偶数时,递归调用,返回时合并makecopy(n);合并环节是最重要的,如果是n偶数的话,如上面的函数copy(n),但是如果是奇数,需要调用copyodd(n)void copyodd(int n)int m = n /2;int i,j;for(i = 1; i <= m; i+) /i的范围是<=m,所以超出m的范围就不算了 for(j = 1; j <= m + 1; j+) if(aij > m) /如果有轮空的话,就让前n/2轮空的选手去后n/2轮空的选手比赛 aij = m + i;am + ij
10、= i;elseam + ij = aij +m; for(j = 2; j <=m; j+) int k,r = i;if(i + j - 1 > m) k = i + j -1;elsek = m + i + j - 1;arm + j = k; akm + j = r;其中后n/2天比赛中,是前n/2选手和后n/2的选手比赛,这点很值得推敲。架构: Tournament(n)输入运动员的个数 nN为奇N = n +1N为偶Tournament(n/2)N =1 makecopy(n)N为偶N为奇Copy(n)Copyodd(n)2. 算法二:利用边是奇数的正多边形。在第二部分
11、图解中已经比较详细描述过,最难想到的一个规律是,对称之后如何转换,如下图;9以n=10为例子,比如以1对称轴,0和2对称,8和3对称,7和4对称,6和5对称,除了 arj = k, akj = r之外,还有什么规律呢? 经过多次画图之后发现,当对称轴变为2时,3和0对称,8和5对称,7和6对称,转变相邻的对称轴,原来对称点的位置改变了两个距离。以前8和3对称,现在8和5对称,增加了两个,以前7和4对称,现在7和6对称; 但是以前3和8对称,现在是和0对称啊,8到1可不是增加了2啊,是的,但是再想循环的数的个数是9,8+2=10, 10%9 =1啊,所以这样一想就可以豁然开朗了。所以就有:由第一
12、列可知, ai1=n-i+1;所以对应的 ai+jj = ai+jj-1 + 2 = ai+j1 + 2*(i-1)=n+i-j-1于是产生了如下算法:当n为偶数时:void tournament_even(int n)int i, j, m;m = n -1; /如上图所示,取出编号最大的数,构成奇多边形for(i = 1; i <= m; i+)aii = n;for(j = 1; j <= m/2; j+) ani = i;int r = (i + j) % m;if(r =0)r = m;int k = (i + n - j -1) % m;if(k = 0)k = m;a
13、ri = k;aki = r;由对称规律,知道对称轴一旁的顶点的对应点,则比赛对手也同样明确了。所以j只需要取m/2一半就够了。所以对称轴是i时, aii=n;在需要知道对称轴这侧的一般就可以了 即: jß1 to jßm/2的ai+ji就可以了,所以就有了同理当n为奇数时相似。void tournament_odd(int n)int i, j;for(i = 1; i<=n; i+)aii = -1;for(j = 1; j <= n/2; j+)int r = (i + j) % n;if(r = 0)r = n;int k = (i + n - j) % n;if(k =0)k = n;ari
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年地震勘探数据处理系统项目建议书
- 2025年薄涂型地坪漆项目发展计划
- 补体与临床治疗
- 酒店千里马系统培训
- 动画制作与游戏设计作业指导书
- 股份制企业合作协议与章程制定指南
- 快消品市场推广与销售策略手册
- 耐挫教育主题班会
- 采油安全经验分享100例
- 建设工程经济技术服务合同
- 中国古代四大发明(小学课件)
- 事故隐患报告举报奖励制度培训
- 广西壮族风俗演示文稿课件
- 新生儿疼痛管理指南2028
- 三年级下册口算天天100题(A4打印版)
- 医院安全生产问题分析报告
- 物权法教案完整版本
- 辅警必考题库以及结构化面试题及答案(2024年完整版)
- 财务用发票分割单原始凭证 发票分割单范本
- 《数字电子技术基础》 题库 各章测试题习题答案
- 辽宁省高中学业水平合格性考试生物试卷(附带答案)
评论
0/150
提交评论