問題描述：
給定兩個序列X={x1，x2，…，xm}和Y={y1，y2，…，yn}，找出X和Y的最長公共子序列，（給定兩個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列，）
細節須知（與之前隨筆的對比）：
將由陣列存盤起來一并輸出至檔案修改為邊運行邊輸出，增加了程式的魯棒性，
演算法原理：
a.最長公共子序列的結構
對X的所有子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列，并且在檢查程序中記錄最長的公共子序列，X的所有子序列都檢查過后即可求出X和Y的最長公共子序列，X的每個子序列相應于下標集{1,2，…，m}的一個子集，
b.子問題的遞回結構
要找出X和Y的最長公共子序列，可按以下方式遞回計算：當xm=yn時，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm（=yn）即可得到X和Y的最長公共子序列，當xm≠yn時，必須解兩個子問題，即找出Xm-1和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列，這兩個公共子序列中較長者即為X和Y的最長公共子序列，
c.計算最優值
利用動態規劃演算法自底向上地計算最優值，
d.構造最長公共子序列
首先從b[m][n]開始，依其值在陣列b中搜索，當b[i][j]=1時，表示Xi和Yj的最長公共子序列
1 #include<cstdio> 2 #include<cstring> 3 #include<stack> 4 #include<ctime> 5 #include<iostream> 6 #include<fstream> 7 #include<algorithm> 8 #include<windows.h> 9 using namespace std; 10 LARGE_INTEGER nFreq;//LARGE_INTEGER在64位系統中是LONGLONG，在32位系統中是高低兩個32位的LONG，在windows.h中通過預編譯宏作定義 11 LARGE_INTEGER nBeginTime;//記錄開始時的計數器的值 12 LARGE_INTEGER nEndTime;//記錄停止時的計數器的值 13 #define N 10000 14 //const int SIZE_CHAR = 10000; //生成32 + 1位C Style字串 15 const char CCH[] = "_0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_"; 16 int dp[N][N]; 17 char c; 18 int main(void) 19 { 20 //char a[N]; 21 //char b[N]; 22 //char a[SIZE_CHAR+2]; 23 //char b[SIZE_CHAR+2]; 24 ofstream fout; 25 int m = 0,i = 0; 26 int SIZE_CHAR; 27 cout<<"Please enter the number of times you want to run the program:"; //輸入程式運行次數 28 cin>>m; 29 //int SIZE[m]; 30 double cost; 31 //double runtime[m]; 32 srand((unsigned)time(NULL)); 33 fout.open("data.txt",ios::app); 34 if(!fout){ 35 cerr<<"Can not open file 'data.txt' "<<endl; 36 return -1; 37 } 38 fout.setf(ios_base::fixed,ios_base::floatfield); //防止輸出的數字使用科學計數法 39 for(i = 0; i < m; i++){ 40 //SIZE_CHAR=10000+RAND_MAX*(rand()%300)+rand(); //RAND_MAX=32767,隨機生成資料量 41 SIZE_CHAR = rand() % 10000; 42 fout<<SIZE_CHAR<<","; 43 // SIZE[i]=SIZE_CHAR; //限定資料規模為10000~9872867 44 char a[SIZE_CHAR + 1] = {'\0'}; 45 char b[SIZE_CHAR + 1] = {'\0'}; 46 cout<<"☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆The "<<i+1<<"th test's string size is:"<<SIZE_CHAR<<"☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆"<<endl; 47 for (int i = 0; i < SIZE_CHAR; ++i){ 48 int x = rand() / (RAND_MAX / (sizeof(CCH) - 1)); 49 a[i] = CCH[x]; 50 } 51 cout<<"The first random sting is:" <<a <<endl; 52 for (int i = 0; i < SIZE_CHAR; ++i){ 53 int x = rand() / (RAND_MAX / (sizeof(CCH) - 1)); 54 b[i] = CCH[x]; 55 } 56 cout<<"The second random string is:" <<b <<endl; 57 cout<<"The longest common subsequence is:"; 58 QueryPerformanceFrequency(&nFreq);//獲取系統時鐘頻率 59 QueryPerformanceCounter(&nBeginTime);//獲取開始時刻計數值 60 int la=strlen(a); 61 int lb=strlen(b); 62 memset(dp,0,sizeof(dp)); 63 for(int i=1; i<=la; i++){ 64 for(int j=1; j<=lb; j++){ 65 if(a[i-1]==b[j-1]) 66 dp[i][j]=dp[i-1][j-1]+1; 67 else 68 dp[i][j]=max(dp[i-1][j],dp[i][j-1]); 69 } 70 } 71 int i=la,j=lb; 72 stack<char>s; 73 while(dp[i][j]){ 74 if(dp[i][j]==dp[i-1][j]){//來自于左方向 75 i--; 76 } 77 else if(dp[i][j]==dp[i][j-1]){//來自于上方向 78 j--; 79 } 80 else if(dp[i][j]>dp[i-1][j-1]){//來自于左上方向 81 i--; 82 j--; 83 s.push(a[i]); //壓堆疊以便倒序輸出 84 } 85 } 86 while(!s.empty()) 87 { 88 c=s.top(); 89 printf("%c",c); 90 s.pop(); 91 } 92 cout<<endl; 93 QueryPerformanceCounter(&nEndTime);//獲取停止時刻計數值 94 cost=(double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart; 95 fout<<cost<<endl; 96 //runtime[i]=cost; 97 cout<<"The running time is："<<cost<<" s"<<endl; 98 } 99 fout.close(); 100 cout<<"Success!"<<endl; 101 return 0; 102 }
程式設計思路：
設序列X={x1，x2，…，xm}和Y={y1，y2，…，yn}的最長公共子序列為Z={z1，z2，…，zk}，則
a.若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長公共子序列，
b.若xm≠yn，且zk≠xm，則Z是Xm-1和Y的最長公共子序列，
c.若xm≠yn，且zk≠yn，則Z是X和Yn-1的最長公共子序列，
其中，Xm-1={x1，x2，…，xm-1}；Ym-1={y1，y2，…，yn-1}；Zk-1={z1，z2，…，zk-1}，
② 子問題的遞回結構
首先建立子問題最優值的遞回關系，用c[i][j]記錄序列Xi和Yj的最長公共子序列的長度，其中，X={x1，x2，…，xm}；Y={y1，y2，…，yn}，當i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故此時c[i][j]=0，在其他情況下，由最優子結構性質課件里遞回關系如下：
③計算最優值
以序列X和Y作為輸入，輸出兩個陣列c和b，其中c[i][j]存盤Xi和Yj的最長公共子序列的長度，b[i][j]記錄c[i][j]的值是由哪一個子問題的解得到的，這在構造最長公共子序列時要用到，問題的最優值，即X和Y的最長公共子序列的長度記錄與c[m][n]中，
④構造最長公共子序列
首先從b[m][n]開始，依其值在陣列b中搜索，當b[i][j]=1時，表示Xi和Yj的最長公共子序列是由Xi-1和Yj-1的最長公共子序列在尾部加上xi所得到的子序列；當b[i][j]=2時，表示Xi和Yj的最長公共子序列與Xi-1和Yj的最長公共子序列相同；當b[i][j]=3時，表示Xi和Yj的最長公共子序列與Xi和Yj-1的最長公共子序列相同，
時間復雜性分析：
a.計算最優值
由于每個陣列單元的計算耗費O（1）的時間，此部分演算法耗時為O（mn），
b.構造最長公共子序列
該演算法每一次遞回呼叫使i或j減1，因此演算法的計算時間為O（m+n），
生成的資料可匯入EXCEL中進行資料分析生成分析圖表，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/89821.html
標籤：C++
上一篇：ipv4的ip字串轉化為int型