【演算法設計與分析】 最長公共子序列（動態規劃）
【問題描述】
使用動態規劃演算法解最長公共子序列問題，具體來說就是，依據其遞回式自底向上的方式依次計算得到每個子問題的最優值，
【輸入形式】
在螢屏上輸入兩個序列X和Y，序列各元素數間都以一個空格分隔，
【輸出形式】
序列Xi = {x1, …, xi}和序列Yj = {y1, …, yj}的最長公共子序列的長度，序列X和Y的其中一個最長公共子序列，也就是當序列X和Y有多個最長公共子序列時，只輸出其中的一個，這個輸出的最長公共子序列選取的方法是：當xi不等于yj時，而c[i-1,j]==c[i,j-1]，那么，c[i,j]是由c[i-1,j]得到的，其中c[i,j]中存放的是：序列Xi = {x1, …, xi}和序列Yj = {y1, …, yj}的最長公共子序列的長度，
當最長公共子序列為空時，輸出最長公共子序列長度為0，最長公共子序列為：None，
【樣例1輸入】
A B C B D A B
B D C A B A
【樣例1輸出】
4
BCBA
【樣例1說明】
輸入：第一行輸入序列X的各元素，第二行輸入序列Y的各元素，元素間以空格分隔，
輸出：序列X和Y的最長公共子序列的長度為4，其中一個最長公共子序列為：BCBA，
【樣例2輸入】
A B C D
E F G H
【樣例2輸出】
0
None
【樣例2說明】
輸入：第一行輸入序列X的各元素，第二行輸入序列Y的各元素，元素間以空格分隔，
輸出：序列X和Y的最長公共子序列為空，最長公共子序列的長度為0，最長公共子序列為：None，
【題解代碼】
C++代碼：
#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>
using namespace std;
char x[100],y[100];
int m,n,c[100][100],b[100][100];//c[i][j]存盤xi和yj的最長公共子序列的長度，b[i][j]記錄c[i][j]的值是由哪個子問題的解得到的
void LCSLength(int m,int n,char x[],char y[],int c[][100],int b[][100])//計算最優值
{
for(int i=0;i<=m;i++)
c[i][0]=0;
for(int j=0;j<=n;j++)
c[0][j]=0;
for(int i=1;i<=m;i++)
for(int 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 LCS(int i,int j,char x[],int b[][100])//輸出最長公共子序列
{
if(i==0||j==0)
return;
if(b[i][j]==1)
{
LCS(i-1,j-1,x,b);
cout<<x[i];
}
else if(b[i][j]==2)
LCS(i-1,j,x,b);
else
LCS(i,j-1,x,b);
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
stringstream scin;
string s;
getline(cin,s);
scin<<s;
int pos=0;
char t;
while(scin>>t)
x[++pos]=t;
m=pos;
scin.clear();
getline(cin,s);
scin<<s;
pos=0;
while(scin>>t)
y[++pos]=t;
n=pos;
LCSLength(m,n,x,y,c,b);//計算最優值
cout<<c[m][n]<<endl;
if(c[m][n]==0)
cout<<"None"<<endl;
else
LCS(m,n,x,b);//輸出最長公共子序列
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/282137.html
標籤：其他