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

PAGEPAGE5《算法设计与分析》实验指导书本文档主要用于《算法设计与分析》课程的实验指导。《算法设计与分析》旨在教会学生处理各种问题的方法，通过实验，使学生能够把所学的方法用于具体的问题，并对所用算法进行比较分析，从而提高学生分析问题、解决问题的能力。通过该课程的实验，使学生对课堂中所讲述的内容有一个直观的认识，更好地掌握所学的知识，培养学生的实际动手能力，加强学生创新思维能力的培养。本课程设计了7个设计型实验。实验内容包括用分治法、动态规划、贪心法、回溯法以及分支限界法求解问题。一、实验内容安排序号实验项目内容提要实验学时实验类型每组人数实验要求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。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1≤i＜j≤n。设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。要求用动态规划法。4设计1必做4汽车加

油问题一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。要求用贪心法。2设计1必做5最小重量机器设计问题设某一机器由n个部件组成，每一种部件可以从m个不同的供应商处购得。设是从供应商j处购得的部件i的重量，是相应的价格。设计一个算法，给出总价格不超过的最小重量机器设计。要求用回溯法。3设计1必做6世界名画

陈列问题针对世界名画陈列馆问题，设计一个算法，计算警卫机器人的最佳哨位安排，使得名画陈列馆的每个陈列室都在警卫机器人监视之下，且所用的警卫机器人数目最少。要求用回溯法。3设计1必做7最佳调

度问题假设有n个任务由k个可并行工作的机器来完成。完成任务i需要时间为，设计完成这n个任务的最佳调度算法，使得完成全部任务的时间最早。要求用分支限界法。2设计1必做二、实验基本要求实验前要求学生一定要先了解实验目的、内容、要求以及注意事项，要求学生熟悉实验对象，设计并编写相应的算法。学生应独立完成所布置实验内容，编写代码，运行程序，记录结果并撰写实验报告。三、实验报告要求实验结束后，应及时整理出实验报告，实验报告提交书面文档。四、考核方式理论考试（60％）＋实验（30％）+作业（10%）五、实验内容与指导实验一快速排序问题1．实验目的(1)用分治法求解该问题。2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。3．实验内容有n个无序的数值数据，现要求将其排列成一个有序的序列。4.实验步骤(1)输入实现该问题的源代码；(2)输入测试数据，验证代码的正确性。5.实验要求(1)做好实验预习，熟悉本实验中所使用的开发环境。(2)写出实验报告①实验目的②实验内容③出错信息及处理方法④实验结果实验二最少硬币问题1．实验目的(1)用动态规划求解该问题。2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。3．实验内容有n种不同面值的硬币，各硬币面值存于数组T[1:n]；现用这些面值的钱来找钱；各面值的个数存在数组Num[1:n]中。对于给定的1≤n≤10，硬币面值数组、各面值的个数及钱数m，0<=m<=2001，设计一个算法，计算找钱m的最少硬币数。4.实验步骤(1)输入实现该问题的源代码；(2)输入测试数据，验证代码的正确性。5.实验要求(1)做好实验预习，熟悉本实验中所使用的开发环境。(2)写出实验报告①实验目的②实验内容③出错信息及处理方法④实验结果实验三租用游艇问题1．实验目的(1)用动态规划求解该问题。2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。3．实验内容长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1≤i＜j≤n。设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。要求用动态规划法。4.实验步骤(1)输入实现该问题的源代码；(2)输入测试数据，验证代码的正确性。5.实验要求(1)做好实验预习，熟悉本实验中所使用的开发环境。(2)写出实验报告①实验目的②实验内容③出错信息及处理方法④实验结果实验四汽车加油问题1．实验目的(1)用贪心法求解该问题。2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。3．实验内容一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。4.实验步骤(1)输入实现该问题的源代码；(2)输入测试数据，验证代码的正确性。5.实验要求(1)做好实验预习，熟悉本实验中所使用的开发环境。(2)写出实验报告①实验目的②实验内容③出错信息及处理方法④实验结果实验五最小重量机器设计问题1．实验目的(1)用回溯法求解该问题。2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。3．实验内容设某一机器由n个部件组成，每一种部件可以从m个不同的供应商处购得。设是从供应商j处购得的部件i的重量，是相应的价格。设计一个算法，给出总价格不超过的最小重量机器设计。4.实验步骤(1)输入实现该问题的源代码；(2)输入测试数据，验证代码的正确性。5.实验要求(1)做好实验预习，熟悉本实验中所使用的开发环境。(2)写出实验报告①实验目的②实验内容③出错信息及处理方法④实验结果实验六世界名画陈列问题1．实验目的(1)用回溯法求解该问题。2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。3．实验内容针对世界名画陈列馆问题，设计一个算法，计算警卫机器人的最佳哨位安排，使得名画陈列馆的每个陈列室都在警卫机器人监视之下，且所用的警卫机器人数目最少。4.实验步骤(1)输入实现该问题的源代码；(2)输入测试数据，验证代码的正确性。5.实验要求(1)做好实验预习，熟悉本实验中所使用的开发环境。(2)写出实验报告①实验目的②实验内容③出错信息及处理方法④实验结果实验七最佳调度问题1．实验目的(1)用分支限界法求解该问题。2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。3．实验内容假设有n个任务由k个可并行工作的机器来完成。