WHCSRL 技术网

算法设计与分析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

运行结果:

image.png

(二)电路布线

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

运行结果如图

image.png

实验总结:

这两个实验有点难度,在对问题的分析上存在一定的问题,通过百度搜索相关知识,对问题求解有很大的帮助。理解是一件事,将思路转换成代码实现又是另外一件事,目前缺乏的就是编码能力,通过查阅相关资料,以及自己对c、c++的学习,将代码编写出来,实现了应有的功能。以后编码能力需要继续提升。

推荐阅读