循环日赛表的分治实现
实现循环赛日程表。
设 有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表:
(1)每个选手 必须与其它n-1个选手各赛一次
(2)每个选手一天只能赛一场
(3)循环赛进行n-1天
基本思路:
按分治策略,将所有的的选手分为两组,N和选手的比赛日程表就可以通过N/2个选手设计的日程来决定。递归的对选手进行分割,直到只剩下2个选手时,比赛的日程表就变得简单。这时只要让这两个选手进行比较近好了。
实现思路:
我们可以创建一个二维数组来存放数据,int [][]table=new int[num][num];
在第一行和第一列放入数据来初始化数组
然后对数组进行递归处理
将左上角的数据写到右下角的数据,将右上角的数据写到左下角的数据。
看代码吧
private void sort(int x, int y, int step) { //如果递归到只剩下一步,即只剩下两个对手,返回 if(step==1)return; step/=2; //对左上右下的这条对角线上的数据进行递归 sort(x, y, step); //对右上左下的数据进行递归 sort(x,y+step,step); for(int i=0;i<step;i++) //对每个分区进行赋值 for(int j=0;j<step;j++){ //右下角的数据等于左上角的数据 table[x+step+i][y+step+j]=table[x+i][y+j]; //左下角的数据等于右上角的数据 table[x+step+i][y+j]=table[x+i][y+step+j]; } }
下面是运行的效果
java文件见附件(全部代码)
<!--EndFragment-->
相关推荐
设有n=2^k个运动员要进行羽毛球循环赛,现要设计一个满足以下要求的比赛日程表:(1)每个选手必须与其他n-1个选手各赛一次。(2)每个选手一天只能比赛一次。 (3)循环赛一共需要进行n-1天。用分治法实现
本文采用分治算法来解决循环赛日程表的安排问题。通过对问题的详细分析,列出1到10个选手的比赛日程表,找出两条规则,作为算法实现的依据,而后采用c语言实现算法,通过测试分析,程序运行结果正确,运行效率较高。...
循环赛日程表的分治算法实现实验报告_gxl.doc
用java实现的循环赛日程表程序。循环赛日程表是算法中的几个经典问题之一
循环赛日程表设计,分治法实现。
分治法实现循环赛问题1
循环赛日程安排问题是算法分析与设计中的经典问题,本程序采用C语言实现的,很好啊!!! 问题描述: 设有n(n = 2^k)位选手参加网球循环赛,循环赛共进行n-1天,每位选手要与其他n-1位选手比赛一场,且每位选手每天...
循环赛问题分析与C语言代码-分治法,详细分析与具体算法实现。
赛程表安排问题,有2的k次方(n)支球队,在n-1天两两比赛,每支球队每天只进行一场比赛,求安排日程表。资源是Java实现的算法。
用分治法求解循环赛日程表,简单的算法,但是实现这个问题还是有点困难,自己手动编写,大量注释,便于阅读。
循环赛算法是分治法的一种应用....然而在处理非2 个选手的循环赛日程表排列时, 问题就变得非常的复杂.本文针对非2 个选手的 循环赛13程安排问题提出了一种行向变换排列的 算法,并给出了实现的程序.
用分治法思想解决比赛日程安排问题,Java语言描述。
分治算法的几个经典例子及实现,有选择最接近的点,线性时间选择,循环日程赛
循环赛的关键问题在于巧妙的填充表格,来安排比赛时间。填充表格用了分治法。和课上讲的区别是有 n 为奇数的情况。分治法的思想也可用于奇数中,只需要添加一个虚拟对手。表格填充需要技巧,偶数的比较容易理解,...
(1)利用分治算法,编程实现循环赛日程表安排问题,并进行时间复杂性分析; (注:想最后成绩比较高的同学必须做:当N<>2k 的情况,有能力的同学也可做) (2)利用分治算法、蛮力法,编程实现最近点对问题,并进行...
15个典型的递归算法的JAVA实现,求N的阶乘、欧几里德算法(求最大公约数)、斐波那契数列、汉诺塔问题、树的三种递归遍历方式、快速排序、折半查找、图的遍历、归并排序、八皇后问题(回溯、递归)、棋盘覆盖(分治,...
1.5.7 循环队列的实现 1.5.8 实例与分析 1.6 树结构 1.6.1 树的概念 1.6.2 树结构的计算机存储形式 1.6.3 二叉树的定义 1.6.4.二叉树的遍历 1.6.5 创建二叉树 1.6.6 实例与分析 1.7 图结构 1.7.1 图的概念 1.7.2 图...