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

#include
#include
#include 

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("n");
 
}

void GetArray(int arr1[],int n)//获取输入 
{
	for(int i=0;i>n>>m;
	GetArray(a,n);
	GetArray(b,m);
	len1=n;
	len2=m;
	lcs(len1,len2);
	cout< 
运行结果： 
 
（二）电路布线 
1.分析题目要求，采用动态规划的算法。这个问题符合最优子结构性质：问题的最优解包含子问题的最优解。
 2.重叠子问题性质：子问题之间不独立的同时(这是区分分治算法的关键)，少量子问题被重复解决了。子问题之间有联系的同时有些计算重复了，我们可以在计算第一次的时候将结果记录下来，以后再用到的时候，直接取值，不用再去花时间计算。
 3.递归公式为： 与i连线的对应点 为n(i)
 当i=1的时候：
 size[i,j]=0 j size[i,j]=1 j>=n(i)
 当i>1的时候：
 size[i,j]=size[i-1,j] j size[i,j]=max{size[i-1,j],size[i-1,n(i)-1]+1} j>=n(i)
 
代码： 
#include  
#include
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<<"下端接线柱取值为:"<=0; i--)
		cout<=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;
}

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