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

《算法分析与设计》实验指导书一、 实验目的《算法设计与分析》是一门面向设计，处于计算机科学与技术学科核心地位的教育课程。通过对计算机算法系统的学习，使学生理解和掌握计算机算法的通用设计方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法进行复杂性分析奠定基础。要求掌握算法复杂度分析、分治法、动态规划法、贪心法、回溯法、分支限界法等算法的设计方法及其分析方法。能将这些方法灵活的应用到相应的问题中，并且能够用C++实现所涉及的算法，并尽量做到低复杂度，高效率。通过本课程的实验，使学生加深对课程内容的理解，培养学生严密的思维能力，运用所学知识结合具体问题设计适用的算法的能力；培养学生良好的设计风格，激励学生创造新算法和改进旧算法的愿望和热情。希望同学们能够充分利用实验条件，认真完成实验，从实验中得到应有的锻炼和培养。希望同学们在使用本实验指导书及进行实验的过程中，能够帮助我们不断地发现问题，并提出建议，使《算法设计与分析》课程成为对大家有益的课程。二、 实验要求《算法设计与分析》课程实验的目的是为了使学生在课堂学习的同时，通过一系列的实验，使学生加深理解和更好地掌握《算法设计与分析实验》课程教学大纲要求的内容。在《算法设计与分析实验》课程实验过程中，要求学生做到：（1）仔细观察调试程序过程中出现的各种问题，记录主要问题，做出必要说明和分析。（2） 认真书写实验报告。（3） 遵守机房纪律，服从辅导教师指挥，爱护实验设备。（4） 实验课程不迟到。如有事不能出席，所缺实验一般不补。本实验采用的开发环境为MicrosoftVisualC++6.0,同学在做实验之前要求熟悉该软件的使用方法。实验成绩主要从以下几方面考核：实验过程态度，实验结果及实验报告书与。上机准备和上机调试上机准备包括以下几个方面：注意同一高级语言文本之间的差别。熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。应该能够熟练运用高级语言的程序调试器DBBUG调试程序。上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试低层函数。在调试过程中可以不断借助DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时应动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。总结和整理实验报告实验结束后，要整理实验结果并认真分析和总结，根据教师要求写出实验报告。实验报告一般包括如下内容：实验内容实验目的程序清单调试步骤运行结果：原始数据，相应的运行结果和必要的说明。分析与思考调试过程及调试中遇到的问题及解决办法;调试程序的心得与体会;其他算法的存在与实践等。若最终未完成调试，要认真找出错误并分析原因等。实验一、利用分治算法，编程实现循环赛日程表安排问题【实验学时】4学时【实验目的】深刻理解并掌握“分治算法”的设计思想；提高应用“分治算法”设计技能；理解这样一个观点：用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。【问题描述】设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：（1） 每个选手必须与其他n-1个选手各赛一次；（2） 每个选手一天只能赛一次；（3） 循环赛一共进行n-1天.按照分治的策略，可将所有参赛的选手分为两部分，n=2k个选手的比赛日程表就可以通过为n/2=2k-i个选手设计的比赛日程表来决定。递归地执行这种分割，直到只剩下2个选手时。【基本要求】实现《网球循环赛》问题的分治算法，并进行算法时间复杂性分析。对实现的分治算法进行改进；对上述改进后算法进行时间复杂性分析，通过实验结果分析对比，得出自己的结论和总结。设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C++的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。【基本步骤】（1）仔细阅读实验要求，设计好输入输出，按照分治法的思想构思算法，选取合适的存储结构实现应用的操作。（2） 设计的结果应在VisualC++实验环境下实现并进行调试。（3） 实验要有详细的测试记录，包括各种可能的测试数据。实验二利用动态规划算法编程求解0-1背包问题【实验学时】4学时【实验目的】（1） 熟练掌握动态规划思想及教材中相关经典算法。（2） 掌握动态规划算法求解问题的一般特征和步骤；使用动态规划法编程，求解0/1背包问题。【问题描述】0/1背包问题是给定n个重量为｛w,w,•••/｝、价值为｛v,v,•••,▼｝1 2 n 1 2 n的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设Xj表示物品i装入背包的情况，则当xj0时，表示物品i没有被装入背包，x：1时，表示物品i被装入背包。0/1背包问题可以看作是决策一个序列（x「X,…，X），对任一变量X的决策是决定X=1还是X=0。在对X决策后，已确2 n i i i i-1定了（X「…，Xi-1），在决策Xi时，问题处于下列两种状态之一：（1）背包容量不足以装入物品i，则Xj=0，背包不增加价值；（2）背包容量可以装入物品i，则x：1，背包的价值增加了七。这两种情况下背包价值的最大者应该是对Xi决策后的背包价值。举例:若商店一共有5类商品，重量分别为：3,4,7,8,9价值分别为：4,5,10，11，13则所选商品的最大价值为24，所选商品的一个序列为：00011【基本要求】实现《0-1背包问题》问题的动态规划法编程，动态规划原理：动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。并进行算法时间复杂性分析。对算法进行时间复杂性分析，通过实验结果分析对比，得出自己的结论和总结。设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C++的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。【基本步骤】（1） 仔细阅读实验要求，设计好输入输出，按照动态规划法的思想构思算法，选取合适的存储结构实现应用的操作。（2） 设计的结果应在VisualC++实验环境下实现并进行调试。（3） 实验要有详细的测试记录，包括各种可能的测试数据。实验三利用贪心算法编程求解背包问题和TSP问题【实验学时】6学时【实验目的】掌握动态规划算法求解问题的一般特征和步骤；使用动态规划法编程，求解背包问题和TSP问题。【问题描述】背包问题是给定n个重量为｛w,w,•••/｝、价值为｛v,v,•••,▼｝的物1 2 n 1 2 n品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装满背包。背包问题的三种贪心策略，（1）选择价值最大的物品；（2）选择重量最轻的物品；（3）选择单位重量价值最大的物品。应用第三种贪心策略，每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后我们就面临了一个最优子问题一一它同样是背包问题，只不过背包容量减少了，物品集合减少了。因此背包问题具有最优子结构性质。TSP问题是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。1）最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。2）最短链接策略：每次在整个图的范围内选择最短边加入到解集合中，但是，要保证加入解集合中的边最终形成一个哈密顿回路。【基本要求】1.实现背包问题的贪心算法编程，利用背包问题的三种贪心策略，（1）选择价值最大的物品；（2）选择重量最轻的物品；（3）选择单位重量价值最大的物品。重点应用第三种贪心策略。对算法进行时间复杂性分析，通过实验结果分析对比，得出自己的结论和总结。设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C++的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。【基本步骤】（1） 仔细阅读实验要求，设计好输入输出，按照动态规划法的思想构思算法，选取合适的存储结构实现应用的操作。（2） 设计的结果应在VisualC++实验环境下实现并进行调试。（3） 实验要有详细的测试记录，包括各种可能的测试数据。实验四利用回溯法编程求解0-1背包问题和TSP问题【实验学时】6学时【实验目的】掌握回溯法的设计思想；掌握解空间树的构造方法，以及在求解过程中如何存储求解路径；考察回溯法求解问题的有效程度。【问题描述】0-1背包问题：给定n种物品和一背包。物品i的重量是wi>0，其价值为vi>0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？TSP问题：指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。

【基本要求】利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量xi(xi=0或l,xi=0表示物体i不放入背包，xi=1表示把物体i放入背包)，使得尽量多的价值装入背包。★数据输入由文件input.txt提供输入数据n,c,及每个物品的重量w[]和价值v[]。★结果输出程序运行结束时，将最优解输出到文件output.txt中输入文件示例input.txt输入文件示例input.txt45213212102015输出文件示例output.txt1101【基本步骤】仔细阅读实验要求，设计好输入输出，按照动态规划法的思想构思算法，选取合适的存储