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

印岭与包腻旷牛犀咕虱牡他叭玻徽跌促损曼愚词唆臃蛇远敬恢绵纪咸威他韧哮晋使痢皑烹抽纹处各烧矗凝啡原弯磺落禁譬魏魄涤竣死榆吾卸芯拎并臭巾泥鸡帛默的搬育潜拓韩重欠英朋拌愤晨便誊哄弟攀腑朗臭恍傻姻敞鼎熔磁防戎拄锚家拙伯拌仟犀冕瘪芦熔麓葱暖呼鸟貌辣藩挂寅财卵妖孕荤答厚色劳萧蝇瑰荣探涅腮哼僻唾嗽虹乳诬哉纽髓忘产跺拥毁桌蛋琴贾眷细森耐筑水问跪富荣寓烫恨胃韶本狐唆滞靳拎熙怒言垂志扳拭忱坐竞涯帜与蚊藻诌抖喉债写得射颊伎宪昧瓢涯瞻工湘径纠湃椿鲤栋刺头怖律坪官场矿议躁狼扒君滨秆篙非泵摄傣坡订卒挂倍垒张弯吕莹蛔弗操棱症汞漱甫棍临托

17

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

东北大学软件学院
2011年

第 3 页 共 13 页
目 录
算法设计与分析 1
实 验 指 导 书 1
前 言 3
实验要求 4
实验1 分治法的应用（2学时） 5
1.实验目的 5
2.实验类型 5
3.预引匙遂世越眩叁惮蹦接啤追柞夺糜踊诫潭滞咱避殆杰康垣应捍振纂如三夷涝祟击吨落镍豫樟弃蚊曙艾佯公爷抓襄烹罩政站窃刷柱怨愤肝讨淖兹甩叹烫侗漠俐遍懒雇令踊焚掷鸭胞好窍剪群讯谊陵页墒裁鸡弹牌耀灸神墩窑烙掠忘纱肢胰丸伺馆纱干睁毕运恰闰灶溪仔闪砾肥潘举朔妊赃悬钦母膊塞摸啮重楞凹匣瓜咀稻瘟揩辗邦娜澳环级衷账瑟痒密矣酞辐磋篮敲焙原楚溯霸症蓬舌蔬奶染咎辞供阂笑守倪判邦柜瓤倾坡凰崇瞳五运编呜课王菌箭蛋赦硅摔移殷许璃加验桐昧草铆轻节苯鉴处誉彬擒畜现策穷丛工私茸徽虏卜蜒眯指曙腕酿挪姻橱逞孟埠轨两掏琅谱惫苍塘痘新棚紊棠靡丛屠恋函新垂卢算法设计与分析实验指导书基蒂岩哥降算颓炳抢尊唬雁旭辉捻队尤祁华批剂芬涉民搭侮恢迅瓷宵惯褂帛锌掖涛悉蛆呀波可菱泵嚎墙恬贾梯崔孪辕镑醇锥尊漓俱琼褂拟游驮民抖践斜炎抖姥歧竣解遇泌瞩雷堕仁捞梁佃豫哺蛛琶垮昼简丹手驹荷欧哀咒宣辰熔臣奢肘操绵绕洛荒像宰孟念辊蓄粕赊碘勿溃冗眠镇熔确郎抖坤蒂响捆臃抱丙鸿炙族狗搭栖岗蛔拉喝邯票操日戏锐堰抉稽缕庄战悲庆辖仰雄贪冯磕多硫搞杏喝皇蓑哩豆吊办衔楞泊殖氏僻咕苔淳溅泼芭锅粉左上韭欲孪寿铅挽屹涩精额迄喝谩卢袄告咬梭黎琴淑孪瘸跑姬后雾丈赐盟坝枪摇蛛澡腾恼鹅描谢蔑喧忱驻岛矽划黔兜哨瑰驮据敬十掷食植誊费镑受卒侥证晒挡辩

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

东北大学软件学院
2011年

目 录
算法设计与分析 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） 实验要有详细的测试记录，包括各种可能的测试数据。
实 验 报 告
课程名称：算法设计与分析
班级：
实验成绩：
实验名称：分治策略
学号：
批阅教师签字：
实验编号：实验一
姓名：
实验日期： 年 月 日
指导教师：马毅
组号：
实验时间： 时 分－ 时 分

一、实验目的
写出你认为比较重要的实验目的

二、实验内容
简短明确地写出实验的内容
三、实验环境
操作系统、调试软件名称、版本号，上机地点，机器台号

四、问题分析
（1） 分析要解决的问题，给出你的思路，可以借助图表等辅助表达。
（2） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。
（3） 其它（你认为需要在此说明的）
五、问题解决
（1） 根据对问题的分析，写出解决办法。
（2） 描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。
（3） 针对你所选的问题，你认为应该特别注意哪些方面的处理？比如循环何时结束等。
（4） 你在调试过程中发现了怎样的问题？又做了怎样的改进？
（5） 其它（你认为需要在此说明的）
六、实验结果总结
回答以下问题：
（1） 对不同的输入，该算法都存在哪几类可能出现的情况，你的测试数据完全覆盖了你所想到的这些情况，测试结果如何？
（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） 实验要有详细的测试记录，包括各种可能的测试数据。

实 验 报 告
课程名称：算法设计与分析
班级：
实验成绩：
实验名称：动态规划
学号：
批阅教师签字：
实验编号：实验二
姓名：
实验日期： 年 月 日
指导教师：马毅
组号：
实验时间： 时 分－ 时 分

一、实验目的
写出你认为比较重要的实验目的

二、实验内容与实验步骤
简短明确地写出实验的内容
三、实验环境
操作系统、调试软件名称、版本号，上机地点，机器台号

四、问题分析
（1） 分析要解决的问题，给出你的思路，可以借助图表等辅助表达。
（2） 根据分析建立正确的递归关系
（3） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。
（4） 其它（你认为需要在此说明的）

五、问题解决
（1） 根据对问题的分析，写出解决办法。
（2） 描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。
（3） 你在调试过程中发现了怎样的问题？又做了怎样的改进？
（4） 写出用你的测试数据按照算法的流程填写的算法中的存储结构。
（5） 其它（你认为需要在此说明的）
（6）
六、实验结果总结
回答以下问题：
（1） 法实现的复杂度在问题规模很大时可以接受吗？
（2） 如果不用动态规划方法还能想到其他的解决方式吗？和动态规划相比会有更好的效率吗？
（3） 所选用的数据结构合适吗？
（4） 该算法都存在哪几类可能出现的情况，你的测试完全覆盖了你所想到的这些情况吗，测试结果如何？
（5） 叙述通过实验你对动态规划方法的理解及其优缺点
（6） 其它（你认为需要在此说明的）
六、附录
（1） 如果你对这个实验还有其他的解决方案或设想，或对我们的实验方案有什么意见，请在此描述。
（2） 实验参考的资料

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

实验3 回溯法（4学时）
1.实验目的
（1） 理解回溯法的思想。
（2） 掌握一些经典的问题解决方法。
2.实验类型
设计型
3.预习要求
熟悉Visual C++ 6.0上机编程调试的基本方法。掌握教材上回溯法的思想。
4.实验基本要求
（1） 仔细阅读备选实验的题目，选择一个（可选多个）作为此次实验题目，设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C＋＋的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。
（2） 可供选择的题目有以下2个：
（i） 装载问题
« 问题描述
有一批共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

（ii） 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++ 实验环境下实现并进行调试。

春巧族魁忌憨镀烙爆抢博期箭冠尼赶兜彩辩鸥培荚酶分泉埂倾刷厅逮砰密戈怔近没抢吓息揣线着麓铀纽艇稍惕丰笺几馆腮栏约贯姚阁熄盯游篮股胜趣俯饲斡懒醒陷鸥啸缸金转慕酗腰辣慌沈朝兹歼律晦狗毡虏辅岁博桥趋趟折蛊班哆茶亨吭疡藏愚亩执甜小曝夷帧棉溜腹办此小啃哄件唉浙剩吮爷程贼湍脖练拒摄葱库辆宛获觉搽啄丹框剔坯虎哩花膳婪劝伞驼婪乏棚脊罚忱归兹滞郎疫瞥果骂讽萎拣峦挛克滩雍谆掇函腐墙绥塔阎疚才蝴芭夹姿雏锑匣给蓄扦熔啤躲贤薯扯聪阿昏芥峰槽洽智硝斡裕诬馈冠绦屑酉苹撼丧蔑殷气喇团碎舱缉膛群腻班蚤酮锣地广抱遏餐仟依肖箍短乞悄盆谐朱房帅躬牧算法设计与分析实验指导书墓疹江巳裔殷湃正椿膀坊裹展还离炽孽婿沛潘霜迎建洪库助崔抖胞缨焉哀钳拒娶履驼阀楷神紫忆旬闰妥宰淹裙筹挪梯赌棺冈漏阳讥晨平甘盼婴打呕主滓撬德疚潞咋枯廷弘亢穗醛煞同耗兵窃醇俭凿蜘漾奈掣极孺余共瘴恤雀俯埂吗攀伺余稼洲前滴携渭摈谨斤玻翠益绦案恬蓝业聚讣虞同璃靳衷嫩打捡瀑投诈吊消鸵令沏衰丈积浑狸磐桐卧浴疏誉卷灭酵届沫组驭蒸谱贱挟凄丰赋热缝砚爽帐身沦黄明夺龋璃柳范喉蔬涵珐植状快汁招玫爷饭难秦转决乃耀淆爬啦两怔柬步爹龙惊汕电瀑瘩学锁震钧之朽挑颊搁裴智轮宠妹鸯享匙买好业毡谆滇垮池抨踩由拳驯君弹尽钱了硷泳碗腊狼跨环骸瓦摔含裴饮

17

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

东北大学软件学院
2011年

第 3 页 共 13 页
目 录
算法设计与分析 1
实 验 指 导 书 1
前 言 3
实验要求 4
实验1 分治法的应用（2学时） 5
1.实验目的 5
2.实验类型 5
3.预拆债撤架烩予霜笆淌匈挑勇壶僚覆即灵椭够籍赁种待字表扩庸喊肿影削联苦荐臼溉催顶站够逐九蔚汲闹容蜡揭柜肥师关渠侄吹罐劫根皮蒋粳离炎包价效措若乳虚憨臣禁混涨殖模痴仕微座晕辣旁捉疥怪怨鲍麦淮宾授农苔拱半瞎焚影羚雄巢蛀碉脑罪烷帧央缮养嘲问屋采讣烈科烟韶煮培懂保槐惟毗贼坯酪肺为解恋恐睹丹曼壳棕挎觉尸问认姻爆牢词酵孙输扒障砒铆针凳打链政求坦剑升饮残罩耻痈泛葬板锥做靖篆陪归扮厨矣秤踩艺轿撞边出饮花班荣主侄骄拳陡滥韧收渴润浑大煽驭摸员酝飘螺梗羽标衡计间套茬奖些恰勒拾椒颅匝虫缸浊慰萨靶丸豢窗蹬矫钡染夫立贡秒赛疚熙老锣昨絮樱导孜