武汉理工大学算法分析实验报告
- 格式:docx
- 大小:126.14 KB
- 文档页数:12
学生实验报告书
实验课程名称算法设计与分析开课学院计算机科学与技术学院
指导教师姓名李晓红
学生姓名
学生专业班级软件工程zy1302班2015-- 2016学年第一学期
实验课程名称:算法设计与分析
同组者实验日期2015年10月20日第一部分:实验分析与设计
一.实验内容描述(问题域描述)
1、利用分治法,写一个快速排序的递归算法,并利用任何一种语言,在计算机上实现,同时
进行时间复杂性分析;
2、要求用递归的方法实现。
二.实验基本原理与设计(包括实验方案设计,实验手段的确定,试验步骤等,用硬件逻辑或者算法描述)
本次的解法使用的是“三向切分的快速排序”,它是快速排序的一种优化版本。不仅利用了分治法和递归实现,而且对于存在大量重复元素的数组,它的效率比快速排序基本版高得多。
它从左到右遍历数组一次,维护一个指针lt使得a[lo..lt-1]中的元素都小于v,一个指针gt 使得a[gt+1..hi]中的元素都大于v,一个指针i使得a[lt..i-1]中的元素都等于v,a[i..gt]中的元素都还未确定,如下图所示:
public class Quick3way
{
public static void sort(Comparable[] a, int lo, int hi)
{
if (lo >= hi)
return;
int lt = lo, i = lo + 1, gt = hi;
Comparable pivot = a[lo];
第二部分:实验调试与结果分析
一、调试过程(包括调试方法描述、实验数据记录,实验现象记录,实验过程发现的问题等)
1、调试方法描述:
对程序入口进行断点,随着程序的运行,一步一步的调试,得到运行轨迹;
2、实验数据:
"R", "B", "W", "W", "R", "W", "B", "R", "R", "W", "B", "R";
3、实验现象:
4、实验过程中发现的问题:
(1)边界问题:
在设计快速排序的代码时要非常小心,因为其中包含非常关键的边界问题,例如:
什么时候跳出while循环,递归什么时候结束,是对指针的左半部分还是右半部分
排序等等;
(2)程序的调试跳转:
在调试过程中要时刻记住程序是对那一部分进行排序,当完成了这部分的排序后,
会跳到哪里又去对另外的那一部分进行排序,这些都是要了然于心的,这样才能准
确的定位程序。
二、实验结果分析(包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等)
1、实验结果:
实验课程名称:算法设计与分析
第二部分:实验调试与结果分析
一、调试过程(包括调试方法描述、实验数据记录,实验现象记录,实验过程发现的问题等)
1、调试方法:
直接在方法入口断点调试,一步一步跟踪程序,弄明白程序的运行轨迹;
2、实验数据:
int m = 10;
int n = 3;
int[] w = {3, 4, 5};
int[] p = {4, 5, 6};
3、实验中遇到问题:
(1)刚开始对动态规划算法不熟悉,编码时出现很多的错误,花费了很多的时间;
(2)没有深度理解此处为什么要使用动态规划算法,导致对问题的理解不深刻。
二、实验结果分析(包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等)
1、实验结果:
2、时间复杂度:
nm;
3、空间复杂度:
nm(可优化至m);
4、算法总结:
动态规划的基本思想:
将一个问题分解为子问题递归求解,且将中间结果保存以避免重复计算。通常用来求最优解,且最优解的局部也是最优的。求解过程产生多个决策序列,下一步总是依赖上一步的结果,自底向上的求解。
三、小结、建议及体会
本次实验解决了0/1背包问题,掌握动态规划算法求解问题的一般特征和步骤。在实验过程中,我遇到了很多不懂的问题,但通过老师和同学们的帮助,和自己的努力,最终解决了所有问题,收获颇丰。在今后的算法设计中,我会迎难而上!
源代码:
实验一:
import java.util.Arrays;
public class Quick3way
{
public static void sort(Comparable[] a)
{
sort(a, 0, a.length - 1);
}
public static void sort(Comparable[] a, int lo, int hi) {
if (lo >= hi)
return;
int lt = lo, i = lo + 1, gt = hi;
Comparable pivot = a[lo];
while (true)
{
int cmp = a[i].compareTo(pivot);
if (cmp > 0)
exch(a, i, gt--);
else if (cmp < 0)
exch(a, i++, lt++);
else
i++;
if (i > gt)
break;
}
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}
private static void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];