算法导论课程设计.doc

课 程 设 计 报 告课程名称 算法导论 课题名称 棋子移动问题 专 业 班 级 学 号 姓 名 指导教师 年 月 日湖 南 工 程 学 院课 程 设 计 任 务 书课程名称 算法导论 课 题 棋子移动问题 专业班级 学生姓名 学 号 指导老师 审 批 任务书下达日期 年 月 日任务完成日期 年 月 日一、设计内容与设计要求1设计内容： 课本P220页 15-6 在棋盘上移动问题假设有一张个方格的棋盘以及一个棋子。必须根据以下的规则把棋子从棋盘的底边移动到棋盘的顶边。在每一步你可以把棋子移动到三个方格中的一个：1） 正上方的方格，2） 左上方的方格（只能当这个棋子不在最左列的时候），3） 右上方的方格（只能当这个棋子不在最右列的时候）。每次从方格x移动到方格y，会得到p（x，y）块钱。已知所有对（x，y）的p（x，y），只要从x到y的移动都是合法的。不要假设p（x，y）的正值。请给出一个计算移动方式集合的算法，把棋子从棋盘底边的某个地方移动到棋盘顶边的某个地方，同时收集尽可能多的钱。你的算法可以自由选择底边的任意方格作为起始点，顶边上的任意方格作为目的点，来最大化一路上收集到的钱数。你的算法执行时间是多少?2设计要求：l 课程设计报告正文内容(一)问题的描述；(二)算法设计与分析，内容包括1， 算法设计，对问题的分析和算法的设计2，算法描述，以伪代码形式的算法3，算法分析，主要是算法的正确性和运行时间的分析（三）算法实现所有程序的原代码，要求用C或java语言程序实现，并对程序写出必要的注释。l 书写格式a要求用A4纸打印成册b正文格式：一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。c正文的内容:正文总字数要求在3000字左右（不含程序原代码）。d封面格式如下页。l 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：a平时出勤 （占10%）b系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）c程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）d设计报告（占30%）e独立完成情况（占10%）。注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。l 课程验收要求a判定算法设计的合理性，运行相关程序，获得正确的数值结果。b回答有关问题。c提交课程设计报告。d提交软盘（源程序、设计报告文档）。e依内容的创新程度，完善程序情况及对程序讲解情况打分。三、进度安排1、 班级： 信息与计算科学：1001、1002、10032、 主讲教师：阳卫锋3、 时间安排：第 16 周 星期一 8时：30分11时：30分 星期二 8时：30分11时：30分 星期四 8时：30分11时：30分 星期五 8时：30分11时：30分摘要动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。我们保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。因此在考虑棋子移动问题时，我们可以利用动态规划的思想找到最优解。在这里我们利用Java语言实现了棋子移动问题的算法。关键字：动态规划；Java；一、问题描述1.基本情况假设有一张个方格的棋盘以及一个棋子。必须根据以下的规则把棋子从棋盘的底边移动到棋盘的顶边。在每一步你可以把棋子移动到三个方格中的一个：4） 正上方的方格，5） 左上方的方格（只能当这个棋子不在最左列的时候），6） 右上方的方格（只能当这个棋子不在最右列的时候）。每次从方格x移动到方格y，会得到p（x，y）块钱。已知所有对（x，y）的p（x，y），只要从x到y的移动都是合法的。不要假设p（x，y）的正值。2.需要解决的问题请给出一个计算移动方式集合的算法，把棋子从棋盘底边的某个地方移动到棋盘顶边的某个地方，同时收集尽可能多的钱。你的算法可以自由选择底边的任意方格作为起始点，顶边上的任意方格作为目的点，来最大化一路上收集到的钱数。你的算法执行时间是多少?2、 算法设计与分析1. 算法设计对于此类问题我们首先可以对其模型化，个方格的棋盘我们可以假设为在个不同的地方分别可以争取钱，其中到某一个区域上的数字为负数则表示在该处消费了多少钱，为正数则表示在该处挣到了多少钱。这个算法就是要实现一个争取最多钱的最大问题，从定义好的二维数组amn的最后一行i=m-1,j=j（0，1，.n-1）开始，依次往上到第一行，i从0到m-1的过程中，如j=0时，则在往上一行继续收集最大的数字时j=j+1或j=0；如j在0到n-1之间时（不包括两端点值），则在往上一行继续收集最大的数字时j=j+1或j=j或j=j-1；如j=n-1时，则在往上一行继续收集最大的数字时j=j或j=n-1。依次类推知道i=0时，通过计算每一行取得的最大值fij=max1(fi+1j,fi+1j-1)+aij）累加起来，得出的就是最大的争取钱数2.算法描述 初始化过程 a = new intnn;System.out.println(请输入方格系数矩阵：);for (int i = 0; i a.length; i+) for (int j = 0; j = 0; i-) if (k = 0) if (ai0 ai1) max = ai0;k = 0;result = result + max + ; else max = ai1;k = 1;result = result + max + ; else if (k = ai.length - 1) if (aiai.length - 1 aiai.length - 2) max = aiai.length - 1;k = ai.length - 1;result = result + max + ; else max = aiai.length - 2;k = ai.length - 2;result = result + max + ; else if (aik = aik - 1 & aik = aik + 1) max = aik;result = result + max + ; else if (aik + 1 aik - 1& aik + 1 aik) max = aik + 1;k = k + 1;result = result + max + ; else max = aik - 1;k = k - 1;result = result + max + ;sum = sum + max;JOptionPane.showMessageDialog(null, 收集钱所走的路线： + result + n+ 收集到的钱最大为： + sum);result = ;3. 算法时间复杂度分析像在矩阵链乘法问题一样，棋子移动问题的递归解涉及到建立一个最优解的值的递归式。定义ci，j为棋子移动的最优子结构可得递归式：因此有以下程序CHECKERBOARD(n, p)for j 1 to ndo d1, j 0for i 2 to ndo for j 1 to ndo di, j if j 1then di, j di 1, j 1 + p(i 1, j 1), (i, j )wi, j j 1if di 1, j + p(i 1, j ), (i, j ) di, j then di, j di 1, j + p(i 1, j ), (i, j )wi, j jif j di, j then di, j di 1, j + 1 + p(i 1, j + 1), (i, j )wi, j j + 1return d and w由CHECKERBOARD可以看出棋子移动的时间复杂度为3、 程序调试1. 使用说明 1）输入的第一个是棋盘的尺寸 2）下面的数组是给棋盘各个位置附上值2. 输入样例请输入方格个数n：5请输入方格系数矩阵：1 -2 4 9 35 3 2 -1 61 -3 8 2 42 5 7 6 -15 4 7 9 13.运行结果预览 注：选择5为起始点 注：选择1为起始点 注：选择4为起始点四、心得体会 一周的课程设计结束了，在这次的课程设计中我不仅检验到了运用我所学习的知识也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情。在设计过程中，与同学分工设计，和同学们相互探讨，相互学习。 课程设计是我们专业课程知识综合应用的实践训练，是我们迈向社会从事职业工作前一个必不少的过程”千里之行始于足下”，通过这次课程设计，我深深体会到这句千古名言的真正含义我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础 在这次设计过程中，体现出团队合作的重要性以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。 5、 参考文献1 Thomas H.Cormen ，Charles.Leiserson ，Ronlad L.Riverst， Clifford Stein 著，潘金贵，顾铁成，李有法，叶懋 算法导论M北京：机械工业出版社，20062 王晓东 算法设计与实验题解M北京：电子工业出版社，2006附件程序代码：package com.yjb;/* 此程序用来解决棋子在棋盘上移动收集最大钱数的问题 * */import java.awt.GridLayout;import java.awt.event.MouseAdapter;import java.awt.event.MouseEvent;import java.util.Scanner;import javax.swing.JButton;import javax.swing.JFrame;import javax.swing.JOptionPane;public class ChessFinal1 static JFrame frame;static int n = 5;static int k;private static int a;private static int max;private static int sum;private static String result = ;public static void main(String args) frame = new JFrame();System.out.print(请输入方格个数n：);Scanner sc = new Scanner(System.in);n = sc.nextInt();frame.getContentPane().setLayout(new GridLayout(n, 1);frame.setLocation(100, 100);a = new intnn;System.out.println(请输入方格系数矩阵：);for (int i = 0; i a.length; i+) for (int j = 0; j ai.length; j+) aij = sc.nextInt();/ 在方格的每个位置上添加按钮，并且给最后一行按钮设置监听JButton jl = new JButtonnn;for (int i = 0; i n; i+) for (int j = 0; j = 0; i-) if (k = 0) if (ai0 ai1) max = ai0;k = 0;result = result + max + ; else max = ai1;k = 1;result = result + max + ; else if (k = ai.length - 1) if (aiai.length - 1 aiai.length - 2) max = aiai.length - 1;k = ai.length - 1;result = result + max + ; else max = aiai.length - 2;k = ai.length - 2;result = result + max + ; else if (aik = aik - 1 & aik = aik + 1) max