四川大学_算法分析与设计_左劼

算法分析设计

4星 · 超过85%的资源需积分: 18 152 浏览量更新于2023-03-16 评论 2 收藏 28KB DOCX 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

算法分析 3-1：

题目分析：

要求出 n 个数组成的序列的最长单调递增子序列，假设有数组 a,x.就是将将数组 a 复制

到数组 x,先用排序算法将数组 x 排序，在调用查找最长公共子序列的算法求出数组 a 和数

组

x 中的最长公共子序列，因为数组 x 是单调递增的，所以由此求出来的最长公共子序列就是

题设所求的最长单调递增子序列。题目要求在 O(n*n)的时间内找出 n 个数组成的序列的最

长单调递增子序列,需要用到排序算法，查找最长公共子序列的算法。

具体实现如下：

//计算最长公共子序列长度

void LCSL(int m,int n,int *x,int *y,int c[][N],int b[][N])

{

c[0][0]=0;

int i,j;

for(i=1;i<=m;i++)

c[i][0]=0;

for(i=1;i<=n;i++)

c[0][i]=0;

for(i=1;i<=m;i++)

for(j=1;j<=m;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;

}

cout<<c[m][m]<<endl;

}

//根据 b[i][j]的内容打印 a,x 数组的最长公共子序列

void LCS(int i,int j,int *x,int b[][N])

{

if(i==0||j==0) return;

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

{

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

for(int y=1;y<i;y++)

if(x[y]==x[i])

return;

cout<<x[i]<<" ";

}

else if(b[i][j]==2)

{

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

}

else

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

}

算法实现题 3-5：

题目分析：

刻画最优解的结构：对于序列 Xi(0≤i≤m)和序列 Yj(0≤j≤n)来说，定义 c[i,j]为

Xi 转换成 Yj 的操作序列的最小开销。假定我们已经知道了最后一次执行的操作，此时分情

况讨论问题的最优解结构。

1. 最后一次操作为 copy。此时，根据题目的定义可知 x=y[j]，我们待解决的问题就转化

成了求将 Xi-1 转换为 Yj-1 的最小开销。将 Xi-1 转换为 Yj-1 的最优解一定包含在 Xi 转换为

Yj 的最优解内。用反证法证明：若存在从 Xi-1 到 yj-1 转换的更小的开销，那么用这个更小

的开销来代替 Xi-1 转换为 yj-1 的最优解，这样就会得到一个更小的从 Xi 转换为 Yj 的开销，

与已知的 Xi 转换为 Yj 的最优解矛盾，所以假设不成立。因此，当最后一次操作为 copy 时，

可以定义 c[i,j]=c[i-1,j-1]+cost(copy)。

2. 最后一次操作为 replace。此时，根据题目的定义可知 x≠y[j]。仿照上述分析，可以

得到相同的最优子结构。此时 c[i,j]=c[i-1,j-1]+cost(replace)。

3. 最后一次操作为 delete。根据题意，这时只是将 x 从序列 Xi 中除去，对序列 Yj 没有任

何影响，此时问题的最优子结构的形式为将 Xi-1 转换成 Yj，于是可以得到 c[i,j]=

c[i-1,j]+cost(delete)。

4. 最后一次操作为 insert。根据题意，在进行插入操作时，序列 Xi 无任何变化，序列 Yj

添加一个字符，因此，这时候问题的最优子结构的形式为将 Xi 转换成为 Yj-1，此时

c[i,j]=c[i,j-1]+cost(insert)。

5. 最后一次操作为 twiddle。根据题意，互换操作是针对两个字符进行的，此时有 y[j]

=x[i-1]和 y[j-1]=x。在进行这个操作的时候，需要满足的条件是 i,j≥2。在这种情况下，

问题的最优子结构的形式为 Xi-2 转换为 Yi-2，此时 c[i,j]=c[i-2,j-2]+cost(twiddle)。

6. 最后一次操作为 kill。这种情况比较特殊，由于 kill 操作可以一次删除一个子串，对

所有 i=1..m-1, j=1..n，当 X 被检查到 xi，Y 被生成到 yj 的时候，用一个 kill 操作可以删

除 X 中剩下的元素，用(n-i)个 insert 操作可以插入 Y 中尚未出现的全部元素。这样即可把

X 中的元素全部检查到，并且生成完整的 Y。这种方式把 X 变成 Y 的总开销为 c[j]+cost

(kill)+(n-i) *cost(insert)。对所有 c[j]求这个值，并且和上述忽略 kill 操作的前

提下求出的编辑距离相比，取其中最小值，即求得编辑距离。

考虑一些特殊的情况，当 X 和 Y 为空串时，c[0,0]=0。当 Xi 为一个非空序列 Yj 为空序列时，

可以很明显的看出此时的操作全为 delete，因此有 c[i,0]=i*cost(delete)。当 Xi 为一

剩余14页未读，继续阅读

z932099925

2013-10-24

当做参考还是可以的

scuxia

粉丝: 3
资源: 15

会员权益专享

四川大学_算法分析与设计_左劼

评论3

会员权益专享

最新资源

四川大学_算法分析与设计_左劼

评论3

四川大学左劼算法设计课程报告

四川大学操作系统课程设计高分报告-第四次实验-作业调度系统.doc

算法分析与设计pdf版的课件

四川大学 数据结构与算法分析

csdn四川大学数据结构与算法考点汇总

数据结构与算法 四川大学 括号匹配

四川大学874真题_考研经验|2020四川大学计算机学硕初试第三、总分387分考研经验分享...

四川大学计算机网络2014a

数据结构与算法 游洪跃

四川大学 experiment of digital electronic technology lecture notes

软件开发环境+四川大学

四川大学计算机学院复试 csdn

四川大学大一有python课吗_1. 案例分析内容: 附件 catering_sale提供了某餐饮行业的商业数据,请利用pandas的read_excel读入数据,并用data保存该数据。并实现一下功...

四川大学计算机图形学_第一次作业gasket

四川大学数电实验fpga计数器

为四川大学图书馆设计“以xxx的读书之道”为主题的阅读推广活动

四川大学计算机系统导论半期pdf

csdn四川大学软件学院《离散数学》期末试卷

四川大学 计算机网络

四川大学概率统计期末(b)

会员权益专享

最新资源

四川大学数据结构与算法分析

数据结构与算法四川大学括号匹配

数据结构与算法游洪跃

四川大学计算机网络