『壹』 動態規劃 最長公共子串思想(c語言)
最長公共子串問題：一個給定序列的子序列是在該序列中刪去若干元素後得到的序列。給定兩個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。最長公共子串就是求給定兩個序列的一個最長公共子序列。例如，X=「ABCBDAB」，Y=「BCDB」是X的一個子序列。
問題分析：
給定兩個序列A和B，稱序列Z是A和B的公共子序列，是指Z同是A和B的子序列。問題要求已知兩序列A和B的最長公共子序列。如採用列舉A的所有子序列，並一一檢查其是否又是B的子序列，並隨時記錄所發現的子序列，最終求出最長公共子序列。這種方法因耗時太多而不可取。
考慮最長公共子序列問題如何分解成子問題，設A=「a0，a1，…，am-1」，B=「b0，b1，…，bm-1」，並Z=「z0，z1，…，zk-1」為它們的最長公共子序列。不難證明有以下性質：
（1） 如果am-1=bn-1，則zk-1=am-1=bn-1，且「z0，z1，…，zk-2」是「a0，a1，…，am-2」和「b0，b1，…，bn-2」的一個最長公共子序列；
（2） 如果am-1!=bn-1，則若zk-1!=am-1，蘊涵「z0，z1，…，zk-1」是「a0，a1，…，am-2」和「b0，b1，…，bn-1」的一個最長公共子序列；
（3） 如果am-1!=bn-1，則若zk-1!=bn-1，蘊涵「z0，z1，…，zk-1」是「a0，a1，…，am-1」和「b0，b1，…，bn-2」的一個最長公共子序列。
這樣，在找A和B的公共子序列時，如有am-1=bn-1，則進一步解決一個子問題，找「a0，a1，…，am-2」和「b0，b1，…，bm-2」的一個 最長公共子序列；如果am-1!=bn-1，則要解決兩個子問題，找出「a0，a1，…，am-2」和「b0，b1，…，bn-1」的一個最長公共子序列 和找出「a0，a1，…，am-1」和「b0，b1，…，bn-2」的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。
為了節約重復求相同子問題的時間，引入一個數組，不管它們是否對最終解有用，把所有子問題的解存於該數組中，這就是動態規劃法所採用的基本方法，具體說明如下。
定義c[i][j]為序列「a0，a1，…，ai-2」和「b0，b1，…，bj-1」的最長公共子序列的長度，計算c[i][j]可遞歸地表述如下：
（1）c[i][j] = 0 如果i=0或j=0；
（2）c[i][j] = c[i-1][j-1]+1 如果i,j>0，且a[i-1] = b[j-1]；
（3）c[i][j] = max{c[i][j-1], c[i-1][j]} 如果i,j>0，且a[i-1] != b[j-1]。
按此算式可寫出計算兩個序列的最長公共子序列的長度函數。由於c[i][j]的產生僅依賴於c[i-1][j-1]、c[i-1][j]和c[i][j-1]，故可以從c[m][n]開始，跟蹤c[i][j]的產生過程，逆向構造出最長公共子序列。
本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/sharpdew/archive/2006/05/30/763180.aspx
『貳』 C語言求最長子序列
下面是你的代碼修改過後的結果，改過的地方都有注釋，另有測試樣例。
#include <stdio.h>
/*
5
5
-2 5 4 -7 3
最長子序列：9
4
-2 -3 8 -7
最長子序列：8
3
-2 -2 7
最長子序列：7
2
-1 5
最長子序列：5
1
-2
最長子序列：0
Process returned 0 (0x0) execution time : 30.999 s
Press any key to continue.
*/
int main() {
int count, i, k, a[100] = {0}, b[10000] = {0}, n, num, max = 0, q, m, j;
scanf("%d", &n);
for (count = 0; count < n; count++) {
scanf("%d", &num);
for (i = 0; i < num; i++) scanf("%d", &a[i]);
k = 0;
for (i = 0; i < num; i++)
for (q = 1; q < num + 1; q++) {
for (m = i; (m < i + q) && (m < num); m++) //在這里再加一個判斷條件(m < num)，
b[k] += a[m];
k++;
}
j = k - 1;
max = 0; //如果全部都是負數的話，結果應該是0，即一個都不選
for (; j >= 0; j--)
if (max < b[j]) max = b[j];
printf("最長子序列：%d\n", max);
max = 0;
for (i = 0; i < 10000; i++) b[i] = 0;
}
return 0;
}
『叄』 C語言 最長的連續的公共子序列
#include<stdio.h>
#define M 7
#define N 7
int c[M][N];
int b[M][N];
int lcsLength(char x[],char y[])
{
int m=M-1;
int n=N-1;
int i,j;
for(i=0;i<M;i++)
c[i][0]=0;
for(j=0;j<N;j++)
c[0][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(x[i]==x[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
return c[m][n];
}
void lcs(int i,int j,char x[],int b[M][N])
{
if(i==0||j==0)
return;
if(b[i][j]==1)
{
lcs(i-1,j-1,x,b);
printf("%-c,%d\t",x[i],i);
}
else if(b[i][j]==2)
lcs(i-1,j,x,b);
else
lcs(i,j-1,x,b);
}
void main()
{
char x[]={'0','A','B','C','B','D','A'};
char y[]={'0','B','H','C','A','B','A'};
int i,j;
printf("%d\n",lcsLength(x,y));
printf("\n");
lcs(M-1,N-1,x,b);
}
『肆』 C語言 最長公共子串
首先指出樓主的錯誤
最長的公共子字元串 應該改成 最長的連續公共子字元串
下面是符合樓主要求的參考代碼
//作者:hacker
//時間:9.12.2006
#include <stdio.h>
#include <string.h>
void main()
{
char* x="aabcdababce";
char* y="12abcabcdace";
int m = strlen(x);
int n = strlen(y);
int i, j, k, l;
int maxlength = 0;
int start = 0;
int count = 0;//用來判斷是否匹配的變數
for (i=1;i<=n;i++)//匹配長度的循環
for (j=0;j<n-i+1;j++)//y的起始位置的循環
for (k=0;k<m-i+1;k++)//x的起始位置的循環
{
count = 0;
for (l=0;l<i;l++)//判斷是否匹配,代碼可以優化
if (y[j+l] == x[k+l])
count++;
if (count==i&&i>maxlength)
{
maxlength = i;//記錄最大長度
start = j;//記錄最大長度的起起位置
}
}
//作者:hacker
//時間:9.12.2006
#include <stdio.h>
#include <string.h>
void main()
{
char* x="aabcdababce";
char* y="12abcabcdace";
int m = strlen(x);
int n = strlen(y);
int i, j, k, l;
int maxlength = 0;
int start = 0;
int count = 0;//用來判斷是否匹配的變數
for (i=1;i<=n;i++)//匹配長度的循環
for (j=0;j<n-i;j++)//y的起始位置的循環
for (k=0;k<m-i;k++)//x的起始位置的循環
{
count = 0;
for (l=0;l<i;l++)//判斷是否匹配,代碼可以優化
if (y[j+l] == x[k+l])
count++;
if (count==i&&i>maxlength)
{
maxlength = i;//記錄最大長度
start = j;//記錄最大長度的起起位置
}
}
if (maxlength==0)
printf("No Answer");
else
for (i=0;i<maxlength;i++)
printf("%c",y[start+i]);
}
}
下面是真正的最長公共子串的動態規劃演算法
//作者:hacker
//時間:9.12.2006
#include <stdio.h>
#include <string.h>
int b[50][50];
int c[50][50];
void lcs(x,m,y,n)
char *x;
int m;
char *y;
int n;
{
int i;
int j;
for (i=1;i<=m;i++) c[i][0] = 0;
for (i=1;i<=n;i++) c[0][i] = 0;
c[0][0] = 0;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
{
if (x[i-1] == y[j-1])
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else
if (c[i-1][j] > c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
void show(i,j,x)
int i;
int j;
char* x;
{
if (i==0||j==0)
return;
if (b[i][j]==1)
{
show(i-1,j-1,x);
printf("%c",x[i-1]);
}
else
if (b[i][j]==2)
show(i-1,j,x);
else
show(i,j-1,x);
}
void main()
{
char* x="aabcdababce";
char* y="12abcabcdace";
int m = strlen(x);
int n = strlen(y);
lcs(x,m,y,n);
show(m,n,x);
}
『伍』 C語言LCIS（最長公共上升子序列）（DP）如何列印解
用一個解向量存儲解啊，思路如下
function(..., char v[]) /*v用於存儲最優解的*/
{
......
if(當前解更優){
當前解為更優解;
更新向量v; /*最好附添加一個結束符*/
}
......
}
主函數中輸出解向量即可。
『陸』 求問c語言最長公共子序列代碼哪裡錯了！！！ 搞了好久，頭暈了都。 感覺是對的，就是不行。。。
樓主你好。
#include<stdio.h>
void LCSLength(int m,int n,char *x,char *y,int c[8][7],int b[8][7])
{
int i,j;
//下面兩行不怎麼需要，因為已經初始化為0了
for(i=0;i<m;i++) c[i][0]=0;//注意應該是從0到m-1
for(i=0;i<n;i++) c[0][i]=0;
for(i=1;i<m;i++){//這里注意應該是從1到m-1
for(j=1;j<n;j++){
if(x[i]==y[j]){
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}else if(c[i-1][j]>=c[i][j-1]){
c[i][j]=c[i-1][j];
b[i][j]=2;
}else {
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
}
void printMatrix(int matrix[8][7]){
int i,j;
for(i=0;i<8;i++){
for(j=0;j<7;j++){
printf("%d ",matrix[i][j]);
}
printf("\n");
}
}
void LCS(int i,int j,char *x,int b[8][7] )
{
if(i==0||j==0) return;
if(b[i][j]==1){
LCS(i-1,j-1,x,b);
printf("%c\n",x[i]);
}else if(b[i][j]==2){//這里注意是==，不是=
LCS(i-1,j,x,b);
}else{
LCS(i,j-1,x,b);
}
}
int main()
{
int c[8][7]={{0}};
int b[8][7]={{0}};
char X[8]={' ','A','B','C','B','D','A','B'};
char Y[7]={' ','B','D','C','A','B','A'};
LCSLength(8,7,X,Y,c,b);
printf("Matrix c\n");
printMatrix(c);
printf("Matrix b\n");
printMatrix(b);
printf("最大公共子序列長度為%d\n",c[7][6]);
LCS(7,6,X,b);
return 1;
}
你運行一下我的代碼，沒問題的。代碼中出現的問題我以注釋的形式寫出來了。
不過勸告樓主，以後寫代碼一定要多寫一些注釋。因為一般的程序員都能寫出機器能讀懂的代碼，而高級程序員才能寫出人也能讀懂的代碼。寫注釋很重要，顯示出代碼的思路。否則思路不清晰的高深代碼，一開始只有原作者和上帝能懂，過一段時間就只有上帝能懂了。
如果還有問題可以再問。
『柒』 求最長公共子序列的c語言代碼
？？？
『捌』 C語言求兩字元序列的最長公共字元子序列，這個代碼哪錯了
大哥，剛開始看我以為你是個新手，仔細看，回調都敢用...
問題太多了， main函數里定義函數...
知道往函數里傳遞兩個字元串長度，怎麼不把兩個字元串傳里？
然後返回值是int 卻想返回個二維數組..傳值麻煩乾脆全定義成全局變數多好 還有就是遞歸能不用就最好不用，一般遞歸都可以用 循環代替，遞歸太占棧
『玖』 求一個最長公共自序列的程序，C語言的，拜託了
#include<stdio.h>
void LCSLength(int m,int n,char *x,char *y,int c[8][7],int b[8][7])
{
int i,j;
for(i=0;i<m;i++) c[i][0]=0;
for(i=0;i<n;i++) c[0][i]=0;
for(i=1;i<m;i++){
for(j=1;j<n;j++){
if(x[i]==y[j]){
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}else if(c[i-1][j]>=c[i][j-1]){
c[i][j]=c[i-1][j];
b[i][j]=2;
}else {
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
}
void printMatrix(int matrix[8][7]){
int i,j;
for(i=0;i<8;i++){
for(j=0;j<7;j++){
printf("%d ",matrix[i][j]);
}
printf("\n");
}
}
void LCS(int i,int j,char *x,int b[8][7] )
{
if(i==0||j==0) return;
if(b[i][j]==1){
LCS(i-1,j-1,x,b);
printf("%c\n",x[i]);
}else if(b[i][j]==2){
LCS(i-1,j,x,b);
}else{
LCS(i,j-1,x,b);
}
}
int main()
{
int c[8][7]={{0}};
int b[8][7]={{0}};
char X[8]={' ','A','B','C','B','D','A','B'};
char Y[7]={' ','B','D','C','A','B','A'};
LCSLength(8,7,X,Y,c,b);
printf("Matrix c\n");
printMatrix(c);
printf("Matrix b\n");
printMatrix(b);
printf("最大公共子序列長度為%d\n",c[7][6]);
LCS(7,6,X,b);
return 1;
}