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

算法设计与分析实 验 指 导 书东北大学软件学院2012年目 录算法设计与分析1实 验 指 导 书1前 言3实验要求4实验1 分治法的应用（2学时）51.实验目的52.实验类型53.预习要求54.实验基本要求55.实验基本步骤7实验2动态规划（2学时）91.实验目的92.实验类型93.预习要求94.实验基本要求95.实验基本步骤10实验3 回溯法（4学时）121.实验目的122.实验类型123.预习要求124.实验基本要求125.实验基本步骤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.txtoutput.txt35 15 183 14 2114 实现提示 比较两个序列的中位数大小，如果两个数相等，则该数为整个2n个数据的中位数，否则通过比较，分别减少两个序列的查找范围，确定查找的起止位置，继续查找。（ii） Gray码问题 问题描述Gray码是一个长度为2n的序列。序列中无相同的元素，每个元素都是长度为n位的串，相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的n构造相应的Gray码。 编程任务 利用分治策略试设计一个算法对任意的n构造相应的Gray码。 数据输入由文件input.txt提供输入数据n。 结果输出 程序运行结束时，将得到的所有编码输出到文件output.txt中。输入文件示例输出文件示例input.txtoutput.txt3000100101010011111101001 实现提示 把原问题分解为两个子问题，分别对两个子问题的每个数组后一位加0和1。（iii）归并排序 问题描述目前的网上拍卖系统会显示很多待拍卖的物品，通常这些系统具有按照某个关键字对打出的广告进行排序列出的功能，并且能够按照用户输入的某个关键字进行过虑，找到某些特定的物品。 编程任务 定义一个Advertisement类，该类中至少包含该物品的数量，名称，联系人e-mail，最好有开拍时间及关闭时间，根据用户输入的关键字比如名称，mail，时间等，利用非递归的归并排序对所有的广告进行排序，并列出所有排好序的广告。 数据输入由文件input.txt提供输入的所有广告信息。程序中由用户输入要排序的关键字。 结果输出 程序运行结束时，排好序的广告输出到文件output.txt中，并为每个广告添加序号。输入文件示例输出文件示例input.txtoutput.txtCoat(物品名称)3（数量）aSkirt5bCap7cBag12aTitle（用户输入按照title排序）1Bag12a2Cap7c3Coat(物品名称)3（数量）a4Skirt5b （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,分别找出这两个数列的中位数xi和y j ,二者进行比较,根据比较结果可以在每个数列中减少一半的搜索范围,然后再分别取两个子数列的中位数再比较,再减少搜索范围,继续下去直到找到最后结果（2） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。O（n）（3） 其它（你认为需要在此说明的）五、问题解决（1） 根据对问题的分析，写出解决办法。设两个长度为n的数列分别为x 0 : n -1和y 0 : n -1,分别找出这两个数列的中位数xi和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）算法的巧妙之处在于分别找出这两个数列的中位数xi和y j ,二者进行比较,根据比较结果可以在每个数列中减少一半的搜索范围,然后再分别取两个子数列的中位数再比较,再减少搜索范围,继续下去直到找到最后结果（3） 针对你所选的问题，你认为应该特别注意哪些方面的处理？比如循环何时结束等。分别找出这两个数列的中位数xi和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种不同面值的硬币，各硬币的面值存于数组T1:n中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值T1,T2,Ti时，可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=。 编程任务 设计一个动态规划算法，对1jL，计算出所有的C( n,j )。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂性 数据输入由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n=13），表示有n种硬币可选。接下来的一行是每种硬币的面值。由用户输入待找钱数j。 结果输出 程序运行结束时，将计算出的所需最少硬币个数输出到文件output.txt中。输入文件示例输出文件示例input.txtoutput.txt31 2 593 实现提示 首先要建立递归关系，并将分析过程写在报告中。(ii) 租用游艇问题（难度系数为4） 问题描述长江游艇俱乐部在长江上设置了n个游艇出租站1，2，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1ijn。试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。 编程任务对于给定的游艇出租站i到游艇出租站j之间的租金为r(i,j),1ijn，编程计算从游艇出租站1到游艇出租站n所需的最少租金。 数据输入由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n=200），表示有n个游艇出租站。接下来的n-1行是r(i,j),1ijn。 结果输出程序运行结束时，将计算出的从游艇出租站1到游艇出租站n所需的最少租金输出到文件output.txt中。输入文件示例输出文件示例input.txtoutput.txt35 15712 实现提示 建立递归关系，然后按照递归关系写出算法。（3） 按照指定的格式书写实验报告，实验报告清晰，但不赘述，字体最大为四号。在实验结束一周内上交实验报告。5.实验基本步骤（4） 选定实验题目，仔细阅读实验要求，设计好输入输出，按照分治法的思想构思算法，选取合适的存储结构实现应用的操作。（5） 设计的结果应在Visual C+ 实验环境下实现并进行调试。（6） 实验要有详细的测试记录，包括各种可能的测试数据。实 验 报 告课程名称：算法设计与分析班级： 软件1304实验成绩：实验名称：动态规划学号：20134726批阅教师签字：实验编号：实验二姓名：赵航实验日期： 2016 年 1 月 5 日指导教师：张莉组号：实验时间： 时 分 时 分一、实验目的熟练掌握动态规划思想及教材中相关经典算法。掌握用动态规划解题的基本步骤，能够用动态规划解决一些问题。二、实验内容与实验步骤找零钱问题（难度系数为3） 问题描述设有n种不同面值的硬币，各硬币的面值存于数组T1:n中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值T1,T2,Ti时，可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=。 编程任务 设计一个动态规划算法，对1jL，计算出所有的C( n,j )。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂性 数据输入由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n=13），表示有n种硬币可选。接下来的一行是每种硬币的面值。由用户输入待找钱数j。 结果输出 程序运行结束时，将计算出的所需最少硬币个数输出到文件output.txt中。输入文件示例输出文件示例input.txtoutput.txt31 2 593 实现提示 首先要建立递归关系，并将分析过程写在报告中。三、实验环境操作系统、调试软件名称、版本号，上机地点，机器台号四、问题分析（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;mn;m+) cm=new intv+1; for(int i=0;i=v;i+) if(i%T0=0) c0i=i/T0; else c0i=INT_MAX; for(int j=1;jn;j+) for(int k=0;k=v;k+) if(kTj) cjk=cj-1k; else cjk=cj-1k0，其价值为vi0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？ 编程任务 利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量i (i = 0 或，i = 0表示物体不放入背包，i 1表示把物体放入背包），使得尽量多的价值装入背包。 数据输入由文件input.txt提供输入数据n，c，及每个物品的重量w 和价值v 。 结果输出 程序运行结束时，将最优解输出到文件output.txt中。输入文件示例输出文件示例input.txtoutput.txt452 1 3 212 10 20 151 1 0 15.实验基本步骤（1） 选定实验题目，仔细阅读实验要求，设计好输入输出，按照回溯的思想构思算法，选取合适的存储结构实现应用的操作。（2） 设计的结果应在Visual C+ 实验环境下实现并进行调试。