精华内容
下载资源
问答
  • 最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法
  • 题目:如果字符串一的所有字符按其在字符串...分析:求最长公共子序列(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。 完整介绍动态规划将
  • 算法导论》中动态规划的第三个问题是最大子序列 这里的最大子序列的定义是:找出一个序列S3,S3在S1和S2中都出现,且出现的顺序相同,现在找出最长的一个S3。 对于序列A=“ABCBDAB”,B=“BDCABA” 他的一个最大...

    问题1:钢条切割
    问题2:矩阵链乘法

    《算法导论》中动态规划的第三个问题是最大子序列
    这里的最大子序列的定义是:找出一个序列S3,S3在S1和S2中都出现,且出现的顺序相同,现在找出最长的一个S3
    对于序列A=“ABCBDAB”,B=“BDCABA”
    他的一个最大子序列是“BCBA”。
    对于一个序列X=<x1,x2,…xm>,序列Y=<y1,y2…yn>,他们的一个最大子序列Z=<z1,z2,zk>。可以得到如下三个结论

    1. 如果xm=yn,那么有zk=xm=yn。且zk-1是xm-1与yn-1的一个最大子序列
    2. 如果xm!=yn,那么zk !=xm,z是xm-1与y的一个最大子序列
    3. 如果xm!=yn,那么zk !=yn,z是x与yn-1的一个最大子序列

    通过上面三个例子,我们可以推出X,Y最大子序列的递归写法。
    想要知道子序列c[i][j]的长度要经过对不同情况讨论来判断,如若xi=yj 则c[i][j]的长度为c[i-1][j-1]+1,xi,yj添加前一个最大子序列的至末尾。如果xi!=yj则序列长度为c[i-1][j]和c[i][j-1]中较大的那一个。这里增加了对子问题情况的判断,针对不同的情况来选择不同的子问题
    动态规划代码:

    	for (i = 1; i <= n; i++)
    	{
    		for (j = 1; j <= m; j++)
    		{
    			if (A[i-1] == B[j-1])
    			{
    				len[i][j] = len[i - 1][j - 1] + 1;
    				dis[i][j] = 1;
    			}
    			else if (len[i - 1][j] >= len[i][j - 1])
    			{
    				len[i][j] = len[i - 1][j];
    				dis[i][j] = 3;
    			}
    			else
    			{
    				len[i][j] = len[i][j - 1];
    				dis[i][j] = 2;
    			}
    		}
    	}
    

    另外创建数组dis[][]来储存每一次的信息,如果xi=yj则为1,另外两种情况为dis[][]中储存为2,3;
    输出最长子序列的代码:

    void show(int i, int j)
    {
    	if (i == 0 || j == 0)
    		return;
    	if (dis[i][j] == 1)
    	{
    		show(i - 1, j - 1);
    		printf("%c ", A[i-1]);
    	}
    	else if (dis[i][j] == 3)
    	{
    		show(i - 1, j);
    	}
    	else
    	{
    		show(i, j - 1);
    	}
    }
    

    这里可以这样理解,若dis[i][j]=3,代表的是len[i-1][j]>len[i][j-1]所以传给show的参数为(i-1,j),向着子序列更长的递归
    完整代码:

    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<string.h>
    int len[100][100];
    int dis[100][100]; //1代表两个都是,2代表行是左,3代表列是上
    char A[100] = "ABCBDAB";
    char B[100] = "BDCABA";
    void show(int, int);
    int main()
    {
    	int n = strlen(A);
    	int m = strlen(B);
    	printf("%d  %d\n", n, m);
    	int i, j, k;
    	for (i = 0; i <= n; i++)
    		len[i][0] = 0;
    	for (i = 0; i <= m; i++)
    		len[0][i] = 0;
    	for (i = 1; i <= n; i++)
    	{
    		for (j = 1; j <= m; j++)
    		{
    			if (A[i-1] == B[j-1])
    			{
    				len[i][j] = len[i - 1][j - 1] + 1;
    				dis[i][j] = 1;
    			}
    			else if (len[i - 1][j] >= len[i][j - 1])
    			{
    				len[i][j] = len[i - 1][j];
    				dis[i][j] = 3;
    			}
    			else
    			{
    				len[i][j] = len[i][j - 1];
    				dis[i][j] = 2;
    			}
    		}
    	}
    	printf("最大子序列长度:%d  ", len[n][m]);
    	for (i = 0; i <= n; i++)
    	{
    		for (j = 0; j <= m; j++)
    		{
    			printf("%d ", dis[i][j]);
    		}
    		puts("");
    	}
    	puts("子序列为:");
    	show(n, m);
    }
    void show(int i, int j)
    {
    	if (i == 0 || j == 0)
    		return;
    	if (dis[i][j] == 1)
    	{
    		show(i - 1, j - 1);
    		printf("%c ", A[i-1]);
    	}
    	else if (dis[i][j] == 3)
    	{
    		show(i - 1, j);
    	}
    	else
    	{
    		show(i, j - 1);
    	}
    }
    

    测试结果:
    在这里插入图片描述

    总结

    有人认为动态规划的名字十分具有迷惑性,他可以等同于记忆化搜索。可见动态规划中储存的作用十分的重要,储存可以避免子问题的重复计算,大大地升程序运行的速度。

    展开全文
  • C语言最长公共子序列问题的算法实现。LCS问题,没有太多的描述语言了,这个资源很简单的。
  • 可以根据里面代码修改具体输出,实现过程根据《算法导论》
  • 利用动态规划的思想,通过设置一个临时数组t[][],其中t[i][j]表示,以Str1[i]作为末尾和以Str[2]作为末尾的最长公共子序列或者子串的长度。 算法步骤: (1)将输入的两个字符串分别存在数组a[]和b[]中,同时设置两...

    核心思想:
    利用动态规划的思想,通过设置一个临时数组t[][],其中t[i][j]表示,以Str1[i]作为末尾和以Str[2]作为末尾的最长公共子序列或者子串的长度。

    算法步骤:
    (1)将输入的两个字符串分别存在数组a[]和b[]中,同时设置两个临时数组t1[][]和t2[][],第一个t1[i][j]表示a[]数组前i-1个字符串和b[]数组前j-1个字符串的最大公共子序列;第二个t2[i][j]表示a[]数组前i-1个字符串和b[]数组前j-1个字符串的最大公共子串;
    (2)循坏遍历两个字符串的所有字符,当遍历到第一个字符串的第i个字符,第二个字符串的第j个字符时:
    对于最长公共子序列:
    若a[i]=b[j],则t1[i][j]=t1[i-1][j-1]+1;
    若a[i]!=b[j],则t1[i][j]=Max{a[k][j],a[i][m]}
    对于最长公共子串:
    若a[i]=b[j],则t2[i][j]=t2[i-1][j-1]+1;
    若a[i]!=b[j],则t2[i][j]=0。
    (3)t1[][]数组最右下角的便是最长公共子序列的长度;而t2[][]数组中最大的元素才是最长公共子串的长度。

    注意:
    子序列:从字符串中顺序地取出字符组成的字符串;
    子串:从字符串中连续地取出字符组成的字符串。

    实例以及代码

    //定义全局变量
    int t1[20][20]={0},t2[20][20]={0};
    char a[20],l1=1,b[20],l2=1;
    
    //存储输入,初始化临时二维数组
    void Input(){
    	char ch;
    	printf("请输入两个字符串:");
    	ch=getchar();
    	while(ch!=' ')
    	{
    		a[l1++]=ch;
    		ch=getchar();
    	}
    	ch=getchar();
    	while(ch!='\n')
    	{
    		b[l2++]=ch;
    		ch=getchar();
    	}
    }
    
    //对于a[i]是否等于b[j]的处理
    void LCDSubsequence(){  //最长公共子序列
    	int i,j,max,k;
    	for(i=1;i<l1;i++)
    		for(j=1;j<l2;j++)
    		{
    			if(a[i]==b[j])
    				t1[i][j]=t1[i-1][j-1]+1;
    			else
    			{
    				if(t[i-1][j]>t[i][j-1])
    				  t[i][j]=t[i-1][j];
    	  	  	  else
    	  	  	      t[i][j]=t[i][j-1];
    			}
    		}
    }
    
    //对于a[i]是否等于b[j]的处理
    void LCCSubsequence(){   //最长公共子串
    	int i,j;
    	for(i=1;i<l1;i++)
    		for(j=1;j<l2;j++)
    		{
    			if(a[i]==b[j])
    				t2[i][j]=t2[i-1][j-1]+1;
    			else
    			{
    				t2[i][j]=0;
    			}
    		}
    }
    
    
    //分别输出
    void Output(){
    	printf("最长公共子序列为:");
    	printf("%d\n",t1[l1-1][l2-1]);
    	int i,j,max=0;
    	printf("最长公共连续序列为:");
        for(i=1;i<l1;i++)
    		for(j=1;j<l2;j++)
    			if(t2[i][j]>max)
    				max=t2[i][j];
    	printf("%d",max);
    }
    
    int main(){
    	Input();
    	LCDSubsequence();
    	LCCSubsequence();
    	Output();
    	return 0;
    }
    

    运行结果:
    在这里插入图片描述

    展开全文
  • 思路: 有两个字符数组a,b 分为三种情况: 比较a,b数组当前长度的最后一个字符...不相等,把a数组的最后一个字符去掉的最长公共子序列大于把b数组的最后一个字符去掉的最长公共子序列 即:当lsc[i-1][j]&g...

    思路:
    有两个字符数组a,b
    分为三种情况:
    比较a,b数组当前长度的最后一个字符

    1. 相等时, lsc值等于前一段值加1
      即:当a[i-1]==b[j-1]时(因为i,j是从1开始,所以是a[i-1],b[j-1]),lsc[i][j]=lsc[i-1][j-1]+1
    2. 不相等,把a数组的最后一个字符去掉的最长公共子序列大于把b数组的最后一个字符去掉的最长公共子序列
      即:当lsc[i-1][j]>=lsc[i][j-1]时,lsc[i][j]=lsc[i-1][j]
    3. 不相等,把b数组的最后一个字符去掉的最长公共子序列大于把a数组的最后一个字符去掉的最长公共子序列
      即:当lsc[i-1][j]<lsc[i][j-1]时,lsc[i][j]=lsc[i][j-1]

    代码:

    #include <stdio.h>
    
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    void LSCLength(char a[],char b[],int c[11][10],int lsc[11][10],int la,int lb)
    {
    	for(int i=0;i<=la;i++)	lsc[0][i]=0;
    	for(int i=0;i<=lb;i++)	lsc[i][0]=0;
    	for(int i=1;i<=la;i++)
    	{
    		for(int j=1;j<=lb;j++){
    			if(a[i-1]==b[j-1])
    			{
    				lsc[i][j]=lsc[i-1][j-1]+1;
    				c[i][j]=1;
    			}
    			else if(lsc[i-1][j]>=lsc[i][j-1])
    			{
    				lsc[i][j]=lsc[i-1][j];
    				c[i][j]=2;
    			}
    			else{
    				lsc[i][j]=lsc[i][j-1];
    				c[i][j]=3;
    			}
    		}
    	}
    
    	
    }
    void LSC(int i,int j,char a[],int c[11][10]) 
    {
    	if(i==0 || j==0)	return;
    	if(c[i][j]==1)
    	{
    		LSC(i-1,j-1,a,c);
    		printf("%3c  ",a[i-1]);
    	}
    	else if(c[i][j]==2)
    	{
    		LSC(i-1,j,a,c);
    	}
    	else
    	{
    		LSC(i,j-1,a,c);
    	}
    	
    }
    int main(int argc, char** argv) {
    	char a[10]={'d','i','d','a','c','t','i','c','a','l'};
    	char b[9]={'a','d','v','a','n','t','a','g','e'};
    	int c[11][10]={0};
    	int lsc[11][10]={0};
    	LSCLength(a,b,c,lsc,10,9);
    	for(int i=0;i<=10;i++)
    	{
    		for(int j=0;j<=9;j++)
    		{
    			printf("%d  ",lsc[i][j]);
    		}
    		printf("\n");
    	}
    	printf("长度:%d\n比较情况\n",lsc[10][9]);
    	
    	for(int i = 0;i<11;i++){
    		for(int j = 0;j<10;j++){
    			printf("%3d",c[i][j]);
    		}
    		printf("\n");
    	}
    	LSC(10,9,a,c);
    	return 0;
    } 
    

    运行结果:
    在这里插入图片描述

    展开全文
  • 最长公共子序列问题: 下面的简单问题说明了动态规划的基本原理。在字母表一∑上,分别给出两个长度为n和m的字符串A和B,确定在A和B中最长公共子序列的长度。这里,A = a₁a₂...an。的子序列是一个形式为a₁ka₂k....

    最长公共子序列问题:

            下面的简单问题说明了动态规划的基本原理。在字母表一∑上,分别给出两个长度为n和m的字符串A和B,确定在A和B中最长公共子序列的长度。这里,A = a₁a₂...an。的子序列是一个形式为a₁ka₂k...aik的字符串,其中每个i都在1和n之间,并且1<i₁< i₂<…<ik≤n。例如,如果∑= {x, y,z},A = zxyxyz和B= xyyzx,那么xzy 同时是A和B的长度为3的子序列。然而,它不是A和B最长的公共子序列,因为字符串xyyz也是A和B公共的子序列,由于这两个字符串没有比4更长的公共子序列,因此,A和B的最长的公共子序列的长度是4

            解决这个问题的-一种途径是蛮力搜索的方法:列举A所有的2^n个子序列,对于每一个子序列在O( m)时间内来确定它是否也是B的子序列。很明显,此算法的时间复杂性是O时间复杂度(m2²),是指数复杂性的。

            为了使用动态规划技术,我们首先寻找--个求最长公共子序列长度的递推公式,令A = a₁a₂...an和B= b₁b₂...bm,令L[i,j]表示a₁a₂...ai和b₁b₂...bj的最长公共子序列的长度。

            注意、i和j可能是0,此时,a₁a₂...ai和b₁b₂...bj中的一个或同时可能为空字符串。即如果i =0或 j =o,那么L[i,j]=0。很容易证明下面的观察结论。

            如果i和j都大于0,那么

            1.若ai=bj, L[i,j]= L[ i-1,j - 1]+1;

    ·        2.若ai≠bj, L[i,j ]= max{L[i,j - 1],L[ i- 1,j] }。

    最长公共子序列算法伪码:

     

     最长公共子序列公式:

     

     最长公共子序列解题思想:

    
    A的长度为5 B的长度为7
    A字符串:zxyyz
    B字符串:zyxzyxz
        0   z   y   x   z   y   x   z
    0   0   0   0   0   0   0   0   0
    z   0   0   0   0   0   0   0   0
    x   0   0   0   0   0   0   0   0
    y   0   0   0   0   0   0   0   0
    y   0   0   0   0   0   0   0   0
    z   0   0   0   0   0   0   0   0
    z与z相遇即相等,将左上角+1,并将其余的比较大小,1>0,所以将其他的值变为1,即得到下图↓
        0   z   y   x   z   y   x   z
    0   0   0   0   0   0   0   0   0
    z   0   1   1   1   1   1   1   1
    x   0   1   1   1   1   1   1   1
    y   0   1   1   1   1   1   1   1
    y   0   1   1   1   1   1   1   1
    z   0   1   1   1   1   1   1   1
    x与x相遇即相等,y与y相遇即相等,将左上角+1得2,并将其余的比较大小,2>1,所以将其他的值变为2,即得到下图↓
        0   z   y   x   z   y   x   z
    0   0   0   0   0   0   0   0   0
    z   0   1   1   1   1   1   1   1
    x   0   1   1   2   2   2   2   2
    y   0   1   2   2   2   2   2   2
    y   0   1   2   2   2   2   2   2
    z   0   1   2   2   2   2   2   2
    z与z相遇即相等,y与y相遇即相等,将左上角+1得3,并将其余的比较大小,3>2,所以将其他的值变为3,即得到下图↓
        0   z   y   x   z   y   x   z
    0   0   0   0   0   0   0   0   0
    z   0   1   1   1   1   1   1   1
    x   0   1   1   2   2   2   2   2
    y   0   1   2   2   2   3   3   3
    y   0   1   2   2   2   3   3   3
    z   0   1   2   2   3   3   3   3
    z与z相遇即相等,将左上角+1得4,没剩余得值了,所以退出程序不用比较,即得到下图↓
        0   z   y   x   z   y   x   z
    0   0   0   0   0   0   0   0   0
    z   0   1   1   1   1   1   1   1
    x   0   1   1   2   2   2   2   2
    y   0   1   2   2   2   3   3   3
    y   0   1   2   2   2   3   3   3
    z   0   1   2   2   3   3   3   4
    

    核心代码就那几行:

    for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                if(a[i-1]==b[j-1])
                    c[i][j]=c[i-1][j-1]+1;
                else
                    c[i][j]=max(c[i][j-1],c[i-1][j]);
            }
        }

    将数据一步一步的带入代码就可以理解了!

     代码实现:

    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <string.h>
    void lcs();
    int max(int a,int b);
    
    int main()
    {
        lcs();
        return 0;
    }
    int max(int a,int b)
    {
        return a>b?a:b;
    }
    void lcs()
    {
        int n,m,i,j;
        char *a,*b;
        printf("分别输入A和B的长度:");
        scanf("%d%d",&n,&m);
    
        a=(char *)malloc(n*sizeof(char));
        b=(char *)malloc(n*sizeof(char));
        int c[n+1][m+1];
    
        printf("输入A字符串:");
            scanf("%s",a);
        getchar();
        printf("输入B字符串:");
            scanf("%s",b);
        for(i=0;i<=n;i++)c[i][0]=0;
        for(j=0;j<=m;j++)c[0][j]=0;
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                if(a[i-1]==b[j-1])
                    c[i][j]=c[i-1][j-1]+1;
                else
                    c[i][j]=max(c[i][j-1],c[i-1][j]);
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                printf("%d  ",c[i][j]);
            }
            printf("\n");
        }
        printf("\n%d\n",c[n][m]);
        printf("按任意键继续\n");
    }

    结果实现: 

     

    希望这对你有帮助! 

     

    展开全文
  • 这位大佬写的对理解DP也很有...字符串2:ABCBDAB则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA二,算法求解这是一个动态规划的题目。对于可用动态规划求解的问题,一般有两个特征:①最优子结构;...
  • 主要介绍了C语言实现最长递增子序列问题的解决方法,采用递归的方法解决该问题,是非常经典的一类算法,需要的朋友可以参考下
  • 最长公共子序列C语言) 问题描述 首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么是子序列呢?即一个给定的序列的子序列,就是将给定...
  • 最长公共子序列 -- C语言

    千次阅读 2020-03-09 14:28:11
    给定两个字符串text1 和text2,返回这两个字符串的最长公共子序列。 一个字符串的子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新...
  • C语言动态规划实现最长公共子序列

    千次阅读 2020-05-30 15:02:52
    ①计算最长公共子序列长度的动态规划算法LscLength以数组ar,br作为输入。输出两个数组c和b。其中,c[i][j]存储ar和br的最长公共子序列的长度,b[i][j]记录c[i][j]的值是由哪一个子问题的解得到的,这在构造最长...
  • 定义:两个字符串共有的最长的子序列(可不连续),最长公共字符串(Longest CommonSubstring)是两个字符串共有的最长的连续字符串。方法:穷举法,动态规划动态规划法的简介:《后补》代码思路:《后补》Python 代码:...
  • 一、求最长公共子序列 1、问题描述: 从一个给定的串中删去(不一定连续地删去)0个或0个以上的字符,剩下地字符按原来顺序组成的串。例如:“ ”,“a”,“xb”,“aaa”,“bbb”,“xabb”,“xaaabbb”都是串...
  • 一.前言 如上 ...//求最长公共子序列的长度 //#include<string.h> int main(){ int max(int a,int b); int i;//循环变量 int j;//循环变量 int a[7][8]; char s2[7];//B char s1[8];//A
  • 最长公共子序列C语言

    千次阅读 2017-08-03 23:58:57
    这个系列的内容均出自《算法设计与问题求解》,有兴趣的可以去看原版书。 输出: 4C(x,y) = 0 当 i=0, j=0时 C(i-1,j-1)+1 当i,j>0,Xi=Yi时 max{C(i-1, j), C(i, j-1)} 当i,j>0, Xi!=Yj时#include #include...
  • 文章目录动态规划(dynamic programming)DP四步骤DP基本要素最长公共子序列(longest common sequence)如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左...
  • 动态规划最长公共子序列C语言

    千次阅读 2018-09-08 12:59:43
    # include "stdafx.h" # include # define m 7 # define n 6 int c [ m ...注意看算法导论书上那个表,x,y数组里的元素都是从1开始的,前面的0是没有元素的。否则运行就会出错。
  • 1、基本概念一个给定序列的子序列就是该给定序列中去掉零个或者多个元素的序列。形式化来讲就是:给定一个序列X={x1,x2,……,xm},另外一个序列Z={z1、z2、……,zk},如果存在X的一个严格递增小标序列1,i2……...
  • 算法设计-动态规划法解最长公共子序列问题 C代码

    千次阅读 多人点赞 2019-03-15 09:01:37
    主要功能:动态规划法解最长公共子序列问题 #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;string.h&amp;gt; char a[101],b[101]; char num[102][102];//记录中间结果的数组 //动态规划采用...
  • 动态规划C语言实现之最长公共子序列(LCS)

    万次阅读 多人点赞 2018-02-06 23:09:28
    我的机器学习教程「美团」算法工程师带你入门机器学习 已经开始更新了,欢迎大家订阅~ 任何关于算法、编程、AI行业知识或博客内容的问题,可以随时扫码关注公众号「图灵的猫」,加入”学习小组“,沙雕博主在线答疑...
  • 最长公共子序列问题(LCS/c++) 两个序列,求解两个序列中最长公共的子序列
  • 最长公共子序列问题C语言 #include<stdio.h> #include<stdlib.h> #include<string.h> int num[50][50]={0}; int b[50][50]={0}; int lcsLength(char *x,char *y,int xLen,int yLen); void LCS(int...
  • 主要功能:递归法解最长公共子序列问题 #include&amp;amp;lt;stdio.h&amp;amp;gt; #include&amp;amp;lt;string.h&amp;amp;gt; /* 递归思路: 当数组a和b对应位置字符相同时,则直接求解下一个位置;...
  • 程序员编程艺术第十一章:最长公共子序列(LCS)问题0、前言程序员编程艺术系列重新开始创作了(前十章,请参考程序员编程艺术第一~十章集锦与总结)。回顾之前的前十章,有些代码是值得商榷的,因当时的代码只顾阐述...
  • 刻画最长公共子序列的特征 LCSLCS的最优子结构:令X=⟨x1,x2…,xm⟩X=⟨x1,x2…,xm⟩和Y=⟨y1,y2,…,yn⟩Y=⟨y1,y2,…,yn⟩为两个序列,Z=⟨z1,z2,…,zk⟩Z=⟨z1,z2,…,zk⟩为XX和YY的任意LCSLCS。 1.如果xm=ynxm=...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,708
精华内容 1,083
关键字:

最长公共子序列c语言算法

c语言 订阅