算法导论课程设计

《算法导论课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计报告课程名称算法导论课题名称棋子移动问题专业班级学号姓名指导教师年月日16湖南工程学院课程设计任务书课程名称算法导论课题棋子移动问题专业班级学生姓名学号指导老师审批任务书下达日期年月日任务完成日期年月日16一、设计内容与设计要求1．设计内容：课本P220页15-6在棋盘上移动问题假设有一张个方格的棋盘以及一个棋子。必须根据以下的规则把棋子从棋盘的底边移动到棋盘的顶边。在每一步你可以把棋子移动到三个方格中的一个：1）正上方的方格，2）左上方的方格（只能当这个棋子不在最左列的时候），3）右上方的

2、方格（只能当这个棋子不在最右列的时候）。每次从方格x移动到方格y，会得到p（x，y）块钱。已知所有对（x，y）的p（x，y），只要从x到y的移动都是合法的。不要假设p（x，y）的正值。请给出一个计算移动方式集合的算法，把棋子从棋盘底边的某个地方移动到棋盘顶边的某个地方，同时收集尽可能多的钱。你的算法可以自由选择底边的任意方格作为起始点，顶边上的任意方格作为目的点，来最大化一路上收集到的钱数。你的算法执行时间是多少?2．设计要求：l课程设计报告正文内容(一)问题的描述；(二)算法设计与分析，内容包括1

3、，算法设计，对问题的分析和算法的设计2，算法描述，以伪代码形式的算法3，算法分析，主要是算法的正确性和运行时间的分析（三）算法实现所有程序的原代码，要求用C或java语言程序实现，并对程序写出必要的注释。l书写格式a．要求用A4纸打印成册b．正文格式：一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。c．正文的内容:正文总字数要求在3000字左右（不含程序原代码）。d．封面格式如下页。l考核方式16指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和

4、设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：a．平时出勤（占10%）b．系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）c．程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）d．设计报告（占30%）e．独立完成情况（占10%）。注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。l课程验收要求a．判定算法设计的合理性，运行相关程序，获得正确的数值结果。b．回答有关问题。c

5、．提交课程设计报告。d．提交软盘（源程序、设计报告文档）。e．依内容的创新程度，完善程序情况及对程序讲解情况打分。三、进度安排1、班级：信息与计算科学：1001、1002、10032、主讲教师：阳卫锋3、时间安排：第16周星期一8时：30分——11时：30分星期二8时：30分——11时：30分星期四8时：30分——11时：30分星期五8时：30分——11时：30分16摘要动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的

6、解。动态规划算法其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。我们保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。因此在考虑棋子移动问题时，我们可以利用动态规划的思想找到最优解。在这里我们利用Java语言实现了棋子移动问题的算法。关键

7、字：动态规划；Java；16一、问题描述1.基本情况假设有一张个方格的棋盘以及一个棋子。必须根据以下的规则把棋子从棋盘的底边移动到棋盘的顶边。在每一步你可以把棋子移动到三个方格中的一个：1）正上方的方格，2）左上方的方格（只能当这个棋子不在最左列的时候），3）右上方的方格（只能当这个棋子不在最右列的时候）。每次从方格x移动到方格y，会得到p（x，y）块钱。已知所有对（x，y）的p（x，y），只要从x到y的移动都是合法的。不要假设p（x，y）的正值。2.需要解决的问题请给出一个计算移动方式集合的算法，

8、把棋子从棋盘底边的某个地方移动到棋盘顶边的某个地方，同时收集尽可能多的钱。你的算法可以自由选择底边的任意方格作为起始点，顶边上的任意方格作为目的点，来最大化一路上收集到的钱数。你的算法执行时间是多少?二、算法设计与分析1.算法设计对于此类问题我们首先可以对其模型化，个方格的棋盘我们可以假设为在个不同的地方分别可以争取钱，其中到某一个区域上的数字为负数则表示在该处消费了多少钱，为正数则表示在该处挣到了多少钱。这个算法就是要实现一个争取最多钱的最大问题，从定义好的二维数组