算法设计与分析试验参考指导书.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算出从游艇出租站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 c[j][k]=c[j-1][k]方法还能想到其它处理方法吗？和动态计划相比会有愈加好效率吗？
能够用回溯法，效率更高。
（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++ 试验环境下实现并进行调试。