生活随笔
收集整理的這篇文章主要介紹了
算法设计与分析——动态规划——最长公共子序列
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<bits/stdc++.h>
#define MAXLEN 50
using namespace std
;void LCSlength(int m
,int n
,char *x
,char *y
,int c
[][MAXLEN
],int b
[][MAXLEN
])
{for(int i
=0;i
<=m
;i
++){c
[i
][0]=0;}for(int i
=1;i
<=n
;i
++){c
[0][i
]=0;}for(int i
=1;i
<=m
;i
++){for(int 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 LCS(int i
,int j
,char *x
,int b
[][MAXLEN
])
{if(i
==0||j
==0){return;}if(b
[i
][j
]==1){LCS(i
-1,j
-1,x
,b
);cout
<<x
[i
-1]<<" ";}else if(b
[i
][j
]==2){LCS(i
-1,j
,x
,b
); }else{LCS(i
,j
-1,x
,b
);}}
int main()
{char x
[MAXLEN
] = {"*abcbdab"};char y
[MAXLEN
] = {"*bdcdba"};
int b
[MAXLEN
][MAXLEN
];int c
[MAXLEN
][MAXLEN
];int m
, n
;m
= strlen(x
);n
= strlen(y
);LCSlength(m
,n
,x
,y
,c
,b
);cout
<<"b矩陣是用來存儲這個問題是由那個子問題來解決的"<<endl
; for(int i
=0;i
<=m
;i
++){for(int j
=0;j
<=n
;j
++){cout
<<b
[i
][j
];}cout
<<endl
;} cout
<<"c矩陣用來存儲最長公共子串的長度 "<<endl
;for(int i
=0;i
<=m
;i
++){for(int j
=0;j
<=n
;j
++){cout
<<c
[i
][j
];}cout
<<endl
;} LCS(m
,n
,x
,b
);}
總結
以上是生活随笔為你收集整理的算法设计与分析——动态规划——最长公共子序列的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
