首页 算法最长子序列

算法最长子序列

举报
开通vip

算法最长子序列算法最长子序列 算法设计与分析实验报告 一、实验题目 求最长公共子序列问题。 三、源程序: package javaapplication1; import java.io.*; public class LCS { static int length = 0; //保存最长公共子序列的长度 static String str_same = ""; //保存最长公共子序列 static int k = 0; public static void main(String args[]) thro...

算法最长子序列
算法最长子序列 算法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 与分析实验 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 一、实验题目 求最长公共子序列问题。 三、源程序: package javaapplication1; import java.io.*; public class LCS { static int length = 0; //保存最长公共子序列的长度 static String str_same = ""; //保存最长公共子序列 static int k = 0; public static void main(String args[]) throws IOException { char x[],y[]; BufferedReader read_x = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt"))); String str_x=read_x.readLine(); String str_y=read_x.readLine(); //原始比较的两个串 try{ str_x=" "+str_x; str_y=" "+str_y; } catch(Exception e){ e.printStackTrace(); } x=str_x.toCharArray(); y=str_y.toCharArray(); int b[][]=new int[x.length][y.length]; lcsLength(x,y,b); lcs(x.length-1,y.length-1,x,b); PrintWriter print = new PrintWriter(new OutputStreamWriter(new FileOutputStream("output.txt"))); print.println(length); print.println(str_same); System.out.println("公共子序列长度:"+length); System.out.println("最长公共子序列:"+str_same); System.out.print("\n"); read_x.close(); print.close(); } 1 public static void lcsLength(char []x,char []y,int [][]b) { int xMaxIndex=x.length-1; int yMaxIndex=y.length-1; int count[][]=new int[xMaxIndex+1][yMaxIndex+1]; for(int i=0;i<=xMaxIndex;i++) { count[i][1]=0; } for(int i=0;i<=yMaxIndex;i++) { count[0][i]=0; } for(int i=1;i<=xMaxIndex;i++) for(int j=1;j<=yMaxIndex;j++) { if(x[i]==y[j]) //如果相等 则对角线加一 { count[i][j]=count[i-1][j-1]+1; b[i][j]=1; } //如果不等,则比较上方和左方,取最大值 else if(count[i-1][j]>=count[i][j-1]) { count[i][j]=count[i-1][j]; b[i][j]=2; } else { count[i][j]=count[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) { length ++; lcs(i-1,j-1,x,b); 2 str_same += x[i]; } else if(b[i][j]==2) { lcs(i-1,j,x,b); } else if(b[i][j]==3) { lcs(i,j-1,x,b); } } } 3 二、实验 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 图 开始 void lcsLength(char x=str_x.toCharArray()[]x,char []y,int ;[][]b)y=str_y.toCharArray() ;import java.io.*;public class LCSint xMaxIndex=x.length-1; int yMaxIndex=y.length-1;int b[][]=new int count[][]=new int[x.length][y.length];int[xMaxIndex+1][yMaxIndex+1];lcsLength(x,y,b);lcs(x.length-static int length = 1,y.length-1,x,b);0;static String str_same = ""; static int k = 0; PrintWriter print = new PrintWriter(new int OutputStreamWriter(new void main(String i=0;i<=xMaxIndex;i+FileOutputStream("output.txt")));args[]) throws + IOException Yprint.println (length);prin char x[],y[];BufferedReader t.println(strread_x=new BufferedReader(new _same);count[i][1]=0;InputStreamReader(new NFileInputStream("input.txt"))); System.out.println("String 公共子序列长str_x=read_x.readLine();度:"+length);System.oString int ut.println("最长公共str_y=read_x.readLine();i=0;i<=yMaxIndex;子序列:"+str_same);i++ Ystr_x=" "+str_x; str_y=" "+str_y;read_x.close();print.closecount[0][i]=0;(); catch(Exception e){ e.printStackTrace() ; } 4 N void lcs(int int i,int j,char b[i][j]==3i=1;i<=xMaxInd[]x,int [][]b)ex;i++ Y lcs(i,j-i==0||j==0int 1,x,b); j=1;j<=yMaxIndYex;j++ Yreturn;结束NN x[i]==y[j] Yb[i][j]==1count[i][j]=cou nt[i-1][j-1]+1; Yb[i][j]=1Nlength ++; lcs(i-1,j- 1,x,b); Ncount[i-str_same += 1][j]>=counx[i];t[i][j-1] Y b[i][j]==2count[i][j]=c ount[i- 1][j];b[i][j]NY=2;lcs(i- 1,j,x,b);count[i][j]=c ount[i][j- 1];b[i][j]=3; 四、结果截屏 5
本文档为【算法最长子序列】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_769014
暂无简介~
格式:doc
大小:27KB
软件:Word
页数:7
分类:生活休闲
上传时间:2017-12-05
浏览量:30