实验二 动态规划.doc

西北师范大学数信学院学生实验报告学号： 201271040138 2013 年 10 月 30 日系别计算机科学与工程学院专业软件工程班级12软件姓名赵海龙课程名称面向对象程序设计课程类型实验学时数实验名称JAVA基本程序设计结构实验目的和要求：1 掌握JAVA基本知识2 用JAVA的知识体系编程实验内容：动态规划算法设平面上有一个mn 的网格，将左下角的网格点标记为（0,0）而右上角的网格点标记为（m,n）。某人想从（0,0）出发沿网格线行进到达（m,n），但是在网格点（i,j）处他只能向下行进或者向右行进，向下行进的代价为aij（amj ），向右行进的代价是bij（bin ）。试设计一个动态规划算法，在这个网格中为该旅行者寻找一条代价最小的旅行路线。 代码：import java.util.*;import static java.lang.Math.*;public class MNpublic static void main(String args)final int m = 5;final int n = 5; / 定义向上，向右的代价 ，以及最优代价 int Cost = new intm+1n+1; int Down = new intmn+1; int Right = new intm+1n; int count = 0, i = 0, j = 0;/ 随机的产生向上代价数组Above，并输出 for(i = 0; i m; i+) for(j = 0; j n+1; j+) Random rand = new Random(); Downij = (rand.nextInt(5)+5); System.out.printf(Down:n); for(i = 0; i m; i+) for(j = 0; j n+1; j+) System.out.printf(%5d, Downij); System.out.println(n); / 随机的产生向上代价数组Right，并输出 for(i = 0; i m+1; i+) for(j = 0; j n; j+) Random rand = new Random(); Rightij = (rand.nextInt(5)+5); System.out.printf(Right:n); for(i = 0; i m+1; i+) for(j = 0; j n; j+) System.out.printf(%5d, Rightij); System.out.println(n); / 求出最优代价数组Cost并输出 Cost00 = 0; for(i = 1; i m+1; i+) Costi0 = Costi-10 + Downi-10; for(j = 1; j n+1; j+) Cost0j = Cost0j-1 + Right0j-1; for(i = 0; i m; i+) for(j = 0; j n; j+) Costi+1j+1 = min(Costi+1j + Righti+1j), (Costij+1 + Downij+1); System.out.printf(最优距离:n); for(i = 0; i m+1; i+) for(j = 0; j = 0 ; i- ) if ( di = 0 ) System.out.println(Right); else System.out.println(Down); 实验结果：Down: 8 6 6 9 5 7 6 7 6 6 9 7 7 5 7 5 5 5 5 8 7 5 8 6 5 5 8 5 5 5Right: 6 5 8 9 7 7 6 6 6 8 7 9 5 9 9 5 6 6 8 7 5 7 9 7 6 6 5 9 7 7最优距离: 0 6 11 19 28 35 8 12 17 23 29 37 14 19 23 28 37 44 21 24 30 33 41 48 26 31 37 38 45 51 31 36 41 43 50 56请输入你想到达的坐标位置：横坐标：3纵坐标：4RightDownRightDownDownRightRight实验总结： 通过对JAVA的知识学习，掌握了很多的JAVA中的细节，希望在以后的学习中，能更好的应用所学的知识。 成绩批阅教师批阅日期