算法设计与分析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++的学习，将代码编写出来，实现了应有的功能。以后编码能力需要继续提升。

算法设计与分析003_qq