循环日程表

实

姓 名 课程名称 成 绩 实验项目名称 学 号 验报告

专业班级 信息管理与信息系统 实验室 B412 202323232 算法设计与分析 指导教师 循环赛日程表 一、实验目的： 1.学习用多种算法解决所遇到的问题，更好的巩固前面学过的内容，灵活掌握和运用算法策略 2.拓展解决问题的思路，提高对java的认识，提高算法设计和识别算法的优劣能力，更好的分析和解决问题 二、实验内容： 设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表。 （1） 每个选手必须与其他n-1个选手各赛一次。 （2） 每个选手一天只能赛一次。 （3） 循环赛在n-1天结束。 请按此要求讲比赛日程表设计成有n行和n-1列的一个表。在表的第i行，第j列处填入第i个选手在第j天所遇到的选手，其中1<=i<=n,1<=j<=n-1。 三、实验步骤（要求有截图）： 算法1： 本程序用二分法递归策略将所有选手分为两半，n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。 }import java.util.Scanner; public class RobinSchedule1{ static int a[][]=new int[100][100]; public static void main(String []args){ System.out.print(\"Please input k:\"); Scanner s=new Scanner(System.in); int k=s.nextInt(); int n=1,i,j; for(i=1;i<=k;i++) n=n*2; System.out.println(n+\"个人比赛的循环赛日程表为：\"); dimidiate(1,n,n); for (i=1;i<=n;i++){ System.out.println(); for (j=1;j<=n;j++) System.out.printf(\"%4d\ } } public static void dimidiate(int i,int j,int n){ int k1,k2; if(n==2){ a[i][n]=j; a[j][n]=i; a[i][n-1]=i; a[j][n-1]=j; } else{ dimidiate(i,i+n/2-1,n/2); dimidiate(i+n/2,j,n/2); for(k1=n;k1>n/2;k1--){ for(k2=i;k2<=i-1+n/2;k2++) a[k2][k1]=a[k2+n/2][k1-n/2]; for(k2=i+n/2;k2<=i-1+n;k2++) a[k2][k1]=a[k2-n/2][k1-n/2]; } } } } 本题中算法按二分策略，将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程来决定，递归的用这种一分为二的策略对选手进行策划，知道只剩下两个选手时，比赛日程表的制定就变得很简单。 算法4: 本算法利用二维递推来实现。 源代码及注释如下所示： import java.util.Scanner; public class RobinSchedule4{ public static void main(String []args){ int a[][]=new int[50][50]; a[1][1]=1; int n,n0,i,j,k,k0; System.out.println(\"Please input k:\"); Scanner input=new Scanner(System.in); k=input.nextInt(); n0=1; n=2; for(k0=1;k0<=k;k0++){ for(i=n0+1;i<=n;i++){ for(j=1;j<=n;j++){ a[i][j]=a[i-n0][j]+n0; } } for(j=n0+1;j<=n;j++){ for(i=1;i<=n0;i++){ a[i][j]=a[i][j-n0]+n0; } } for(j=n0+1;j<=n;j++){ for(i=n0+1;i<=n;i++){ a[i][j]=a[i][j-n0]-n0; } } n0=n; n=n*2; } n=n/2; System.out.println(n+\"个人比赛的循环赛日程表为：\"); for(i=1;i<=n;i++){ System.out.println(); for(j=1;j<=n;j++){ System.out.printf(\"%4d\ } } } } 本算法根据行号、列号与规模之间的关系找出左下、右上、右下三部分的递推关系，最终实现二维循环赛日程表。 四、实验结果（要求有截图）： 编译并运行算法的代码： 算法1截图如下： 算法4截图如下： 五、实验分析： 无论哪种算法，都是可以实现在后预期目标，从具体到抽象是认识世界的基本方法，也是进行算法基本设计的进本方法。本实验除了加强对java的熟悉程度之外，对算法的设计也有了一定的进步，算法设计能力也得到了提高。在以后的学习生活中，针对一个问题，并不是只有单一的方法，用不用的算法策略，不同的数据结构和不同的数学模型进行多方位的算法设计，可以的到更好的效果