编程实现动态规划的算法实验报告.doc

算法设计与分析实验报告实验序号： 实验项目名称:编程实现动态规划的算法学号姓名 专业、班 11软服2班实验地点指导教师实验时间2013/11/29一、实验目的及要求 1. 体验实现程序的运行过程 2. 写出源程序，并编译运行。2、 实验内容与步骤 1.矩阵连乘问题（或多边形游戏问题） 2.最长公共子序列问题（或最接近点对问题）3、 实验方法 4、 实验结果与数据处理最长公共子序列：乘法五、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日期：附源程序清单： 最长公共子序列：Import java.io.BufferedReader; Import java.io.IOException; Import java.io.InputStreamReader; Import java.util.ArrayList; Import java.util.Scanner; Import java.util.List; /* * 动态规划法解最长公共子系列。 * author蓝冠恒 */Public class LcsLength publicstatic List resultList = New ArrayList(); /* * 计算最优值 * param x * 字符系列数组 * param y * 字符系列数组 * param c * 存储x和y最长公共子系列长度数组 * param b * 记录c中元素对应子问题的解的数组 */ public static void lcsLength(char x, char y, int c, int b) int m = x.length - 1; int n = y.length - 1; resultList.clear(); for (int i = 1; i = m; i+) ci0 = 0; for (int i = 1; i = n; i+) c0i = 0; for (int i = 1; i = m; i+) for (int j = 1; j = cij - 1) cij = ci - 1j; bij = 2; else cij = cij - 1; bij = 3; public static void lcs(int i, int j, char x, int b) if (i = 0 | j = 0) return; if (bij = 1) lcs(i - 1, j - 1, x, b); resultList.add(xi); else if (bij = 2) lcs(i - 1, j, x, b); else lcs(i, j - 1, x, b); publicstaticvoid main(String arg) String a; String input; char x; char y; Scanner scan= New Scanner(System.in); BufferedReader in = New BufferedReader(New InputStreamReader(System.in); do try do System.out.println(请输入第一串字符系列); input = in.readLine().trim(); while(input.equals(); input = S + input; x = input.toCharArray(); do System.out.println(请输入第二串字符系列); input = in.readLine().trim(); while (input.equals(); input = S + input; y = input.toCharArray(); int b = newintx.lengthy.length;int c = New intx.lengthy.length; lcsLength(x, y, c, b);/ 计算最优值lcs(x.length- 1, y.length- 1, x, b);/ 构造最长公共子系列int size = resultList.size(); System.out.print(最长公共子系列为:); for(int i = 0; i size; i+) System.out.print(resultList.get(i); System.out.println(n); catch (IOException e) e.printStackTrace(); System.out.print(继续输入请按y。退出请按任意键！); a=scan.nextLine(); while (a.equals(y); 连乘问题 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Scanner; import java.util.List; /* * 动态规划法解最长公共子系列。 * author 蓝冠恒 */ public class LcsLength public static List resultList = new ArrayList(); /* * 计算最优值 * param x * 字符系列数组 * param y * 字符系列数组 * param c * 存储x和y最长公共子系列长度数组 * param b * 记录c中元素对应子问题的解的数组 */ public static void lcsLength(char x, char y, int c, int b) int m = x.length - 1; int n = y.length - 1; resultList.clear(); for (int i = 1; i = m; i+) ci0 = 0; for (int i = 1; i = n; i+) c0i = 0; for (int i = 1; i = m; i+) for (int j = 1; j = cij - 1) cij = ci - 1j; bij = 2; else cij = cij - 1; bij = 3; public static void lcs(int i, int j, char x, int b) if (i = 0 | j = 0) return; if (bij = 1) lcs(i - 1, j - 1, x, b); resultList.add(xi); else if (bij = 2) lcs(i - 1, j, x, b); else lcs(i, j - 1, x, b); public static void main(String arg) String a; String input; char x; char y; Scanner scan= new Scanner(System.in); BufferedReader in = new BufferedReader(new InputStreamReader(System.in); do try do System.out.println(请输入第一串字符系列); input = in.readLine().trim(); while (input.equals(); input = S + input; x = input.toCharArray(); do System.out.println(请输入第二串字符系列); input = in.readLine().trim(); while (input.equals(); input = S + input; y = input.toCharArray(); int b = new intx.lengthy.length; int c = new intx.lengthy.length; lcsLength(x, y, c, b);/ 计算最优值 lcs(x.length- 1, y.length- 1, x, b);/ 构造最长公共子系列int size = resultList.size(); System.out.print(最长公共子系列为:); for (int i = 0; i