想了挺久到底第一篇在這兒的博客寫什麼好,剛好這兩天又一次看到動態規劃的LCS算法覺得還是有點意思的,就拿來寫了寫,第一篇博客就發它吧。
#include<iostream><iomanip> LCS_Length( *X, *Y, *count[], *tag[], length_X, ( i = ; i < length_X+; i++] = ( i = ; i < length_Y+; i++][i] = ( i = ; i <= length_X; i++ ( j = ; j <= length_Y; j++ (X[i-] == Y[j - = count[i-][j-]+= (count[i-][j] > count[i][j-= count[i-= = count[i][j-= Print_LCS( *tag[], *X, Length_X, (Length_X == || Length_Y == i = Length_X, j = (tag[i][j] == <<X[i-]<<setw(-,j- (tag[i][j] == -- *X = *Y = *count[ ( i = ; i < ; i++= []; *tag[ ( i = ; i < ; i++= [<<<<count[][]<<<<
主要函數有兩個,一個函數是做出保存最長公共子序列的元素個數的矩陣,這裡給出的示例中,兩個字符串都各6個字符,所以給出的是7行7列矩陣(第一行第一列全為零)。
另外一個函數即為打印函數,從矩陣右下角一位開始遍歷到[0][0]位,凡是遇到tag[i][j]標志為0則將該位的字符打印出來。算法比較簡單易懂,具體可以參考《算法導論》。
下面補充說一個問題:二維指針到底怎麼用。比如前面的二維數組初始化,如果我希望能夠通過字符串的長度來給我的二維數組定義大小,而不是用常數來指定,使得我們可以通過strlen()函數來定義長度,那麼就要用到二維指針。
注意:int *Arr[strlen(str)];這種聲明方式是不正確的,編譯器會提示錯誤,數組的聲明必須使用常量。下面給出正確的示例: