西北农林科技大学信息工程学院《算法分析与设计》综合训练实习报告
题目:分治法循环赛日程表
学号
姓名
专业班级
指导教师
实践日期2011年5月16日-5月20日
目录
一、综合训练目的与要求 (1)
二、综合训练任务描述 (1)
三、算法设计 (1)
四、详细设计及说明 (3)
五、调试与测试 (4)
六、实习日志 (6)
七、实习总结 (6)
八、附录:核心代码清单 (6)
一、综合训练目的与要求
本综合训练是软件工程专业重要的实践性环节之一,是在学生学习完《算法分析》课程后进行的综合练习。本课综合训练的目的和任务:
(1)巩固和加深学生对算法分析课程基本知识的理解和掌握;
(2)培养利用算法知识解决实际问题的能力;
(3)掌握利用程序设计语言进行算法程序的开发、调试、测试的能力;
(4)掌握书写算法设计说明文档的能力;
(5)提高综合运用算法、程序设计语言、数据结构知识的能力。
二、综合训练任务描述
假设有n=2k 个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表:(1)每个选手必须与其他n-1个选手各赛一次
(2)每个选手一天只能赛一次
(3)循环赛一共进行n-1天
利用Java语言开发一个界面,输入运动员的个数,输出比赛日程表。对于输入运动员数目不满足n=2k时,弹出信息提示用户。
三、算法设计
(1) 文字描述
假设n位选手顺序编号为1,2,3……n,比赛的日程表是一个n行n-1列的表格。第i行j列表示第i号选手在第j天的比赛对手,根据分治法,要求n个选手的比赛日程,只要知道其中一半的比赛日程,所以使用递归最终可以分到计算两位选手的比赛日程,然后逐级合并,得出结果。
(2) 框图
N Y
Y
输入n
N error
n=2^k?
n=n/2 a[1][1]=1, n=n*2
n=1?
N
Y
N
Y
i<=m?
Int j=1
j<=m?
a[i][j + m] = a[i][j] + m;
a[i + m][j] = a[i][j + m];
a[i + m][j + m] = a[i][j];
j++
i++
OVER Int i=1
m=n/2 图 1
(3) 伪代码
static int a[][] = new int[100][100];
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++) {
a[i][j + m] = a[i][j] + m;// 由左上角数的值算出对应的右上角数
a[i + m][j] = a[i][j + m];// 把右上角数的值赋给对应的左下角数
a[i + m][j + m] = a[i][j];// 把左上角数的值赋给对应的右下角数
}
}
static void tournament(int n) // 分治算法,递归调用自己
{
if (n == 1) {
a[1][1] = 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是否等于2^k。不是则提示出错,要求重新输入
(2)按照分治的策略,将所有参赛的选手分为两部分,tournament(int n) 使n=n/2,递归调用自身,直到n=1.
(3)n=1得出a[1][1] = 1之后,开始逐级合并,n=n*2,m=n/2,由a[i][j + m] = a[i][j] + m得出a[1][2],由a[i + m][j] = a[i][j + m]得出a[2][1],由a[i + m][j + m] = a[i][j]得出a[2][2],如下所示:
表1
1 2
2 1
(4)继续n=n*2,m=n/2,可以仍把它看做均分的四个区域,仍然按照右上,左下,右下的顺序计算。
由a[1][1]得出a[1][3],由a[1][2]得出a[1][4],由a[2][1]得出a[2][3],由a[2][2]得出a[2][4],(即由左上角数的值算出对应的右上角数)
由a[1][3]得出a[3][1],由a[1][4]得出a[3][2],由a[2][3]得出a[4][1],由a[2][4]得出a[4][2],(即把右上角数的值赋给对应的左下角数)
由a[1][1]得出a[3][3],由a[1][2]得出a[3][4],由a[2][1]得出a[4][3],由a[2][2]得出a[4][4],(即把左上角数的值赋给对应的右下角数)
如下图:
表2
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
(5)继续照这样递归,直到算出a[i][j]所有的值
五、调试与测试
测试结果:
图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++) {
a[i][j + m] = a[i][j] + m;// 由左上角数的值算出对应的右上角数
a[i + m][j] = a[i][j + m];// 把右上角数的值赋给对应的左下角数
a[i + m][j + m] = a[i][j];// 把左上角数的值赋给对应的右下角数
}
}
static void tournament(int n) // 分治算法,递归调用自己
{
if (n == 1) {
a[1][1] = 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();// 创建标签对象inputofk
inputofk.setBounds(25, 25, 80, 25);// 标签位置大小
inputofk.setText("请输入k值:");// 标签内容
getContentPane().add(inputofk);// 将标签添加到窗体中
final JLabel outputofresult = new JLabel();// 创建标签对象outputofresult
outputofresult.setBounds(250, 20, 100, 25);// 标签位置大小
outputofresult.setText("比赛安排结果:");// 标签内容
getContentPane().add(outputofresult);// 将标签添加到窗体中
final JTextArea result = new JTextArea();// 创建文本域对象result
result.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();// 创建文本框对象valueofk
valueofk.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());
// 将文本框中的字符串转化为整型赋给n
if (((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++)// 输出数组a[i][j]
{
for (int j = 1; j <= athletes; j++) {
if (a[i][j] < 10) {
String str = String.format("%6d", a[i][j]);
// 若a[i][j]小于10则比大于10的数宽度多输出一位以便对齐
result.append(str);
} else {
String str = String.format("%5d", a[i][j]);
// 将数组a[i][j]中的数字转化为5位长度字符串
result.append(str);
}// 输出字符串,即将a[i][j]中的数输出
}
result.append("\n" + " ");
}
}
}
}
yes.addActionListener(new ButtonAction());// 为按钮添加动作监听器getContentPane().add(yes);// 将按钮添加到窗体中
西北农林科技大学信息工程学院《算法分析与设计》综合训练实习报告 题目:分治法循环赛日程表 学号 姓名 专业班级 指导教师 实践日期2011年5月16日-5月20日
目录 一、综合训练目的与要求 (1) 二、综合训练任务描述 (1) 三、算法设计 (1) 四、详细设计及说明 (3) 五、调试与测试 (4) 六、实习日志 (6) 七、实习总结 (6) 八、附录:核心代码清单 (6)
一、综合训练目的与要求 本综合训练是软件工程专业重要的实践性环节之一,是在学生学习完《算法分析》课程后进行的综合练习。本课综合训练的目的和任务: (1)巩固和加深学生对算法分析课程基本知识的理解和掌握; (2)培养利用算法知识解决实际问题的能力; (3)掌握利用程序设计语言进行算法程序的开发、调试、测试的能力; (4)掌握书写算法设计说明文档的能力; (5)提高综合运用算法、程序设计语言、数据结构知识的能力。 二、综合训练任务描述 假设有n=2k 个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表:(1)每个选手必须与其他n-1个选手各赛一次 (2)每个选手一天只能赛一次 (3)循环赛一共进行n-1天 利用Java语言开发一个界面,输入运动员的个数,输出比赛日程表。对于输入运动员数目不满足n=2k时,弹出信息提示用户。 三、算法设计 (1) 文字描述 假设n位选手顺序编号为1,2,3……n,比赛的日程表是一个n行n-1列的表格。第i行j列表示第i号选手在第j天的比赛对手,根据分治法,要求n个选手的比赛日程,只要知道其中一半的比赛日程,所以使用递归最终可以分到计算两位选手的比赛日程,然后逐级合并,得出结果。 (2) 框图