算法设计与分析003_qq
算法设计与分析003
(一)最长公共子序列
1.一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后得到的结果。
给定串中任意个连续的字符组成的子序列称为该串的子串。
2.动态规划的基本思想就是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。
3.用c[i,j]表示Xi 和 Yj 的LCS的长度
递归公式为:
c[i][j]=0 if(i== 0||j==0)
c[i][j]=c[i-1][j-1]+1 if(i>0&&j>0&&x ==y)
c[i][j] = max{c[i-1][j],c[i][j-1]} if(i>0&&j>0&&x!=y)
代码如下:c++
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[1001], b[1001];
int dp[1001][1001], len1, len2;
void lcs(int i, int j)
{
for(i=1; i<=len1; i++)
{
for(j=1; j<=len2; j++)
{
if(a[i-1] == b[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else if(dp[i-1][j] > dp[i][j-1])
dp[i][j] = dp[i-1][j];
else
dp[i][j] = dp[i][j-1];
}
}
}
void llcs()
{
int i, j, z = 0;
int c[1001];
memset(c, 0, sizeof(c));
i = len1, j = len2;
while(i!=0 && j!=0)
{
if(a[i-1] == b[j-1])
{
c[z++] = a[--i];
j--;
}
else if(dp[i-1][j] < dp[i][j-1])
j--;
else if(dp[i][j-1] <= dp[i-1][j])
i--;
}
for(i=z-1; i>=0; i--)
printf("%%d ", c[i]);
printf("
");
}
void GetArray(int arr1[],int n)//获取输入
{
for(int i=0;i<n-1;i++)
scanf("%%d,",&arr1[i]);
scanf("%%d",&arr1[n-1]);
}
int main()
{
int n,m;
cin>>n>>m;
GetArray(a,n);
GetArray(b,m);
len1=n;
len2=m;
lcs(len1,len2);
cout<<dp[n][m]<<endl;
llcs();
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
运行结果:
(二)电路布线
1.分析题目要求,采用动态规划的算法。这个问题符合最优子结构性质:问题的最优解包含子问题的最优解。
2.重叠子问题性质:子问题之间不独立的同时(这是区分分治算法的关键),少量子问题被重复解决了。子问题之间有联系的同时有些计算重复了,我们可以在计算第一次的时候将结果记录下来,以后再用到的时候,直接取值,不用再去花时间计算。
3.递归公式为: 与i连线的对应点 为n(i)
当i=1的时候:
size[i,j]=0 j<n(i)
size[i,j]=1 j>=n(i)
当i>1的时候:
size[i,j]=size[i-1,j] j<n(i)
size[i,j]=max{size[i-1,j],size[i-1,n(i)-1]+1} j>=n(i)
代码:
#include <iostream>
#include<stdio.h>
using namespace std;
const int N = 10;
void MNS(int C[],int n,int **size);
void Traceback(int C[],int **size,int n,int Net[],int& m);
int main()
{
int c[N+1];
int **size = new int *[N+1];
c[0]=0;
cout<<"下端接线柱取值为:"<<endl;
for(int i=1;i<N;i++)
scanf("%%d,",&c[i]);
scanf("%%d",&c[N]);
for(int i=0; i<=N; i++)
size[i] = new int[N+1];
MNS(c,N,size);
int Net[N],m;
Traceback(c,size,N,Net,m);
cout<<"最大不相交连线分别为:"<<endl;
for(int i=m-1; i>=0; i--)
cout<<Net[i]<<" "<<c[Net[i]]<<endl;
cout<<"最大不相交连线数目为:"<<size[N][N]<<endl;
return 0;
}
void MNS(int C[],int n,int **size)
{
for(int j=0;j<C[1];j++)
size[1][j]=0;
for(int j=C[1]; j<=n; j++)
size[1][j]=1;
for(int i=2; i<n; i++)
{
for(int j=0; j<C[i]; j++)
size[i][j]=size[i-1][j];//当i<c[i]的情形
for(int j=C[i]; j<=n; j++)
//当j>=c[i]时,考虑(i,c[i])是否属于MNS(i,j)的两种情况
size[i][j]=max(size[i-1][j],size[i-1][C[i]-1]+1);
}
size[n][n]=max(size[n-1][n],size[n-1][C[n]-1]+1);
}
void Traceback(int C[],int **size,int n,int Net[],int& m)
{
int j=n;
m=0;
for(int i=n;i>1;i--)
{
if(size[i][j]!=size[i-1][j])//此时,(i,c[i])是最大不相交子集的一条边
{
Net[m++]=i;
j=C[i]-1;//更新扩展连线柱区间
}
}
if(j>=C[1])//处理i=1的情形
Net[m++]=1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
运行结果如图
实验总结:
这两个实验有点难度,在对问题的分析上存在一定的问题,通过百度搜索相关知识,对问题求解有很大的帮助。理解是一件事,将思路转换成代码实现又是另外一件事,目前缺乏的就是编码能力,通过查阅相关资料,以及自己对c、c++的学习,将代码编写出来,实现了应有的功能。以后编码能力需要继续提升。