[問題] Longest Common Subsequence

看板C_and_CPP作者heymei0421 (heymei)時間12年前 (2012/04/09 13:00)推噓0(0推 0噓 23→)

留言23則, 2人參與討論串1/1

大家好目前在寫 Longest Common Subsequence 用Dynamic programming solution實現寫到一個地方卡關很久所以特來求助版上的大大們我目前寫到一個function 此function要印出所有lcs的數值因為fuction滿短的所以我就直接貼上 // x是一維陣列1 : x={2,5,3,1,6,4} // y是一維陣列2 : y={1,2,3,4,5,6} // i , j分別是x,y陣列的長度 // tbl是一個二維陣列每一格記錄著x,y陣列合起來的lcs長度 // tbl如圖:http://ppt.cc/wv9; template<typename T> void lcs(const T* x,int i,const T* y,int j,const int*const* tbl) { //Output an lcs according to the two input sequences and the table tbl while((i>0)&&(j>0)) { if( *(x+(i-1)) == *(y+(j-1)) ) //由陣列最後一個元素比起 { cout << " " << *(x+(i-1)) ;//若相同則印出 i--; j--; } else { if(tbl[i][j-1]>tbl[i-1][j]) j--; else if(tbl[i][j-1]<tbl[i-1][j]) i--; else { lcs(x,i-1,y,j,tbl); //若tbl中任一元素的上與下值相同 j--; //則呼叫另一遞迴走任外一條路徑 } //j--則還是走原本路徑直到跑完 } } cout << endl; } 跑出來的結果: 6 5 2 3 2 3 2 3 2 4 3 2 正確應該是: 6 5 2 6 3 2 6 3 2 4 3 2 觀察一下我錯誤的結果<如我附的圖> 應該是我在呼叫遞迴時沒有把呼叫遞迴之前若x,y某一元素相同的值帶過去所以才會跑出3 2 ，而一直跑出32的原因應該是某些路徑會重複走到我一直想辦法想解決把6帶到下一個路徑但搞了老半天就是沒辦法這是我整個code : http://codepad.org/KTSWKNN2 請大大們幫忙 >"< -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.0.145

→

xatier

04/09 13:17, , 1^F

04/09 13:17, 1^F

→

xatier

04/09 13:50, , 2^F

04/09 13:50, 2^F

→

xatier

04/09 13:53, , 3^F

04/09 13:53, 3^F