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

这是一份实验报告,内容是矩阵连乘问题和最长公共子序列问题

《算法设计与分析》实验报告

实验序号： 实验项目名称:编程实现动态规划的算法

这是一份实验报告,内容是矩阵连乘问题和最长公共子序列问题

附源程序清单：

最长公共子序列：

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<Character>

resultList =

New ArrayList<Character>();

/**

*

计算最优值

*

@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++) {

c[i][0] = 0;

}

for

这是一份实验报告,内容是矩阵连乘问题和最长公共子序列问题

int

i = 1; i <= n; i++) {

c[0][i] = 0;

}

for

(

int

i = 1; i <= m; i++) {

for

(

int

j = 1; j <= n; j++) {

这是一份实验报告,内容是矩阵连乘问题和最长公共子序列问题

if

(x[i] == y[j]) {

c[i][j] = c[i - 1][j - 1] + 1;

b[i][j] = 1;

}

else

if

(c[i - 1][j] >= c[i][j - 1]) {

c[i][j] = c[i - 1][j];

b[i][j] = 2;

这是一份实验报告,内容是矩阵连乘问题和最长公共子序列问题

}

else

{

c[i][j] = c[i][j - 1];

b[i][j] = 3;

}

}

}

}

public

static

void

这是一份实验报告,内容是矩阵连乘问题和最长公共子序列问题

lcs(

int

i,

int

j,

char

x[],

int

[][] b) {

if

(i == 0 || j == 0) {

return

;

}

这是一份实验报告,内容是矩阵连乘问题和最长公共子序列问题

if

(b[i][j] == 1) {

lcs

(i - 1, j - 1, x, b);

resultList

.add(x[i]);

}

else

if

(b[i][j] == 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 = newint[x.length][y.length];

int[][] c = New int[x.length][y.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<Character>

resultList

=

new

ArrayList<Character>();

/**

*

计算最优值

这是一份实验报告,内容是矩阵连乘问题和最长公共子序列问题

*

@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++) {

c[i][0] = 0;

}

for

(

int

i = 1; i <= n; i++) {

c[0][i] = 0;

}

本文来源：https://www.bwwdw.com/article/mz61.html