《算法设计与分析》实验指导书20161022-.doc

《算法设计与分析》实验指导书 本文档主要用于《算法设计与分析》课程的实验指导。《算法设计与分析》旨在教会学生处理各种问题的方法，通过实验，使学生能够把所学的方法用于具体的问题，并对所用算法进行比较分析，从而提高学生分析问题、解决问题的能力。 通过该课程的实验，使学生对课堂中所讲述的内容有一个直观的认识，更好地掌握所学的知识，培养学生的实际动手能力，加强学生创新思维能力的培养。 本课程设计了6个实验。实验内容包括应用分治法、动态规划、贪心法、回溯法以及分支限界法设计求解问题的算法。 一、实验内容安排 序号 实验项目 内 容 提 要 实验学时 实验类型 每组人数 实验 要求 1 快速排序问题 有n个无序的数值数据，现要求将其排列成一个有序的序列。要求用分治策略。 2 验证 1 必做 2-1 租用游艇问题 长江游艇俱乐部在长江上设置了n 个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i 到游艇出租站j 之间的租金为r(i,j),1≤i＜j≤n。设计一个算法，计算出从游艇出租站1 到游艇出租站n 所需的最少租金 2-2 最少硬币问题有n种不同面值的硬币，各硬币面值存于数组T[1:n]现用这些面值的钱来找钱；各面值的个数存在数组Num[1:n]中。对于给定的1≤n≤10，硬币面值数组、各面值的个数及钱数m，0=m=2001，设计一个算法计算找钱m的最少硬币数。 3 汽车加油问题一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。 4 最小重量机器设计问题 设某一机器由个部件组成，每一种部件可以从个不同的供应商处购得。设是从供应商处购得的部件的重量，是相应的价格。设计一个算法，给出总价格不超过的最小重量机器设计。 5 世界名画陈列问题世界名画陈列馆问题设计一个算法，使得名画陈列馆的每个陈列室都在警卫机器人监视之下，所用的警卫机器人数目最少。 6 最佳调度问题 假设有n个任务由k个可并行工作的机器来完成。完成任务i需要时间，设计最佳调度，使得完成全部任务的时间最早 二、实验基本要求 要求学生提前了解实验目的、实验内容、实验环境和实验要求；要求学生根据实验内容提前设计算法并编写相应的代码；要求学生将写好的实验代码通过在线测试平台验证是否正确；要求学生独立完成，长江游艇俱乐部在长江上设置了n 个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i 到游艇出租站j 之间的租金为r(i,j),1≤i＜j≤n。设计一个算法，计算出从游艇出租站1 到游艇出租站n 所需的最少租金最少硬币问题有n种不同面值的硬币，各硬币面值存于数组T[1:n]现用这些面值的钱来找钱；各面值的个数存在数组Num[1:n]中。对于给定的1≤n≤10，硬币面值数组、各面值的个数及钱数m，0=m=2001，设计一个算法计算找钱m的最少硬币数。问题一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。设某一机器由个部件组成，每一种部件可以从个不同的供应商处购得。设是从供应商处购得的部件的重量，是相应的价格。设计一个算法，给出总价格不超过的最小重量机器设计。世界名画陈列问题世界名画陈列馆问题设计一个算法，使得名画陈列馆的每个陈列室都在警卫机器人监视之下，所用的警卫机器人数目最少。假设有n个任务由k个可并行工作的机器来完成。完成任务i需要时间，设计最佳调度，使得完成全部任务的时间最早 3