文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 计算机算法设计与分析实验报告
侵权投诉

计算机算法设计与分析实验报告

实验一:最长公共子序列问题

一、实验目的与要求

1、明确子序列公共子序列的概念

2、最长公共子序列(Longest Common Subsequence,简称LCS) 的概念 3、利用动态规划解决最长公共子序列问题

二、实验题:

问题描述:字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1, ,xm-1”,序列Y=“y0,y1, ,yk-1”是X的子序列,存在X的一个严格递增下标序列<i0,i1, ,ik-1>,使得对所有的j=0,1, ,k-1,有xij=yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。

给定两个序列A和B,称序列Z是A和B的公共子序列,是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。

三、实验代码

#include<stdlib.h> #include<stdio.h> #include<string.h> #define Size 100

void LCSLength(int m,int n,char *x,char *y,int c[Size][Size],int b[Size][Size]) { int i,j;

for(i=1;i<=m+1;i++) c[i][0]=0; for(i=1;i<=n+1;i++) c[0][i]=0; for(i=1;i<=m+1;i++) for(j=1;j<=n+1;j++) { if(x[i]==y[j])

{ c[i][j]=c[i-1][j-1]+1; b[i][j]=0; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=1; }

else { c[i][j]=c[i][j-1]; b[i][j]=2; } }

}

void LCS(int i,int j,char *x,int b[Size][Size]) { if(i==0||j==0) return; if(b[i][j]==0)

{ LCS(i-1,j-1,x,b); printf("%c",x[i]); } else if(b[i][j]==1) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); }

main()

上一页第2页

你可能喜欢

  • 背包问题
  • 偏微分方程
  • VB 串口
  • 河南中考数学试题及答案
  • 通信设计
  • 页面置换算法实验报告
  • 计算机算法设计与分析

热门文档

相关文档

  • 计算机算法设计与分析实验报告

    计算机算法设计与分析 实验报告 专学姓 业: 测试技术 10-01 号: 54101311 名: XXX 指导老师: 宋胜利 实验一:棋盘覆盖一、实验目的与要求 1、理解算法的概念 ...

  • 计算机算法设计与分析实验报告

    贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告课程名称:算法设计与分析 姓名: 熊齐超 实验序号:一 班级:软件 121 学号:1208060220 实验日期:2014/11...

  • 计算机算法设计与分析实验报告

    华北电力大学科技学院 实验报告 实验名称 课程名称 算法设计与分析算法设计与分析 专业班级:计算机 10k1 学号:101909010121 学生姓名:孙刚成绩: 实验...

  • 计算机算法与设计分析实验报告

    计算机算法与设计分析 计算机算法与设计分析 实验报告 班级: 姓名: 学号: 目录实验一 分治与递归 ………1 1、基本递归算法………1 2、棋盘覆盖问题………...

  • 计算机算法与设计分析实验报告

    计算机算法与设计分析实验报告 隐藏>> 计算机算法与设计分析 实验报告 班级: 姓名: 学号: 目录实验一 分治与递归 ???1 1、基本递归算法???1 2、棋盘覆盖问题...

  • 计算机算法设计实验报告

    计算机算法设计实验报告_IT/计算机_专业资料。课程名: 课程名:计算机算法设计与分析 实验一 分治法的应用——快速排序 分治法的应用——快速排序 —— 一 实验目的...

  • 计算机算法设计与分析实验指导书

    分支限界法 32页 2财富值 第七章 分支限界法 28页 1财富值 算法设计与分析实验报告手... 54页 1财富值 计算机算法设计与分析【王... 90页 1财富值...

  • 计算机算法设计与分析实验二

    洛阳师范学院信息技术学院 软件实验报告专业:网络工程(物联网方向)课程:计算机算法设计与分析 学号:111124092 姓名:朱玉付班级:11 级网工物联 实验名称 实验类型 ...

  • 计算机算法设计与分析 哈夫曼编码 实验报告

    组 计算机算法设计与分析 课 教师评定 学号 2007102×× 姓名 121 实验日期 哈夫曼编码问题 1、 、 实验目的: 实验目的:根据最优二叉树构造哈夫曼编码 利用哈...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email