武汉理工大学算法分析实验报告.docx

学生学号

实验课成绩

学 生 实 验 报 告 书

实验课程名称
算法设计与分析
开 课 学 院
计算机科学与技术学院
指导教师姓名
李晓红
学 生 姓 名

学生专业班级
软件工程zy1302班

2015
--
2016
学年
第
一
学期

实验课程名称： 算法设计与分析
实验项目名称
分治与递归
实验成绩

实 验 者

专业班级
软件zy1302班
组 别

同 组 者

实验日期
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];

while (i <= gt)
{
int cmp = a[i].compareTo(pivot);
if (cmp > 0)
exch(a, i, gt--);
else if (cmp < 0)
exch(a, i++, lt++);
else
i++;
}

sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}
}

三、主要仪器设备及耗材

PC机

第二部分：实验调试与结果分析
一、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等）

1、 调试方法描述：
对程序入口进行断点，随着程序的运行，一步一步的调试，得到运行轨迹；
2、 实验数据：
"R", "B", "W", "W", "R", "W", "B", "R", "R", "W", "B", "R"；
3、 实验现象：

4、 实验过程中发现的问题：
（1） 边界问题：
在设计快速排序的代码时要非常小心，因为其中包含非常关键的边界问题，例如：什么时候跳出while循环，递归什么时候结束，是对指针的左半部分还是右半部分排序等等；
（2） 程序的调试跳转：
在调试过程中要时刻记住程序是对那一部分进行排序，当完成了这部分的排序后，会跳到哪里又去对另外的那一部分进行排序，这些都是要了然于心的，这样才能准确的定位程序。

二、实验结果分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等）

1、 实验结果：

2、 时间复杂度：
介于N和NlogN之间；
3、 空间复杂度：
lgN；
4、 算法总结：
三项切分的快速排序不是稳定的排序，是原地排序，它的运行效率由概率保证，同时取决于输入元素的分布情况，对于包含大量重复元素的数组，它奖排序时间从线性对数级降低到了线性级别，这非常的了不起。

三、小结、建议及体会

本次实验完成了三向切分的快速排序，其中不仅利用了分治法和递归，还对快速排序进行了优化，使得对于存在大量重复元素的数组，能够表现更高的效率。在实验过程中，我遇到了不少的困难，但通过自己在网上大量的浏览文献和资料，独立解决了所有问题，收获了不少。在下次的实验中，我也会继续努力的！

实验课程名称： 算法设计与分析
实验项目名称
动态规划算法
实验成绩

实 验 者

专业班级
软件zy1302班
组 别

同 组 者

实验日期
2015年12月1日
第一部分：实验分析与设计
二． 实验内容描述（问题域描述）

1、 掌握动态规划算法求解问题的一般特征和步骤；
2、 使用动态规划法编程，求解0/1背包问题；
3、 问题描述：给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？

二.实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述）

0/1背包问题的特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即c[i][v]表示前i件物品恰放入一个重量为m的背包可以获得的最大价值。则其状态转移方程便是：
c[i][m]=max{c[i-1][m],c[i-1][m-w[i]]+p[i]}
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。我来解释一下：“将前i件物品放入重量为m的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为c[i-1][m]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的重量为m-w[i]的背包中”，此时能获得的最大价值就是c[i-1][m-w[i]]再加上通过放入第i件物品获得的价值p[i]。
算法设计如下：
F[0][] ← {0}
F[][0] ← {0}
for i←1 to N
do for k←1 to V
F[i][k] ← F[i-1][k]
if(k >= C[i])
then F[i][k] ← max(F[i][k],F[i-1][k-C[i]]+W[i])
return F[N][V]

三、主要仪器设备及耗材

PC机

第二部分：实验调试与结果分析
一、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等）

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];
a[j] = temp;
}

public static void show(Comparable[] a)
{
System.out.println(Arrays.toString(a));
}

public static void main(String[] args)
{
String[] a = {"R", "B", "W", "W", "R", "W", "B", "R", "R", "W", "B", "R"};
System.out.println("排序前：\t");
show(a);
sort(a); // 对数组a进行排序
System.out.println("排序后：\t");
show(a);
}
}

实验二：

package com.shawn;

public class Package01
{
public int[][] pack(int m, int n, int w[], int p[])
{
//c[i][v]表示前i件物品恰放入一个重量为m的背包可以获得的最大价值
int c[][] = new int[n + 1][m + 1];
for (int i = 0; i < n + 1; i++)
c[i][0] = 0;
for (int j = 0; j < m + 1; j++)
c[0][j] = 0;
for (int i = 1; i < n + 1; i++)
{
for (int j = 1; j < m + 1; j++)
{
//当物品为i件重量为j时，如果第i件的重量(w[i-1])小于重量j时，c[i][j]为下列两种情况之一：
//(1)物品i不放入背包中，所以c[i][j]为c[i-1][j]的值
//(2)物品i放入背包中，则背包剩余重量为j-w[i-1],所以c[i][j]为c[i-1][j-w[i-1]]的值加上当前物品i的价值
if (w[i - 1] <= j)
{
if (c[i - 1][j] < (c[i - 1][j - w[i - 1]] + p[i - 1]))
c[i][j] = c[i - 1][j - w[i - 1]] + p[i - 1];
else
c[i][j] = c[i - 1][j];
}
else
c[i][j] = c[i - 1][j];
}
}
return c;
}

// 逆推法求出最优解
public int[] printPack(int c[][], int w[], int m, int n)
{
int x[] = new int[n];
//从最后一个状态记录c[n][m]开始逆推
for (int i = n; i > 0; i--)
{
//如果c[i][m]大于c[i-1][m]，说明c[i][m]这个最优值中包含了w[i-1](注意这里是i-1，因为c数组长度是n+1)
if (c[i][m] > c[i - 1][m])
{
x[i - 1] = 1;
m -= w[i - 1];
}
}
for (int j = 0; j < n; j++)
System.out.println("第" + j + "号背包：" + x[j]);
return x;
}

public static void main(String args[])
{
int m = 10; // 背包容量
int n = 3; // 物品数量
int w[] = {3, 4, 5}; // 物品重量
int p[] = {4, 5, 6}; // 物品价值
Package01 pack = new Package01();
int c[][] = pack.pack(m, n, w, p);
pack.printPack(c, w, m, n);
}
}