分治法循环赛日程表实验报告.docx
《分治法循环赛日程表实验报告.docx》由会员分享，可在线阅读，更多相关《分治法循环赛日程表实验报告.docx（12页珍藏版）》请在冰点文库上搜索。
分治法循环赛日程表实验报告
西北农林科技大学信息工程学院
《算法分析与设计》综合训练实习报告
题目：
分治法循环赛日程表
学号
姓名
专业班级
指导教师
实践日期
2011年5月16日-5月20日
一、综合训练目的与要求
本综合训练是软件工程专业重要的实践性环节之一，是在学生学习完《算法分析》课程后进行的综合练习。
本课综合训练的目的和任务：
（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）框图
（3）伪代码
staticinta[][]=newint[100][100];
staticintathletes;
staticintn;
staticvoidcopy（intn）{//核心代码
intm=n/2;
for（inti=1;i<=m;i++）
for（intj=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];//把左上角数的值赋给对应的右下角数
}
}
staticvoidtournament（intn）//分治算法，递归调用自己
{
if（n==1）{
a[1][1]=1;
return;
}
tournament（n/2）;//分治
copy（n）;//合并
}
publicstaticvoidmain（String[]args）{
n=getText（）;
athletes=n;
tournament（n）;
}
}
四、详细设计及说明
（1）输入一个数字n，根据（x&（x-1））==0判断n是否等于2^k。
不是则提示出错，要求重新输入
（2）按照分治的策略，将所有参赛的选手分为两部分，tournament（intn）使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
2
2
1
表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）算法核心：
staticvoidcopy（intn）{//核心代码，计算右上角数，并根据右上-左下和左上-右下原则赋值
intm=n/2;
for（inti=1;i<=m;i++）
for（intj=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];//把左上角数的值赋给对应的右下角数
}
}
staticvoidtournament（intn）//分治算法，递归调用自己
{
if（n==1）{
a[1][1]=1;
return;
}
tournament（n/2）;//分治
copy（n）;//合并
}
（2）界面（包含窗体，标签，文本域，文本框，按钮）：
publicBoard（）{//构造界面
super（）;//继承父类构造方法
setTitle（"循环赛安排计算器"）;//窗体标题
setBounds（350,200,800,600）;//窗体位置大小
getContentPane（）.setLayout（null）;//不采用布局管理器
setDefaultCloseOperation（JFrame.EXIT_ON_CLOSE）;//设置窗体关闭按钮的动作为退出
finalJLabelinputofk=newJLabel（）;//创建标签对象inputofk
inputofk.setBounds（25,25,80,25）;//标签位置大小
inputofk.setText（"请输入k值：
"）;//标签内容
getContentPane（）.add（inputofk）;//将标签添加到窗体中
finalJLabeloutputofresult=newJLabel（）;//创建标签对象outputofresult
outputofresult.setBounds（250,20,100,25）;//标签位置大小
outputofresult.setText（"比赛安排结果：
"）;//标签内容
getContentPane（）.add（outputofresult）;//将标签添加到窗体中
finalJTextArearesult=newJTextArea（）;//创建文本域对象result
result.setColumns（45）;//文本域显示文字列数
result.setRows（22）;//文本域显示文字行数
result.setFont（newFont（"",Font.BOLD,14））;//字体
result.setLineWrap（false）;//不自动换行
finalJScrollPanescrollPane=newJScrollPane（）;//创建滚动面板对象
scrollPane.setViewportView（result）;//将文本域添加到滚动面板中
Dimensiondime=result.getPreferredSize（）;//获得文本域的首选大小
scrollPane.setBounds（200,50,dime.width,dime.height）;//滚动面板位置大小
getContentPane（）.add（scrollPane）;//将滚动面板添加到窗体中
finalJTextFieldvalueofk=newJTextField（）;//创建文本框对象valueofk
valueofk.setHorizontalAlignment（JTextField.CENTER）;//文本框内容的水平对齐方式
valueofk.setBounds（20,100,80,25）;//文本框显示位置大小
getContentPane（）.add（valueofk）;//将文本框添加到窗体中
finalJButtonyes=newJButton（）;//创建按钮对象
yes.setBounds（30,180,60,25）;//按钮位置大小
yes.setText（"确定"）;//按钮标签内容
}
（3）动作监听和事件处理：
classButtonActionimplementsActionListener{//编写动作监听器类
publicvoidactionPerformed（ActionEvente）{
StringbuttonName=e.getActionCommand（）;
//获得触发事件的按钮的标签文本
if（buttonName.equals（"确定"））{//如果按下确定
intn;//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（intl=1;l<=athletes-1;l++）{//输出天数
if（l<10）{
Stringday=String.format（"%6d",l）;
//若l小于10则比大于10的数多输出一位以便对齐
result.append（day）;
}else{
Stringday=String.format（"%5d",l）;//将l转化为5位长度字符串
result.append（day）;
}
}
result.append（"\n"+""）;
for（inti=1;i<=athletes;i++）//输出数组a[i][j]
{
for（intj=1;j<=athletes;j++）{
if（a[i][j]<10）{
Stringstr=String.format（"%6d",a[i][j]）;
//若a[i][j]小于10则比大于10的数宽度多输出一位以便对齐
result.append（str）;
}else{
Stringstr=String.format（"%5d",a[i][j]）;
//将数组a[i][j]中的数字转化为5位长度字符串
result.append（str）;
}//输出字符串，即将a[i][j]中的数输出
}
result.append（"\n"+""）;
}
}
}
}
yes.addActionListener（newButtonAction（））;//为按钮添加动作监听器
getContentPane（）.add（yes）;//将按钮添加到窗体中
升级会员 