[問題] Longest Common Subsequence

[heymei0421 (heymei)]

大家好

目前 在寫 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:又是小黃作業XDD hw4
→ xatier:不過小黃不是只有要求找出一組就好了@@? 幹嘛全部都找?
→ xatier:http://codepad.org/jl3xg8R3 我的作法 :)
→ heymei0421:哪有~~是全部都要找吧@@我看他的demo結果阿PDF上
→ heymei0421:我剛剛重看一次...真的只找一個XDDDDDDDDDDDDDDDDDD
→ xatier:In case there is more than one lcs, you may find any
→ heymei0421:害我弄得半死= =
→ xatier:one of them
→ heymei0421:謝拉XD 你都寫完了喔
→ xatier:恩，大概吧(?    A, B 兩種方法差不多阿
→ heymei0421:ㄟ 你的做法應該會跑到無限迴圈吧= =
→ xatier:不會阿，你怎麼會這麼覺得?
→ heymei0421:可能你外部怎麼寫我不知道，可是對於lcs那個function
→ heymei0421:你i,j不會減少ㄟ
→ heymei0421:我想應該是你外部有寫別的東西吧@@"
→ xatier:i, j 幹嘛減少? 不就往下遞迴 0.0
→ heymei0421:喔喔= =因為你沒有while拉 我有XDDD
→ xatier:http://i.imgur.com/GbJIw.png 建議你再看一下作業講義這邊
→ heymei0421:感謝= = 奇怪我呼叫test_lcs("pioneer",7,"springb..等
→ heymei0421:他會說overloading失敗ㄟ..明明參數數目不同..
→ heymei0421:可以了 我右眼殘了
→ xatier:詳細希望？ 我這邊不會這樣
→ xatier:XDDDDDD