分治法赛程安排实验论文

1、算法分析与设计综合训练实习报告题 目：利用分治思想设计循环赛日程表 学 号姓 名专业班级指导教师实践日期目 录一、综合训练目的与要求1二、综合训练任务描述1三、算法设计1四、详细设计及说明1五、调试与测试1六、实习日志1七、实习总结1八、附录：核心代码清单1一、综合训练目的与要求本综合训练是软件工程专业重要的实践性环节之一，是在学生学习完算法分析课程后进行的综合练习。本课综合训练的目的和任务：1. 巩固和加深学生对算法分析课程基本知识的理解和掌握；2. 培养利用算法知识解决实际问题的能力；3. 掌握利用程序设计语言进行算法程序的开发、调试、测试的能力；4. 掌握书写算法设计说明文档的能力；5.

2、 提高综合运用算法、程序设计语言、数据结构知识的能力。二、综合训练任务描述有n个运动员要进行网球循环赛，设计比赛日程表：（1） 每个选手必须与其他n-1个选手赛一次；（2） 每个选手一天只能赛一次；（3） 当n是偶数时，循环赛进行n-1天；当n是奇数时，循环赛进行n天；（4） 要求掌握分治法或者多边形方法；（5） 设计一个界面，显示产生的日程表；（6） 编程语言不限；三、算法设计(1) 文字描述按分治策略，可以将所有的选手对分为两组（如果n是偶数，则直接分为n/2每组，如果n是奇数，则取（n+1）/2每组），n个选手的比赛日程表就可以通过为（n/2或（n+1）/2）个选手设计的比赛日程表来决定

3、。递归地用这种一分为二的策略对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 下图给出的是六个选手的比赛日程表，其中第一列表示1-6个选手，第二列到第六列表示各个选手在第一天到第五天的所遇到的选手。(2) 框图比赛人数nNNYNYNYYNYint i=1i=Ni+a1i=ii+m=1s=1s=k?N=N/2int t=1t=N?int i=m+1i=2*mj=m+1j=m+1aij+(t-1)*m*2 = ai-mj+(t-1)*m*2-maij+(t-1)*m*2-m = ai-mj+(t-1)*m*2j+i+t+s+m=m*2k+=

4、1伪代码public static void copy(int n) int m = n / 2;for (int i = 1; i = m; i+)for (int j = 1; j 1 & odd(n / 2)copyodd(n);elsecopy(n);public static void copyodd(int n) / 实现n/2为奇数时的复制int b = new intsize;int m = n / 2;for (int i = 1; i = m; i+) bi = m + i;bm + i = bi;for (int i = 1; i = m; i+) / 这个循环比较难看懂

5、，试着在纸上走走n=6时的情形，就能明白为什么要这么写for (int j = 1; j m) aij = bi;am + ij = (bi + m) % n; elseam + ij = aij + m;for (int j = 2; j = m; j+) aim + j = bi + j - 1;abi + j - 1m + j = i;四、详细设计及说明1.输入数字n判断n的奇偶性，根据情况进行分治法，安排赛程。2.用一个for循环输出日程表的第一行for (int i = 1; i = num - 1; i+) jb_s1i = new JButton(第 + i + 天);jb_s1

6、i.setBackground(Color.lightGray);centerPanel.add(jb_s1i);3.用一个for循环将问题分成几部分，对于k=3，n=8，将问题分成3大部分，第一部分为，根据已经填充的第一行，填写第二行，第二部分为，根据已经填充好的第一部分，填写第三四行，第三部分为，根据已经填充好的前四行，填写最后四行。for (int s=1;s=k;s+)N/=2;4.用一个for循环对4中提到的每一部分进行划分for(int t=1;t=N;t+)对于第一部分，将其划分为四个小的单元，即对第二行进行如下划分同理，对第二部分（即三四行），划分为两部分，第三部分同理5.最后

7、，进行每一个单元格的填充。填充原则是：对角线填充for(int i=m+1;i=2*m;i+)/i控制行for(int j=m+1;j=2*m;j+) /j控制列 aij+(t-1)*m*2 = ai-mj+(t-1)*m*2-m;/*右下角的值等于左上角的值 */ aij+(t-1)*m*2-m = ai-mj+(t-1)*m*2;/*左下角的值等于右上角的值 */ 例：由初始化的第一行填充第二行1234567821436587进行第二部分的填充12345678214365873412785643218765最后是第三部分的填充12345678214365873412785643218765

8、567812346587214378563412876543216.设计界面，让产生的表格输出，用java实现。五、调试与测试1.还未输入参数时：2.输入一个奇数测试：3.输入一个偶数测试：六、实习日志5月16日理解题意，题目要求，确定使用分治法解决。5月17日根据书上分治法的设计思路以及所提供的代码按题目要求设计算法。5月18日 根据算法写出代码，并测试调试。5月19日 根据代码，及要产生的表，用java设计界面。5月20日 总结，写论文，ppt等。七、实习总结根据分治算法，将本问题进行了由小规模到大规模的求解设计，程序设计的关键点在于如何对问题进行划分和填充公式的归纳。在划分时，主要运用了

9、两个for循环；在填充时，运用了两个for循环。通过这次程序设计，加深了对分治算法的认识。解决具体问题时，程序故重要，但一个好的算法更加重要。不足之处即花费了很长时间来推导这个算法，对算法掌握还不够熟练。八、附录：核心代码清单package .js3;import java.util.Scanner;import javax.swing.*;import javax.swing.table.*;import java.awt.*;import java.awt.event.*;import java.util.*;class text1 public static final in

10、t size = 50;public static int a = new intsizesize;public static void copy(int n) int m = n / 2;for (int i = 1; i = m; i+)for (int j = 1; j 1 & odd(n / 2)copyodd(n);elsecopy(n);public static void copyodd(int n) / 实现n/2为奇数时的复制int b = new intsize;int m = n / 2;for (int i = 1; i = m; i+) bi = m + i;bm +

11、 i = bi;for (int i = 1; i = m; i+) / 这个循环比较难看懂，试着在纸上走走n=6时的情形，就能明白为什么要这么写for (int j = 1; j m) aij = bi;am + ij = (bi + m) % n; elseam + ij = aij + m;for (int j = 2; j = m; j+) aim + j = bi + j - 1;abi + j - 1m + j = i;public class text implements ActionListener JFrame jf;JButton jb;JPanel centerPane

12、l;JTextField textField;JLabel jl_w;ImageIcon icon = new ImageIcon(qck.jpg);JPanel southpanel;JPanel wpanel;text1 text;public static void main(String args) text frame = new text();public text() jf = new JFrame(网球赛程表);jf.setBounds(150, 150, 550, 550);jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);f

13、inal JPanel viewPanel = new JPanel();Container c = jf.getContentPane();viewPanel.setBackground(Color.lightGray);textField = new JTextField();JLabel jl = new JLabel(请输入参赛队数：);/ jl.setBackground(Color.red);viewPanel.add(jl);textField.setColumns(10);viewPanel.add(textField);jb = new JButton(确定);jb.addA

14、ctionListener(this);viewPanel.add(jb);c.add(viewPanel, BorderLayout.NORTH);centerPanel = new JPanel();JLabel j = new JLabel();j.setText(欢迎使用网球赛程安排系统);j.setFont(new Font(, Font.BOLD, 16);j.setBounds(100, 100, 0, 0);j.setHorizontalAlignment(j.CENTER);j.setHorizontalTextPosition(j.CENTER);j.setVertical

15、TextPosition(j.BOTTOM);j.setIcon(icon);centerPanel.add(j);southpanel = new JPanel();jl_w = new JLabel(还未输入参赛队数);southpanel.add(jl_w);wpanel = new JPanel();JPanel epanel = new JPanel();c.add(centerPanel, BorderLayout.CENTER);c.add(southpanel, BorderLayout.SOUTH);c.add(wpanel, BorderLayout.WEST);c.add

16、(epanel, BorderLayout.EAST);jf.setVisible(true);public void actionPerformed(ActionEvent e) if (e.getSource() = jb) String str = textField.getText();int num = Integer.parseInt(str);centerPanel.removeAll();centerPanel.repaint();centerPanel.validate();final GridLayout gridLayout = new GridLayout(num +

17、1, num);centerPanel.setLayout(gridLayout);text.tournament(num);if (!text.odd(num) JButton jb_s = new JButtonnum + 2num + 1;jb_s11 = new JButton(选手/天数);jb_s11.setBackground(Color.orange);centerPanel.add(jb_s11);for (int i = 1; i = num - 1; i+) jb_s1i = new JButton(第 + i + 天);jb_s1i.setBackground(Colo

18、r.lightGray);centerPanel.add(jb_s1i);for (int i = 2; i = num + 1; i+) for (int j = 1; j = num; j+) jb_sij = new JButton();jb_sij.setBackground(Color.cyan);centerPanel.add(jb_sij);for (int i = 2; i = num + 1; i+) for (int j = 1; j = num; j+) jb_sij.setText(选手 + text.ai - 1j);jl_w.setText(当前参赛队数为： + num);jf.add(centerPanel, BorderLayout.CENTER); else JButt