图4.2 (c) 规模k为3的棋盘显示
20
图4.2 (d) 规模k为4的棋盘显示
图4.2棋盘覆盖问题
21
4.3 最近对问题运行结果及分析
根据屏幕的提示，从键盘上输入平面上点的总数目N，并输入N个坐标点，在屏幕上列出各点的坐标。用分治法思想求解最近点对，对各个点按X轴从小到大排序，计算最近点对及最近点对间的最短距离，并输出显示最近点对，以及最近点对间的最短的距离。
运行结果如图4.3所示。
图4.3最近点对问题
22
5 实验总结
本次实验是基于算法中分治思想的学习，我们以分治法为基准，从多方面对分治法思想进行设计与考虑，通过对分治算法中经典问题的分析与了解，我们知道，分治算法是我们生活中不可或缺的一部分。比如较典型的范例有：排序问题中的分治法——快速排序问题、组合问题中的分治法——棋盘覆盖问题、几何问题中的分治法——最近对问题。这些问题都是分治法思想的主要处理的对像，本实验也是通过这些问题来较全面阐述算法中的分治。
排序问题中的分治法——快速排序问题，排序是算法处理中经常使用的一种重要运算，它的功能是将多个记录的任意序列，重新排列成一个按关键字有序的序列。排序分很多种，有插入排序、选择排序、快速排序、基数排序外部排序，每种排序又可分多种，且各有千秋，所以我们要了解各种方法要视实际情况而定。这次设计的快速排序有很大的缺陷，程序不尽全面，固定只能对10个数排序，用户没有什么选择，排序内容较窄。
组合问题中的分治法——棋盘覆盖问题，这次设计的这个棋盘覆盖规模较小，不能实现大功能的棋盘覆盖。
几何问题中的分治法——最近对问题，这个问题设计的比较清楚，但是只考虑了一维的情形，没有考虑到二维的情况。
总之，这次的课程设计让我学习到很多。首先，完成这次课程设计，我要一定的文献检索能力，要找到比较合适的参考文献， 并拥有适当的处理及筛选信息的能力。其次，巩固了对课程知识的理解，比较全面的运用课程中所学知识分析、解决课程相关实际问题的能力。再次，积累了相关项目开发（专案策划、软设计、调试专案跟踪）经验，提高了论文撰写能力。经过查资料、程序设计、撰写设计报告，是我得到一次较全面的项目实践训练。理论联系实际，提高和培养创新能力，为后续课程的学习、毕业设计、毕业后的工作打下基础。
23
6 参考文献
[1]吴昊等．ACM程序设计培训教程[M]．中国铁道出版社，2007．
[2]Addison Wesley/Pearson．数据结构与算法分析[M]．机械工业出版社，2004． [3]Michael T.Goddrich Roberto Tamassia．算法分析与设计[M]．人民邮电出版社，2006．
24
分治法开放性实验报告-正文
