分治法循环赛日程表实验报告.doc

西北农林科技大学信息工程学院算法分析与设计综合训练实习报告题 目：分治法循环赛日程表 学 号姓 名专业班级指导教师实践日期2011年5月16日-5月20日目 录一、综合训练目的与要求1二、综合训练任务描述1三、算法设计1四、详细设计及说明3五、调试与测试4六、实习日志5七、实习总结6八、附录：核心代码清单6一、综合训练目的与要求本综合训练是软件工程专业重要的实践性环节之一，是在学生学习完算法分析课程后进行的综合练习。本课综合训练的目的和任务：（1）巩固和加深学生对算法分析课程基本知识的理解和掌握；（2）培养利用算法知识解决实际问题的能力；（3）掌握利用程序设计语言进行算法程序的开发、调试、测试的能力；（4）掌握书写算法设计说明文档的能力；（5）提高综合运用算法、程序设计语言、数据结构知识的能力。二、综合训练任务描述假设有n=2k 个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次（2）每个选手一天只能赛一次（3）循环赛一共进行n-1天利用Java语言开发一个界面，输入运动员的个数，输出比赛日程表。对于输入运动员数目不满足n=2k时，弹出信息提示用户。三、算法设计(1) 文字描述假设n位选手顺序编号为1，2，3n，比赛的日程表是一个n行n-1列的表格。第i行j列表示第i号选手在第j天的比赛对手，根据分治法，要求n个选手的比赛日程，只要知道其中一半的比赛日程，所以使用递归最终可以分到计算两位选手的比赛日程，然后逐级合并，得出结果。(2) 框图NYY输入nNerrorn=2k?n=n/2a11=1, n=n*2n=1?NYNYi=m?Int j=1j=m?aij + m = aij + m;ai + mj = aij + m;ai + mj + m = aij;j+i+OVERInt i=1m=n/2图 1(3) 伪代码static int a = new int100100;static int athletes; static int n;static void copy(int n) / 核心代码int m = n / 2;for (int i = 1; i = m; i+)for (int j = 1; j = m; j+) aij + m = aij + m;/ 由左上角数的值算出对应的右上角数ai + mj = aij + m;/ 把右上角数的值赋给对应的左下角数ai + mj + m = aij;/ 把左上角数的值赋给对应的右下角数static void tournament(int n) / 分治算法，递归调用自己if (n = 1) a11 = 1;return;tournament(n / 2); / 分治copy(n); / 合并public static void main(String args) n=getText();athletes = n;tournament(n);四、详细设计及说明（1）输入一个数字n，根据（x&（x-1）=0判断n是否等于2k。不是则提示出错，要求重新输入（2）按照分治的策略，将所有参赛的选手分为两部分，tournament(int n) 使n=n/2,递归调用自身，直到n=1.（3）n=1得出a11 = 1之后，开始逐级合并，n=n*2，m=n/2，由aij + m = aij + m得出a12，由ai + mj = aij + m得出a21，由ai + mj + m = aij得出a22，如下所示：1221表1（4）继续n=n*2，m=n/2，可以仍把它看做均分的四个区域，仍然按照右上，左下，右下的顺序计算。由a11得出a13，由a12得出a14，由a21得出a23，由a22得出a24，（即由左上角数的值算出对应的右上角数）由a13得出a31，由a14得出a32，由a23得出a41，由a24得出a42，（即把右上角数的值赋给对应的左下角数）由a11得出a33，由a12得出a34，由a21得出a43，由a22得出a44，（即把左上角数的值赋给对应的右下角数）如下图：表21234214334124321（5）继续照这样递归，直到算出aij所有的值五、调试与测试测试结果：图2 输入不是2的阶次方的数图3 输入数16的结果六、实习日志5月16日理解题意，题目要求，确定使用分治法解决5月17日根据书上分治法的设计思路以及所提供的代码按题目要求设计算法，并根据算法写出核心代码，在C+上实现。5月18日在JAVA上实现除界面以外的要求，然后添加界面代码5月19日用SWING实现界面，并解决两位数输出无法对齐的问题5月20日完成文档和PPT，准备答辩七、实习总结根据分治算法，将本问题进行了由小规模到大规模的求解设计，程序设计的关键点在于如何对整个数组中分出的3个数块进行赋值，运用了两个for循环和三条赋值语句实现。通过这次程序设计，加深了对分治算法的认识。解决具体问题时，程序故重要，但一个好的算法更加重要。不足之处即花费了很长时间来推导这个算法，对算法掌握还不够熟练。八、附录：核心代码清单（1）算法核心：static void copy(int n) / 核心代码，计算右上角数，并根据右上-左下和左上-右下原则赋值int m = n / 2;for (int i = 1; i = m; i+)for (int j = 1; j = m; j+) aij + m = aij + m;/ 由左上角数的值算出对应的右上角数ai + mj = aij + m;/ 把右上角数的值赋给对应的左下角数ai + mj + m = aij;/ 把左上角数的值赋给对应的右下角数static void tournament(int n) / 分治算法，递归调用自己if (n = 1) a11 = 1;return;tournament(n / 2); / 分治copy(n); / 合并（2）界面（包含窗体，标签，文本域，文本框，按钮）：public Board() / 构造界面super();/ 继承父类构造方法setTitle(循环赛安排计算器);/ 窗体标题setBounds(350, 200, 800, 600);/ 窗体位置大小getContentPane().setLayout(null);/ 不采用布局管理器setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);/ 设置窗体关闭按钮的动作为退出final JLabel inputofk = new JLabel();/ 创建标签对象inputofkinputofk.setBounds(25, 25, 80, 25);/ 标签位置大小inputofk.setText(请输入k值：);/ 标签内容getContentPane().add(inputofk);/ 将标签添加到窗体中final JLabel outputofresult = new JLabel();/ 创建标签对象outputofresultoutputofresult.setBounds(250, 20, 100, 25);/ 标签位置大小outputofresult.setText(比赛安排结果：);/ 标签内容getContentPane().add(outputofresult);/ 将标签添加到窗体中final JTextArea result = new JTextArea();/ 创建文本域对象resultresult.setColumns(45);/ 文本域显示文字列数result.setRows(22);/ 文本域显示文字行数result.setFont(new Font(, Font.BOLD, 14);/ 字体result.setLineWrap(false);/ 不自动换行final JScrollPane scrollPane = new JScrollPane();/ 创建滚动面板对象scrollPane.setViewportView(result);/ 将文本域添加到滚动面板中Dimension dime = result.getPreferredSize();/ 获得文本域的首选大小scrollPane.setBounds(200, 50, dime.width, dime.height);/ 滚动面板位置大小getContentPane().add(scrollPane);/ 将滚动面板添加到窗体中final JTextField valueofk = new JTextField();/ 创建文本框对象valueofkvalueofk.setHorizontalAlignment(JTextField.CENTER);/ 文本框内容的水平对齐方式valueofk.setBounds(20, 100, 80, 25);/ 文本框显示位置大小getContentPane().add(valueofk);/ 将文本框添加到窗体中final JButton yes = new JButton();/ 创建按钮对象yes.setBounds(30, 180, 60, 25);/ 按钮位置大小yes.setText(确定);/ 按钮标签内容（3）动作监听和事件处理：class ButtonAction implements ActionListener / 编写动作监听器类public void actionPerformed(ActionEvent e) String buttonName = e.getActionCommand();/ 获得触发事件的按钮的标签文本if (buttonName.equals(确定) / 如果按下确定int n;/ n个运动员n = Integer.parseInt(valueofk.getText();/ 将文本框中的字符串转化为整型赋给nif (n & (n - 1) != 0) |(n=0)JOptionPane.showMessageDialog(null,输入的数字不是2的阶次方，请重新输入, 警告,JOptionPane.ERROR_MESSAGE);/ 用JOptionPane标准的错误信息提示输入错误return;athletes = n;tournament(n);result.setText(null);/ 清空文本域result.append(运动员有 + athletes + 名 + n + 安排如下);result.append(n + 人员/天数);for (int l = 1; l = athletes - 1; l+) / 输出天数if (l 10) String day = String.format(%6d, l);/ 若l小于10则比大于10的数多输出一位以便对齐result.append(day); else String day = String.format(%5d, l);/ 将l转化为5位长度字符串result.append(day);result.append(n + );for (int i = 1; i = athletes; i+)/ 输出数组aijfor (int j = 1; j = athletes; j+) if (aij 10) String str = String.format(%6d, aij);/ 若aij小于10则比大于10的数宽度多输出一位以便对齐result.append(str); else String str = String.format(%5d, aij);/ 将数组aij中的数字转化为5位长度字符串result.append(str);/ 输出字符串，即将aij中的数输出result.append(n + );yes.addActionListener(new ButtonAction();/ 为按钮添加动作监听器getContentPane().add(yes);/ 将按钮添加到窗体中9