算法设计与分析试验参考指导书.doc

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

东北大学软件学院

目 录
算法设计和分析 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和Y2n个数中位数。
« 编程任务
利用分治策略试设计一个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（数量）

Skirt
5

Cap
7

Bag
12

Title（用户输入根据title排序）

1
Bag
12

2
Cap
7

3
Coat(物品名称)
3（数量）

4
Skirt
5

（3） 根据指定格式书写试验汇报，试验汇报清楚，但不赘述，字体最大为四号。在试验结束一周内上交试验汇报。
5.试验基础步骤
（1） 选定试验题目，仔细阅读试验要求，设计好输入输出，根据分治法思想构思算法，选择适宜存放结构实现应用操作。
（2） 设计结果应在Visual C++ 试验环境下实现并进行调试。
（3） 试验要有具体测试统计，包含多种可能测试数据。
实 验 报 告
课程名称：算法设计和分析
班级：软件1304
试验成绩：
试验名称：分治策略
学号：4726
批阅老师签字：
试验编号：试验一
姓名：赵航
试验日期： 1月 1 日
指导老师：张莉
组号：
试验时间： 时 分－ 时 分

一、试验目标
了解分治法思想。
掌握用分治法处理问题

二、试验内容
（i） 中位数问题
« 问题描述
设X[ 0 : n - 1]和Y[ 0 : n – 1 ]为两个数组，每个数组中含有n个已排好序数。找出X和Y2n个数中位数。
« 编程任务
利用分治策略试设计一个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
试验成绩：
试验名称：动态计划
学号：4726
批阅老师签字：
试验编号：试验二
姓名：赵航
试验日期： 年 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++ 试验环境下实现并进行调试。