編程實現(xiàn)動態(tài)規(guī)劃的算法實驗報告

1、算法設(shè)計與分析實驗報告實驗序號： 實驗項目名稱:編程實現(xiàn)動態(tài)規(guī)劃的算法學號姓名 專業(yè)、班 11軟服2班實驗地點指導教師實驗時間2013/11/29一、實驗目的及要求 1. 體驗實現(xiàn)程序的運行過程 2. 寫出源程序，并編譯運行。2、 實驗內(nèi)容與步驟 1.矩陣連乘問題（或多邊形游戲問題） 2.最長公共子序列問題（或最接近點對問題）3、 實驗方法 4、 實驗結(jié)果與數(shù)據(jù)處理最長公共子序列：乘法五、分析與討論對上機實踐結(jié)果進行分析，上機的心得體會。六、教師評語簽名：日期：附源程序清單： 最長公共子序列：Import java.io.BufferedReader; Import java.io.IOExc

2、eption; Import java.io.InputStreamReader; Import java.util.ArrayList; Import java.util.Scanner; Import java.util.List; /* * 動態(tài)規(guī)劃法解最長公共子系列。 * author藍冠恒 */Public class LcsLength publicstatic List<Character> resultList = New ArrayList<Character>(); /* * 計算最優(yōu)值 * param x * 字符系列數(shù)組 * param y *

3、字符系列數(shù)組 * param c * 存儲x和y最長公共子系列長度數(shù)組 * param b * 記錄c中元素對應子問題的解的數(shù)組 */ 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+

4、) for (int j = 1; j <= n; j+) if (xi = yj) cij = ci - 1j - 1 + 1; bij = 1; else if (ci - 1j >= 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);

5、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("請輸入第一串字符系列"

6、;); 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 =

7、newintx.lengthy.length;int c = New intx.lengthy.length; lcsLength(x, y, c, b);/ 計算最優(yōu)值lcs(x.length- 1, y.length- 1, x, b);/ 構(gòu)造最長公共子系列int size = resultList.size(); System.out.print("最長公共子系列為:"); for(int i = 0; i < size; i+) System.out.print(resultList.get(i); System.out.println("n&qu

8、ot;); catch (IOException e) e.printStackTrace(); System.out.print("繼續(xù)輸入請按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;

9、import java.util.List; /* * 動態(tài)規(guī)劃法解最長公共子系列。 * author 藍冠恒 */ public class LcsLength public static List<Character> resultList = new ArrayList<Character>(); /* * 計算最優(yōu)值 * param x * 字符系列數(shù)組 * param y * 字符系列數(shù)組 * param c * 存儲x和y最長公共子系列長度數(shù)組 * param b * 記錄c中元素對應子問題的解的數(shù)組 */ public static void lcsLen

10、gth(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 <= n; j+) if (xi = yj) cij = ci - 1j - 1 + 1; bij = 1; else if (ci - 1

11、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(Stri

12、ng 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"

13、+ 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);/ 計算最優(yōu)值 lcs(x.length- 1, y.length- 1, x, b);/ 構(gòu)造最長公共子系列int size = resultList.size(); System.out.print("最長公共子系列為:"); for (int i = 0; i < size; i+) System.out.print