今天是2012年12月22日。今天的算法練習題是最長公共子序列的長度求解。 此題初看時，感覺問題非常復雜，要求解兩個序列的最長的(可以不連續)的公共子序列。但是，"將復雜的問題分解成簡單的問題"是基本的程序設計思想。分治法是將一個大問題分解成多個相似的小問題，而本題采用的動態規劃算法，則是將復雜的問題分解成一系列的相似的子問題。另外，將所求解的子問題的解通過數組等容器保存起來，來節省重復求解相同子問題的時間，是動態規劃算法的一個很重要的思想:備忘錄思想。 另外，本題還將采用逆向的思路，這與常規的順序的思路相悖。str1[a],str2[b]兩個字符串，不是從左至右的考慮，而是從右至左的方向。 分析過程如下: str1[a],str1[b]是待求最長公共子序列的兩個字符串，假設result[c]就是其最長公共子序列。 那麼就有以下3種情況。 1.如果str1[a-1]==str2[b-1]，那麼肯定有result[c-1]=str1[a-1]=str2[b-1],即最後一個元素一定是最長公共子序列的一部分。那麼，就可以不再考慮str1[a-1],str2[b-1],result[c-1],從他們之前的元素開始討論，也就是意味著，result[c-2]及之前的元素就是str1[a-2]之前的元素與str[b-2]之前的元素的最長公共子序列。 2.如果str1[a-1]!=str2[b-1],而且result[c-1]!=str1[a-1]，那麼就可以肯定,str1[a-1]不在最長公共子序列中，也就是說，result[c-1]及之前的元素就是str1[a-2]之前的元素與str2[b-1]之前的元素的最長公共子序列。 3.如果str1[a-1]!=str2[b-1],而且result[c-1]!=str2[b-1]，類似的，就可以肯定,str1[b-1]不在最長公共子序列中，也就是說，result[c-1]及之前的元素就是str1[a-1]之前的元素與str2[b-2]之前的元素的最長公共子序列。 由此，可以得到遞歸方程。(ps:我不知道在這裡如何插入公式，如果您知道，請告訴小弟我，非常感謝!) max_len[i][j]=0 如果i<=0 || j<=0 (當一個序列長度為0時，也就沒有意義) =1 +max_len[i-1][j-1] 如果str1[i-1]==str2[j-1] (對應上面第1種情況) =MAX(max_len[i-1][j],max_len[i][j-1]) 如果str1[i-1]!=str2[j-1] (對應上面第2,3種情況) 思路已經很清晰了，代碼如下:
最長公共子序列
1 #include <stdio.h>
2 #include <string.h>
3 #define MAX 100
4
5 int max(int num1,int num2);
6
7 //記錄a[i],b[j]的最長公共子序列的長度
8 int max_len[MAX+2][MAX+2]={0};
9
10 char a[MAX]="abcde";
11 char b[MAX]="afffbcde";
12
13 int main()
14 {
15 int len_a=strlen(a);
16 int len_b=strlen(b);
17 int result_max=0;
18 int i,j;
19 LCS(len_a,len_b);
20 for(i=1;i<=len_a;i++)
21 {
22 for(j=1;j<=len_b;j++)
23 {
24 if(result_max<=max_len[i][j])
25 result_max=max_len[i][j];
26 }
27 }
28 printf("result: %d\n",result_max);
29 return 0;
30 }
31
32 int LCS(int m,int n)
33 {
34 if(m<=0 || n<=0)
35 return 0; else if(max_len[m][n]!=0)
return max_len[m][n];
36 else if(a[m-1]==b[n-1])
38 return (max_len[m][n]=LCS(m-1,n-1)+1);
40 else
41 return (max(LCS(m,n-1),LCS(m-1,n)));
42 }
43
44 int max(int num1,int num2)
45 {
46 return (num1>num2?num1:num2);
47 } 明天得把具體的最長公共子序列給打印出來。 以下內容補充於2012年12月23日: 昨天留了個問題，就是打印出最長公共子序列。想了一會，沒什麼思路，就索性把max_len給打印出來，結果一打印我才發現，我把問題想得太復雜了。這本是一個多麼簡單的問題。 比如str1="abbcd"; str2="afffbcd"; 那麼打印出max_len:?1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 4 一目了然了。當且僅當str1[a-1]==str2[b-1]時，肯定會使得max_len中對應元素加1. 在程序中加一步就可以了。如下: 1 for(i=1;i<=len_a;i++)
2 {
3 for(j=1;j<=len_b;j++)
4 {
5 if(max_len[i][j]!=0)
6 printf("%c ",a[i-1]);
7 }
8 } 如果您覺得我的文章對您有所幫助，請贊一下，非常感謝! 本文出自 “Neil的博客” 博客，請務必保留此出處http://neilhappy.blog.51cto.com/5504414/1097226
