算法设计与分析实验指导书详解.doc

算法设计与分析
实 验 指 导 书

东北大学软件学院
2012年

目 录
算法设计与分析 1
实 验 指 导 书 1
前 言 3
实验要求 4
实验1 分治法的应用（2学时） 5
1.实验目的 5
2.实验类型 5
3.预习要求 5
4.实验基本要求 5
5.实验基本步骤 7
实验2动态规划（2学时） 9
1.实验目的 9
2.实验类型 9
3.预习要求 9
4.实验基本要求 9
5.实验基本步骤 10
实验3 回溯法（4学时） 12
1.实验目的 12
2.实验类型 12
3.预习要求 12
4.实验基本要求 12
5.实验基本步骤 13

前 言
《算法设计与分析》是一门面向设计，处于计算机科学与技术学科核心地位的教育课程。通过对计算机算法系统的学习，使学生理解和掌握计算机算法的通用设计方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法进行复杂性分析奠定基础。
要求掌握算法复杂度分析、分治法、动态规划法、贪心法、回溯法、分支限界法等算法的设计方法及其分析方法。能将这些方法灵活的应用到相应的问题中，并且能够用C++实现所涉及的算法，并尽量做到低复杂度，高效率。
通过本课程的实验，使学生加深对课程内容的理解，培养学生严密的思维能力，运用所学知识结合具体问题设计适用的算法的能力；培养学生良好的设计风格，激励学生创造新算法和改进旧算法的愿望和热情。希望同学们能够充分利用实验条件，认真完成实验，从实验中得到应有的锻炼和培养。
希望同学们在使用本实验指导书及进行实验的过程中，能够帮助我们不断地发现问题，并提出建议，使《算法设计与分析》课程成为对大家有益的课程。

实验要求
《算法设计与分析》课程实验的目的是为了使学生在课堂学习的同时，通过一系列的实验，使学生加深理解和更好地掌握《算法设计与分析》课程教学大纲要求的内容。
在《算法设计与分析》的课程实验过程中，要求学生做到：
（1）仔细观察调试程序过程中出现的各种问题，记录主要问题，做出必要说明和分析。
（2）认真书写实验报告。实验报告模板见附录1。
（3）遵守机房纪律，服从辅导教师指挥，爱护实验设备。
（4）实验课程不迟到。如有事不能出席，所缺实验一般不补。
（5）本实验采用的开发环境为 Microsoft Visual C++ 6.0，同学在做实验之前要求熟悉该软件的使用方法。
（6）实验成绩主要从以下几方面考核：实验过程态度，实验结果及报告书写。

实验1 分治法的应用（2学时）
1.实验目的
（1） 理解分治法的思想。
（2） 掌握用分治法解决问题
2.实验类型
设计型
3.预习要求
熟悉Visual C++ 6.0上机编程调试的基本方法。掌握教材上分治法的思想，掌握各种排序方法及二分搜索的思想。
4.实验基本要求
（1） 仔细阅读备选实验的题目，选择一个（可选多个）作为此次实验题目，设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C＋＋的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。
（2） 可供选择的题目有以下3个：
（i） 中位数问题
« 问题描述
设X[ 0 : n - 1]和Y[ 0 : n – 1 ]为两个数组，每个数组中含有n个已排好序的数。找出X和Y的2n个数的中位数。
« 编程任务
利用分治策略试设计一个O (log n)时间的算法求出这2n个数的中位数。
« 数据输入
由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n<=200），表示每个数组有n个数。接下来的两行分别是X，Y数组的元素。
« 结果输出
程序运行结束时，将计算出的中位数输出到文件output.txt中。
输入文件示例
输出文件示例
input.txt
output.txt
3
5 15 18
3 14 21
14

« 实现提示
比较两个序列的中位数大小，如果两个数相等，则该数为整个2n个数据的中位数，否则通过比较，分别减少两个序列的查找范围，确定查找的起止位置，继续查找。

（ii） Gray码问题
« 问题描述
Gray码是一个长度为2n的序列。序列中无相同的元素，每个元素都是长度为n位的串，相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的n构造相应的Gray码。
« 编程任务
利用分治策略试设计一个算法对任意的n构造相应的Gray码。
« 数据输入
由文件input.txt提供输入数据n。
« 结果输出
程序运行结束时，将得到的所有编码输出到文件output.txt中。
输入文件示例
输出文件示例
input.txt
output.txt
3

000
100
101
010
011
111
101
001

« 实现提示
把原问题分解为两个子问题，分别对两个子问题的每个数组后一位加0和1。
（iii）归并排序
« 问题描述
目前的网上拍卖系统会显示很多待拍卖的物品，通常这些系统具有按照某个关键字对打出的广告进行排序列出的功能，并且能够按照用户输入的某个关键字进行过虑，找到某些特定的物品。
« 编程任务
定义一个Advertisement类，该类中至少包含该物品的数量，名称，联系人e-mail，最好有开拍时间及关闭时间，根据用户输入的关键字比如名称，mail，时间等，利用非递归的归并排序对所有的广告进行排序，并列出所有排好序的广告。
« 数据输入
由文件input.txt提供输入的所有广告信息。程序中由用户输入要排序的关键字。
« 结果输出
程序运行结束时，排好序的广告输出到文件output.txt中，并为每个广告添加序号。
输入文件示例
输出文件示例
input.txt
output.txt
Coat(物品名称)
3（数量）
a@
Skirt
5
b@
Cap
7
c@
Bag
12
a@
Title（用户输入按照title排序）

1
Bag
12
a@
2
Cap
7
c@
3
Coat(物品名称)
3（数量）
a@
4
Skirt
5
b@

（3） 按照指定的格式书写实验报告，实验报告清晰，但不赘述，字体最大为四号。在实验结束一周内上交实验报告。
5.实验基本步骤
（1） 选定实验题目，仔细阅读实验要求，设计好输入输出，按照分治法的思想构思算法，选取合适的存储结构实现应用的操作。
（2） 设计的结果应在Visual C++ 实验环境下实现并进行调试。
（3） 实验要有详细的测试记录，包括各种可能的测试数据。
实 验 报 告
课程名称：算法设计与分析
班级：软件1304
实验成绩：
实验名称：分治策略
学号：20134726
批阅教师签字：
实验编号：实验一
姓名：赵航
实验日期： 2016年 1月 1 日
指导教师：张莉
组号：
实验时间： 时 分－ 时 分

一、实验目的
理解分治法的思想。
掌握用分治法解决问题

二、实验内容
（i） 中位数问题
« 问题描述
设X[ 0 : n - 1]和Y[ 0 : n – 1 ]为两个数组，每个数组中含有n个已排好序的数。找出X和Y的2n个数的中位数。
« 编程任务
利用分治策略试设计一个O (log n)时间的算法求出这2n个数的中位数。
« 数据输入
由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n<=200），表示每个数组有n个数。接下来的两行分别是X，Y数组的元素。
三、实验环境
WINDOWS7家庭版
DEVC++

四、问题分析
（1） 分析要解决的问题，给出你的思路，可以借助图表等辅助表达。
设两个长度为n的数列分别为x[ 0 : n -1]和y[ 0 : n -1],分别找出这两个数列的中位数x[i]和y[ j ],二者进行比较,根据比较结果可以在每个数列中减少一半的搜索范围,然后再分别取两个子数列的中位数再比较,再减少搜索范围,继续下去直到找到最后结果

（2） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。
O（n）

（3） 其它（你认为需要在此说明的）
五、问题解决
（1） 根据对问题的分析，写出解决办法。
设两个长度为n的数列分别为x[ 0 : n -1]和y[ 0 : n -1],分别找出这两个数列的中位数x[i]和y[ j ],二者进行比较,根据比较结果可以在每个数列中减少一半的搜索范围,然后再分别取两个子数列的中位数再比较,再减少搜索范围,继续下去直到找到最后结果

（2） 描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。
int findMedian(int* x, int* y, int n)
{
if(n==1)
return *x <= *y? *x:*y;

int m=(n-1)/2;
int p=m+1;

if(n%2!=0)
p--;

if(*(x+m)==*(y+m))
return *(x+m);
else if(*(x+m)<*(y+m))
return findMedian(x+p,y,m+1);
else
return findMedian(x,y+p,m+1);
}
O（n）
算法的巧妙之处在于分别找出这两个数列的中位数x[i]和y[ j ],二者进行比较,根据比较结果可以在每个数列中减少一半的搜索范围,然后再分别取两个子数列的中位数再比较,再减少搜索范围,继续下去直到找到最后结果

（3） 针对你所选的问题，你认为应该特别注意哪些方面的处理？比如循环何时结束等。
分别找出这两个数列的中位数x[i]和y[ j ],二者进行比较，直到最后的结果。
（4） 你在调试过程中发现了怎样的问题？又做了怎样的改进？
在调试中发现了编译不通过，经检查是语法问题。

（5） 其它（你认为需要在此说明的）
六、实验结果总结
回答以下问题：
（1） 对不同的输入，该算法都存在哪几类可能出现的情况，你的测试数据完全覆盖了你所想到的这些情况，测试结果如何？
1、普通 2、数组中只有一个数 结果如下

（2） 算法实现的复杂度在问题规模很大时可以接受吗？
可以
（3） 如果不用分治方法还能想到其他的解决方式吗？和分治相比会有更好的效率吗？
有：将二者放到同一数组然后排序取中值，效率更低。
（4） 所选用的数据结构合适吗？
选用数组，合适。
（5） 叙述通过实验你对分治方法的理解及你认为的分治法的优缺点。
分治法的优点是将大问题拆成小问题来进行解决，可以节约时间。
（6） 其它（你认为需要在此说明的）
六、附录
（1） 如果你对这个实验还有其他的解决方案或设想，或对我们的实验方案有什么意见，请在此描述。
（2） 实验参考的资料和网址

注：本实验的考核点主要在问题的分析是否正确，对问题的考虑是否全面，解决方法及程序是否正确，程序代码是否清晰，是否符合编码规范，是否有注释，测试数据是否完整，是否有创新。

实验2动态规划（2学时）
1.实验目的
（1） 熟练掌握动态规划思想及教材中相关经典算法。
（2） 掌握用动态规划解题的基本步骤，能够用动态规划解决一些问题。

2.实验类型
设计型
3.预习要求
掌握动态规划思想，复习学过的有关动态规划的算法，并设计实验题目的程序。
4.实验基本要求
（1） 仔细阅读备选实验的题目，选择一个（可选多个）作为此次实验题目，设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C＋＋的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。
（2） 可供选择的题目有以下2个：
(i）找零钱问题（难度系数为3）
« 问题描述
设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值T[1],T[2],…,T[i]时，可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=∞。
« 编程任务
设计一个动态规划算法，对1≤j≤L，计算出所有的C( n,j )。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂性
« 数据输入
由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n<=13），表示有n种硬币可选。接下来的一行是每种硬币的面值。由用户输入待找钱数j。
« 结果输出
程序运行结束时，将计算出的所需最少硬币个数输出到文件output.txt中。
输入文件示例
输出文件示例
input.txt
output.txt
3
1 2 5
9
3

« 实现提示
首先要建立递归关系，并将分析过程写在报告中。

(ii) 租用游艇问题（难度系数为4）
« 问题描述
长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1£i<j£n。试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。
« 编程任务
对于给定的游艇出租站i到游艇出租站j之间的租金为r(i,j),1£i<j£n，编程计算从游艇出租站1到游艇出租站n所需的最少租金。

« 数据输入
由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n<=200），表示有n个游艇出租站。接下来的n-1行是r(i,j),1£i<j£n。
« 结果输出
程序运行结束时，将计算出的从游艇出租站1到游艇出租站n所需的最少租金输出到文件output.txt中。

输入文件示例
输出文件示例
input.txt
output.txt
3
5 15
7
12

« 实现提示
建立递归关系，然后按照递归关系写出算法。
（3） 按照指定的格式书写实验报告，实验报告清晰，但不赘述，字体最大为四号。在实验结束一周内上交实验报告。

5.实验基本步骤
（4） 选定实验题目，仔细阅读实验要求，设计好输入输出，按照分治法的思想构思算法，选取合适的存储结构实现应用的操作。
（5） 设计的结果应在Visual C++ 实验环境下实现并进行调试。
（6） 实验要有详细的测试记录，包括各种可能的测试数据。

实 验 报 告
课程名称：算法设计与分析
班级： 软件1304
实验成绩：
实验名称：动态规划
学号：20134726
批阅教师签字：
实验编号：实验二
姓名：赵航
实验日期： 2016 年 1 月 5 日
指导教师：张莉
组号：
实验时间： 时 分－ 时 分

一、实验目的
熟练掌握动态规划思想及教材中相关经典算法。
掌握用动态规划解题的基本步骤，能够用动态规划解决一些问题。

二、实验内容与实验步骤
找零钱问题（难度系数为3）
« 问题描述
设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值T[1],T[2],…,T[i]时，可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=∞。
« 编程任务
设计一个动态规划算法，对1≤j≤L，计算出所有的C( n,j )。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂性
« 数据输入
由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n<=13），表示有n种硬币可选。接下来的一行是每种硬币的面值。由用户输入待找钱数j。
« 结果输出
程序运行结束时，将计算出的所需最少硬币个数输出到文件output.txt中。
输入文件示例
输出文件示例
input.txt
output.txt
3
1 2 5
9
3

« 实现提示
首先要建立递归关系，并将分析过程写在报告中。
三、实验环境
操作系统、调试软件名称、版本号，上机地点，机器台号

四、问题分析
（1） 分析要解决的问题，给出你的思路，可以借助图表等辅助表达。
问题为找零钱，则应该采用递归的算法解决问题，一个一个硬币往上加

（2） 根据分析建立正确的递归关系
c(i, j)表示从第1个到第i个硬币可选，要找的钱数是j，则出口是

（3） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。
O(n的平方)
（4） 其它（你认为需要在此说明的）

五、问题解决
（1） 根据对问题的分析，写出解决办法。
采用递归的算法解决问题，一个一个硬币往上加

（2） 描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。
int changeCoins(int *T, int n, int v)
{
sort(T,T+n);
int **c=new int*[n];
for(int m=0;m<n;m++){
c[m]=new int[v+1];
}
for(int i=0;i<=v;i++)
if(i%T[0]==0)
c[0][i]=i/T[0];
else
c[0][i]=INT_MAX;
for(int j=1;j<n;j++)
for(int k=0;k<=v;k++)
if(k<T[j])
c[j][k]=c[j-1][k];
else
c[j][k]=c[j-1][k]<c[j][k-T[j]]+1?c[j-1][k]:c[j][k-T[j]]+1;
return c[n-1][v];

delete[] c;
}
O(n的平方)

（3） 你在调试过程中发现了怎样的问题？又做了怎样的改进？
发现编译报错，经查是语法问题
（4） 写出用你的测试数据按照算法的流程填写的算法中的存储结构。

（5） 其它（你认为需要在此说明的）

六、实验结果总结
回答以下问题：
（1） 法实现的复杂度在问题规模很大时可以接受吗？
可以接受。
（2） 如果不用动态规划方法还能想到其他的解决方式吗？和动态规划相比会有更好的效率吗？
可以用回溯法，效率更高。
（3） 所选用的数据结构合适吗？
合适
（4） 该算法都存在哪几类可能出现的情况，你的测试完全覆盖了你所想到的这些情况吗，测试结果如何？
1、硬币数为1 2、普通 3、找不出来 结果如下

（5） 叙述通过实验你对动态规划方法的理解及其优缺点
优点是在分治法的基础上减少了重复计算。
（6） 其它（你认为需要在此说明的）
六、附录
（1） 如果你对这个实验还有其他的解决方案或设想，或对我们的实验方案有什么意见，请在此描述。
（2） 实验参考的资料

注：本实验的考核点主要在问题的分析是否正确，递归关系建立是否正确，对问题的考虑是否全面，解决方法及程序是否正确，程序代码是否清晰，是否符合编码规范，是否有注释，测试数据是否完整，是否有创新。

实验3 回溯法（4学时）
1.实验目的
（1） 理解回溯法的思想。
（2） 掌握一些经典的问题解决方法。
2.实验类型
设计型
3.预习要求
熟悉Visual C++ 6.0上机编程调试的基本方法。掌握教材上回溯法的思想。
4.实验基本要求
（1） 仔细阅读备选实验的题目，选择一个（可选多个）作为此次实验题目，设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C＋＋的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。
（2） 可供选择的题目有以下2个：
（ii） 装载问题
« 问题描述
有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi ，且 ，要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，请给出该方案。
« 编程任务
利用回溯法试设计一个算法求出该装载问题的解。
« 数据输入
由文件input.txt提供输入数据。文件的第1行中有2个正整数n及c，表示有n个集装箱，第一艘船的载重量为c。接下来的一行为每个集装箱的重量。
« 结果输出
程序运行结束时，将计算出的最优解输出到文件output.txt中，如果某集装箱被装入船上，则对应的解为1，如果不能装入则为0。
输入文件示例
输出文件示例
input.txt
output.txt
3 30
16 15 15
0 1 1

（iii） 0-1背包问题
« 问题描述
给定n种物品和一背包。物品i的重量是wi>0，其价值为vi>0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？
« 编程任务
利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量ｘi
(ｘi = 0 或１，ｘi = 0表示物体ｉ不放入背包，ｘi ＝1表示把物体ｉ放入背包），
使得尽量多的价值装入背包。
« 数据输入
由文件input.txt提供输入数据n，c，及每个物品的重量w[ ]和价值v[ ]。
« 结果输出
程序运行结束时，将最优解输出到文件output.txt中。
输入文件示例
输出文件示例
input.txt
output.txt
4
5
2 1 3 2
12 10 20 15
1 1 0 1
5.实验基本步骤
（1） 选定实验题目，仔细阅读实验要求，设计好输入输出，按照回溯的思想构思算法，选取合适的存储结构实现应用的操作。
（2） 设计的结果应在Visual C++ 实验环境下实现并进行调试。