Bài toán xử lý xâu dựa trên quy hoạch động?

[Soul Killer]

Xin các cao thủ ra tay xử lý giúp bài này bằng Pascal:
Cho 1 xâu S có độ dài <=100 và n xâu x1,x2,...,xn. (n<=20, độ dài mỗi xâu xi <= 20).
a) Cho biết có thể tạo ra xâu S bằng cách ghép các xâu nhỏ xi lại được không? (số lần lấy không hạn chế). Nếu được, chỉ ra 1 cách ghép sao cho số lần dùng xâu xi là ít nhất.
b) Nếu không có phương án ghép thành xâu S, chỉ ra cách xóa đi ít nhất các ký tự của S để tồn tại cách ghép. Nếu đã xóa đi mà không tìm được thì ghi -1.
Input.inp
S
n
x1
x2
.
.
.
xn

Output.ou1 (câu a)
xi
.
.
.
xm
<<m là số xâu xi dùng để ghép thành xâu S>>

Output.ou2 (câu b)
Ghi ra xâu S mới
x1
.
.
.
xk
<<k là số xâu si dùng để ghép thành xâu S mới>>

[Soul Killer]

Không lẽ ai cũng "bó tay" với bài toán này sao?

[pfiev]

Câu a thì ko có vấn đề, câu b hơi khó.
Sau giống mấy bài thi QG hồi năm 12 thế!

[Soul Killer]

Câu a bạn làm như thế nào? Viết source ra xem sao.

[pfiev]

Làm kiểu vét cạn ấy. Bài này (a) chắc trong chương đầu của cuốn Tin 11 chắc có (hồi đó học lóm của đứa bạn). Thế cũng là QHĐ chứ nhỉ?
Hic, tui học hết năm 3 rồi mà ép ngồi viết source bài này!!!

[Soul Killer]

Thôi đi. Nếu vét cạn thì máy sẽ tiêu luôn đó. Tôi đã thử rồi nhưng không được. Nếu vét được thì tôi đã vét rồi. Quy hoạch động quan trọng là tìm được công thức quy hoạch động và tổ chức dữ liệu là mọi thứ đều xong.

[msn]

Bạn gì ơi sao bạn đi khắp nơi để hỏi bài này thế
Vẫn chưa thoả mãn với công thức QHĐ kia à

[hmt]

Bai nay khac gi bai tim xau chung dai nhat cua 2 xau dau...Don gian thoi ma!

[Soul Killer]

Vậy các bạn có thể viết source ra được không?

[luan01]

Bai nay de thoi, chi goi y thoi:
Goi a[i,j]:= so xau nho nhat tu phan tu thu i den phan tu thu j
Cho 2 vong for chay nhu sau:
M:=length(s);
For i:=1 to M-1 do
For j:=i+1 to M do

[msn]

Bài này QHĐ dùng mảng một chiều (chứ không phải là vét cạn)
a[i]=j có nghĩa là đoạn xâu từ 1-->i có thể chuyển thành các xâu con và xâu con cuối cùng là j.
Tương tự với câu b.
Bài đơn giản thế sao mãi vẫn không có ai trả lời đúng vậy ?

[CrazyBabe]

Câu A thì đúng là quy hoạch động được. Hàm quy hoạch tương đối đơn giản. Alike msn said. Nhưng cụ thể thì cần thêm feedback là B[j]=k >> nó xuất fát từ vị trí thứ k để ghép thêm xâu j. Cái này chẳng có gì, chỉ để tăng tốc thôi.
Câu B thì kô. Thực sự chưa nghĩ ra, thử dùng Gen xem sao ?

[msn]

câu b cũng tương tự như vậy thôi
anh bạn nghĩ kĩ lại xem

[CrazyBabe]

He he, bài này cả thế hệ chúng tôi nghĩ kĩ rùi cậu ạh. Cậu cứ cài đi rùi tôi cho một test giãy đành đạch luôn. Liệu câu B làm QHD thì cậu fát sinh feedback như thế nào ? Select where để được solution min đây ? Trình bày rõ ràng hộ cái.

[msn]

Thế hệ nào mà bài này không nghĩ ra thế.
Bài này QHĐ rõ thế mà không ra à.
Anh có dám cá tôi làm xong bài này không ?

[CrazyBabe]

Àh, chả dám ká mô. Cậu cứ trình bày đi, tôi test cho. Qua được thì tốt. Kô qua cũng chả sao.
Thế hệ chúng tôi là dân Tổng Hợp 1997-2000. Okie ? Cũng chả đầu tư vào bài này nhiều, nhưng sau 1 giờ học (3 tiếng) kô làm ra >> kết lựng kô làm được (hè hè, dốt quá nhể ?)
PS: Kô cần thiết phải máu me thế, show tí kiến thức đi.

[CrazyBabe]

Hey MSN, where are u ? Can u show me the way ?

[CrazyBabe]

Hey MSN, where are u ? Can u show me the way ?

[msn]

Làm cả bài thì ngại lắm tôi chỉ viết cái công thức QHĐ thôi :
Cost[i] là số lượng xâu con nhỏ nhất có thể dùng để tạo ra i kí tự đầu của xâu cần tạo
Cost[i]=Min(Cost[j]+1, sao cho i>j và từ đoạn từ j+1-->i là một xâu con)
khởi tạo Cost[0]=0 còn Cost[i]=inf
Bác xem có ổn không ?

[CrazyBabe]

Ụa, chả thấy ổn giề cả, ngay câu 1 đã fải làm thế rồi.
Sinh xong costing reference thì cậu làm cái gì với nó để select ra những failure ?

[msn]

Đó là câu 1 còn câu 2 đây:
Cost[i] là số lượng các kí tự nhỏ nhất có thể bỏ đi để tạo ra được i kí tự đầu của xâu.
Cost[i]=Min(Min(Cost[j], sao cho i>j nếu từ đoạn từ j+1-->i là một xâu con),Min(Cost[j]+i-j sao cho i>j nếu từ đoạn j+1-->i không phải là xâu con))
khởi tạo Cost[0]=0 còn Cost[i]=inf
Thế đã được chưa ?

[CrazyBabe]

Tôi có hỏi cậu hàm QHĐ đâu ? Sau khi sinh bảng ref thì cậu select như thế nào để kô mất đi bản chất QHĐ cơ ? Chứ còn sinh xong mà dùng ROAM thì...

[msn]

Anh cứ đọc lại đi. Hàm câu a và câu b khác nhau mà.

[CrazyBabe]

Ui dòi oi...
Tôi có mù đâu...
Tôi chẳng quan tâm đến hàm QHĐ --> rõ thế rồi cơ mà
Chỉ quan tâm đến chuyện cậu execute thế nào với cái bảng ref đấy để đưa ra những lựa chọn loại bỏ thôi ?
Cả mấy post vô dụng, pó chân.

[bete]

Ba.n msn cho ho?i 1 ti' nhe':

Cost[i] là số lượng xâu con nhỏ nhất có thể dùng để tạo ra i kí tự đầu của xâu cần tạo
Cost[i]=Min(Cost[j]+1, sao cho i>j và từ đoạn từ j+1-->i là một xâu con)
khởi tạo Cost[0]=0 còn Cost[i]=inf

Cho^~ do`ng:
Cost[i]=Min(Cost[j]+1, sao cho i>j và từ đoạn từ j+1-->i là một xâu con)

==> j ba('t đa^`u tu*` bao nhie^u va^.y (0 hay 1 hay .....) !? va` j ke^'t thu'c o*?
(i-1) co' pha?i 0 !?

[bete]

Xin cho ho?i ba.n msn 1 ca^u nu*~a:

o*? do`ng:

Cost[i]=Min(Min(Cost[j], sao cho i>j nếu từ đoạn từ j+1-->i là một xâu con),Min(Cost[j]+i-j sao cho i>j nếu từ đoạn j+1-->i không phải là xâu con))

==> co' ne^n su*?a la`:

Cost[i]=Min(Min(Cost[j]+1, sao cho i>j nếu từ đoạn từ j+1-->i là một xâu con),Min(Cost[j]+i-j sao cho i>j nếu từ đoạn j+1-->i không phải là xâu con))

(Vo*'i qui uo*'c: S[i,j] la` xa^u con trong S ba('t đa^`u tu*` chi? so^' i, ke^'t thu'c o*? chi? so^' j: ne^'u S[j+1,j] la` 1 xa^u con thi`
Cost(S[1,j]) + Cost(S[j+1,i]) = Cost(j) + 1)

[bete]

Xin lo^~i ba.n msn nghen, tui lo^.n ro^`i:

Cost[i]=Min(Min(Cost[j], sao cho i>j nếu từ đoạn từ j+1-->i là một xâu con),Min(Cost[j]+i-j sao cho i>j nếu từ đoạn j+1-->i không phải là xâu con))

nhu* ba.n vie^'t la` đu'ng (mi`nh đang ti'nh so^' ky' tu*. bi. xo'a cho*' 0 pha?i ti'nh
so^' chuo^~i con ca^`n xa`i)

[bete]

Co' the^? ha`m QHD cu?A ba.n bi. sai logic 1 ti'. Cho tui no'i nghen:

Tui qui uo*'c: S[i,j] la` xa^u con trong S ba('t đa^`u tu*` chi? so^' i, ke^'t thu'c o*? chi? so^' j. Vi' du.: S[3,5] -> ba('t đa^`u o*? 3, ke^'t thu'c o*? 5 (3 ky' tu*.)

Cho S = 'abc'; x = 'ac' (1 chuo^~i con tho^i)
Kho?*i ta.o: cost[0] = 1; cóst[1] = cost[2] = cost[3] = inf

Loop i: 1 -> 3

i=1:
loop j: 0 -> 0
j=0: S[1,1] = a: 0 la` 1 xa^u con => cost[1] = min{cost[0] + 1} = 1

i=2:
loop j: 0 -> 1
j=0: S[1,2] = ab: 0 la` 1 xa^u con => cost1[2] = min{cost[0] + 2} = 0 + 2 = 2
j=1: S[2,2] = b: 0 la` 1 xa^u con => cost2[2] = min{cost[1] + 1} = 1 + 1 = 2
==> cost[2] = min {cost1[2], cost2[2]} = 2

i=3:
loop j: 0 -> 2
j=0: S[1,3] = abc: 0 la` 1 xa^u con => cost1[3] = min{cost[0] + 3} = 0 + 3 = 3
j=1: S[2,3] = bc: 0 la` 1 xa^u con => cost2[3] = min{cost[1] + 2} = 1 + 2 = 3
j=2: S[3,3] = c: 0 la` 1 xa^u con => cost3[3] = min{cost[2] + 1} = 2 + 1 = 3
==> cost[3] = min {cost1[3], cost2[3], cost3[3]} = 3

end loop i

==> nhu* va^.y đa'p so^' theo nhu* ca'ch cu?a ba.n msn la` 3 (xo'a he^'t 3 ky'
tu*. ==> đuo*.c 1 chuo^~i tro^'ng ==> tuo*ng đuo*ng vo*'i 0 chuo^~i con ghe'p
la.i). Tuy nhie^n đa'p so^' đu'ng se~ la` 1: xo'a b tu*` chuo^~i S (abc) se~ đuo*.c
chuo^~i con x (ac) !?

Kho^ng bie^'t tui co' lo^.n cho^~ na`o 0 !?

(xin lo^~i la` ca'ch tui bo? da^'u co' the^? la`m ma^'y bo^` kho' đo.c la('m !?)

[bete]

Theo tui nghi~, ne^'u ca'ch gia?i cu?a ba.n msn co' tru.c tra(.c, thi` tru.c tra(.c la`
o*? cho^~:

Ba.n msn pha^n ti'ch chuo^~i con S[1,i] tha`n 2 chuo^~i con S[1,j] & S[j+1,i]
Ne^'u chuo^~i con S[j+1,i] 0 ba(`ng 1 chuo^~i con Xi na`o thi` ba.n cho.n ca'ch
xo'a ta^'t ca? ca'c ki' tu*. trong chuo^~i con S[j+1,i] ==> đuo*.c 1 chuo^~i tro^'ng
==> tuo*ng đuo*ng vo*'i 0 chuo^~i con Xi no^'i vo*'i nhau

Lo*i gia?i na`y la` đu'ng ne^'u ba`i toa'n đo`i ho?i ti`m 1 lo*'i gia?i na`o cu~ng
đuo*.c

Tuy nhie^n ba`i toa'n la.i đo`i lo*`i gia?i to^'i u*u (xoa' it' ky' tu*. nhu*'t). Ho*n
nu*~a ne^'u chi? ca^`n ti`m 1 lo*`i gia?i thi` chi? ca^`n xo'a he^'t ca'i ky' tu*.
tu*` chuo^~i nguye^n thu?y S (kho?i ca^`n suy nghi~ la^u la('c) :)

Vi' du.: S = abc; X = ac
abc 0 la`1 xa^`u con na`o => chi? xo'a 1 ky' tu*. b la` co' xa^u con X (ac) (thay
vi` xoa' he^'t ca? 3 ky' tu*.)

Co' the^? su*?a ca'ch gia?i cu?a ba.n msn la.i 1 ti': gia?i the^m 1 ba`i toa'n tuo*ng tu*. kha'c (du`ng QHD): Cho 1 xâu S có độ dài <=100 và n xâu x1,x2,...,xn. (n<=20, độ dài mỗi xâu xi <= 20). Chi? ra 1 lo*`i gia?i to^'i u*u: xo'a i't ky' tu*. nhu*'t trong S
đe^? ta.o tha`n 1 trong nhu*~ng xa^u con Xi

Ba`i toa'n na`y tuo*ng tu*. ca^u b cu?a ba`i toa'n nguye^n thu?y nhu*ng ha`m QHD thi` kha'c (& đo*n gia?n ho*n nhie^`u)

Lu*u y': đe^` ba`i nguye^n thuy? ye^u ca^`n in ra -1 ne^'u 0 co' lo*`i gia?i
==> tui nghi~ la` xoa' he^'t ca'c ky' tu*. đe^? co' 1 chuo^~i tro^'ng 0 đuo*.c coi la` lo*`i gia?i (0 ne^n tra? ve^`n gia' tri. 0 ma` pha?i tra? ve^` gia' tri. -1 !?!?)

[CrazyBabe]

Hic, bete ơi, bạn làm ơn gõ unicode được không, xem mã mù mắt mất.
msn: cậu giải thích rõ hộ ra đi, lâu rồi kô nghĩ mấy bài kiểu này giờ cù lần lém, nhưng thực sự là tôi chả hiểu cậu sinh bảng ref xong - cứ cho là xong đi - thì làm gì tiếp ?

[bete]

Bo^` CrazyBabe la`m o*n chi? du`m tui ca'ch go~ unicode đuo*.c 0 !?
Ca'm o*n nhie^`u.

theo tui nghi~ thi` mi`nh đie^`n ca'i ma?ng Cost nhu* sau

Loop i: 1 -> length(s)
cost[i] = ......... (du*.a tre^n cost[j]; j: 0 -> (i-1))
end loop i

Cuo^'i cu`ng nhi`n vo^ cost[length(s)] thi` bie^'t ca^`n xo'a bao nhie^u ky' tu*.
Muo^'n in ra ca'c xa^u con cu?a lo*`i gia?i to^'i u*u thi` pha?i đie^`n the^m 1
ma?ng kha'c (& do` nguo*.c ca'i ma?ng na`y)

[CrazyBabe]

Hic, gõ cứ như telex thui, diễn đàn đã có bộ gõ nhúng rùi mà ?

[Antone]

Hehehe! sao nhiều người kô nhìn thấy bộ gõ thế ta! Bạn nhìn xuống phía dưới thanh status ấy!!! nhấn F9 để thay đổi kiểu gỏ!