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

《2016新编《算法设计与分析》实验指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法设计与分析》实验指导书本文档主要用于《算法设计与分析》课程的实验指导。《算法设计与分析》旨在教会学生处理各种问题的方法，通过实验，使学生能够把所学的方法用于具体的问题，并对所用算法进行比较分析，从而提高学生分析问题、解决问题的能力。通过该课程的实验，使学生对课堂中所讲述的内容有一个直观的认识，更好地掌握所学的知识，培养学生的实际动手能力，加强学生创新思维能力的培养。本课程设计了7个设计型实验。实验内容包括用分治法、动态规划、贪心法、回溯法以及分支限界法求解问题。一、实验内容安排序号实验项目内

2、容提要实验学时实验类型每组人数实验要求1快速排序问题有n个无序的数值数据，现要求将其排列成一个有序的序列。要求用快速排序方法。2设计1必做2最少硬币问题有n种不同面值的硬币，各硬币面值存于数组T[1:n]；现用这些面值的钱来找钱；各面值的个数存在数组Num[1:n]中。对于给定的1≤n≤10，硬币面值数组、各面值的个数及钱数m，0<=m<=2001，设计一个算法，计算找钱m的最少硬币数。要求用动态规划法。2设计1必做3租用游艇问题长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这

3、些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1≤i＜j≤n。设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。要求用动态规划法。4设计1必做4汽车加油问题一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。要求用贪心法。2设计1必做65最小重量机器设计问题设某一机器由n个部件组成，每一种部件可以从m个不同的供应商处购得。设是从供应商j处购得的部件i的重

4、量，是相应的价格。设计一个算法，给出总价格不超过的最小重量机器设计。要求用回溯法。3设计1必做6世界名画陈列问题针对世界名画陈列馆问题，设计一个算法，计算警卫机器人的最佳哨位安排，使得名画陈列馆的每个陈列室都在警卫机器人监视之下，且所用的警卫机器人数目最少。要求用回溯法。3设计1必做7最佳调度问题假设有n个任务由k个可并行工作的机器来完成。完成任务i需要时间为，设计完成这n个任务的最佳调度算法，使得完成全部任务的时间最早。要求用分支限界法。2设计1必做二、实验基本要求实验前要求学生一定要先了解实验

5、目的、内容、要求以及注意事项，要求学生熟悉实验对象，设计并编写相应的算法。学生应独立完成所布置实验内容，编写代码，运行程序，记录结果并撰写实验报告。三、实验报告要求实验结束后，应及时整理出实验报告，实验报告提交书面文档。四、考核方式理论考试（60％）＋实验（30％）+作业（10%）五、实验内容与指导实验一快速排序问题1．实验目的(1)用分治法求解该问题。2．实验环境6PC机，要求安装Eclipse软件或VC++软件供学生实验。3．实验内容有n个无序的数值数据，现要求将其排列成一个有序的序列。4.实

6、验步骤(1)输入实现该问题的源代码；(2)输入测试数据，验证代码的正确性。5.实验要求(1)做好实验预习，熟悉本实验中所使用的开发环境。(2)写出实验报告①实验目的②实验内容③出错信息及处理方法④实验结果实验二最少硬币问题1．实验目的(1)用动态规划求解该问题。2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。3．实验内容有n种不同面值的硬币，各硬币面值存于数组T[1:n]；现用这些面值的钱来找钱；各面值的个数存在数组Num[1:n]中。对于给定的1≤n≤10，硬币面值数组、

7、各面值的个数及钱数m，0<=m<=2001，设计一个算法，计算找钱m的最少硬币数。4.实验步骤(1)输入实现该问题的源代码；(2)输入测试数据，验证代码的正确性。5.实验要求(1)做好实验预习，熟悉本实验中所使用的开发环境。(2)写出实验报告①实验目的②实验内容③出错信息及处理方法④实验结果实验三租用游艇问题1．实验目的6(1)用动态规划求解该问题。2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。3．实验内容长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在

8、这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1≤i＜j≤n。设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。要求用动态规划法。4.实验步骤(1)输入实现该问题的源代码；(2)输入测试数据，验证代码的正确性。5.实验要求(1)做好实验预习，熟悉本实验中所使用的开发环境。(2)写出实验报告①实验目的②实验内容③出错信息及处理方法④实验结果实验四汽车加油问题1．实验目的(1)用贪心法求解该问题。2．实验