Longest Common Subsequence(LCS) 這次要介紹的是Longest Common Subsequence，以下舉個例子來說，給予兩個字串“ A BC D G H ”和“ A E D F H R”他們的共同最長子序列即是“ADH”長度為3，註： 子序列是以相同的相對順序出現的序列，但不一定是連續的。例如，“abc”，“abg”，“bdf”，“aeg”，“”acefg“等等是”abcdefg“的子序列。 演算法(運用遞迴解法)： 讓兩個input字串為X[0....m-1]和Y[0....n-1]，並且長度分別為m和n，LCS(X[0....m-1], Y[0....n-1])為這兩字串的LCS長度。 從最後一個字元開始比較，如果一樣則為1+ LCS ( X[ 0....m-2], Y[0....n-2])，否則的話為MAX( LCS ( X[ 0....m-2], Y[0....n-1]), LCS ( X[ 0....m-1], Y[0....n-2]))即找出扣掉X最後一字元與Y或是扣掉Y的最後一個字元與X的LCS長度。 C程式碼 : #include <stdio.h> #include <string.h> //宣告max function int max(int a, int b); //LCS function int lcs(char* a, char* b, int m, int n){ if( m == 0 || n ==0){ return 0; } //開始遞迴解法(以上演算法的第二步驟) if(a[m-1] == b[n-1]) return 1 + lcs(a, b, m-1, n-1); else return max(lcs(a, b, m-1, n), lcs(a, b, m, n-1)); } int max(int c, int d){ return (c > d)? c: d; } int main() { c
發表文章
- 取得連結
- 以電子郵件傳送
- 其他應用程式
嗨，大家好我是Jeremy，會開始寫網誌是因為十月底剛退伍正處在找工作的階段，但幾次面試下來讓我不得不加強自己的C語言方面的能力，廢話不多說讓我們來看看以下幾個GeeksforGeeks的考題，也歡迎大家多多交流，謝謝！ 指標(進階) Q1. 難度*** void fun (int *p) { int q = 10; p = &q; } int main() { int r = 20; int *p = &r; fun(p) ; printf("%d", *p); return 0; } Sol: 20 , 由於fun傳遞並不是p的位置，在此處q只是pointer p的一份拷貝而已，當我們更改q去指向別的地方並不會更動到p，若要輸出正確為10，更動程式碼如下： void fun (int **ptr) { static int q = 10; *ptr = &q; } int main() { int r = 20; int *p = &r; fun (&p); printf("%d", *p); return 0; } 更改後，將p的位置傳入fun，fun的參數也要改為pointer的pointer，此時ptr的值也被改為q的位置。註：static變數為整個程式結束後才從記憶體中釋放。 Q2. 難度** Assume sizeof an integer and a pointer is 4 byte. Output? #include <stdio.h> #define R 10 #define C 20 int main(){ int (*p)[R][C]; printf("%d", sizeof(*p)); getchar(); return 0; } Sol: 800 , 10*20*sizeof(int) = 10*20*4 = 800，注意只針對把integ