View Full Version : Xâu con
Vừa làm xong bài này. Hóa ra cực dễ. Chưa đầy 3' là xong.
Post lên cho mọi người thử. Đây là phần mình yếu nhất.
Xâu a gọi là xâu con của xâu b nếu có thể xóa bớt 1 số kí tự của b để được xâu a.
Ví dụ b='abcdefg123' thì a='abc' là 1 xâu con của b.
Viết ct tìm xâu c có độ dài lớn nhất là xâu con của cả a & b.
Bài này dành cho new mem. Ai pro QHĐ như bld thì ngồi chơi xơi nước nhá.
đúng là xài QHĐ là xong
vận dụng bài "biến đổi xâu" trong sách của thầy Hoàng (về cách suy nghĩ)
Chuẩn. Công thức truy hồi đơn giản hơn.
xâu con chung dựa trên bài cơ bản là "dãy con chung dài nhất " đúng k nhỉ :)
đúng là xài QHĐ là xong
vận dụng bài "biến đổi xâu" trong sách của thầy Hoàng (về cách suy nghĩ)
ko biết hu làm thế nào, b vẫn chưa nghĩ ra làm cách nào để biến đổi , chỉ biết cách thông thường thôi ^^
Đúng như anh huysun nói:
Gọi F[i,j] là độ dài xâu con lớn nhất của 2 xâu a(1..i) và b(1..j)
Nếu a[i]=b[j] thì F[i,j]=F[i-1,j-1]+1, ko thì bằng Max(F[i-1,j],F[i,j-1]).
CT đã xây dựng xong. Truy vết rất dễ.
biến đổi xâu ở chỗ nào vậy ^^'
Sử dụng cái bài "Biến đổi xâu đó"
Bài cho 3 phép biển đổi là chèn thay và xóa ý.
bài này đâu có liên quan ?+_+
Vận dụng được mà. Cái phần so sánh kí tự cuối 2 xâu đó.
không sao , tùy cách nghĩ của mỗi người thôi ^^, người này thấy dc cái giống, người kia thì ko, làm 1 bài khác thử xem các bạn :tìm xâu con đối xứng dài nhất
Bài này chưa nghĩ ra ct truy hồi. Làm tạm cách này vậy O(n^2) (hơi lớn thì phải)
F[i] là độ dài xâu con dài nhất đx bắt đầu tại i.
Lập 1 hàm dx(s,i,j):boolean trả về true nếu xâu s[i..j] là đối xứng và ngược lại.
n:=Length(s);
For i:=1 to n-1 do
Begin
k:=1;
For j:=i+1 to n do If dx(s,i,j) then k:=j-i+1;
If F[i]=0 then F[i]:=k else F[i]:=1;
End;
Truy vết: Tìm max của F, vd vị trí là k, in ra s từ k đến max+k-1.
Vậy là cách giải của mình ko phân rã được bài toán nến ko thể gọi là QHĐ, để nghĩ thêm đã. Ít ra cách này cũng đã AC.
Các bạn có thể 1 trong 2 mảng lại rồi tìm xâu con chung thôi :)
ngtrhieu0011
17-07-2009, 20:17
Dynamic Prog có 3 dạng chính là: Non Inc/Dec Seq, Longest Common Seq, Knapsack. Còn lại hầu hết là biến thể của 3 dạng chính này. Bài bạn quangtp cho ngay dạng chuẩn thứ 2 của QHĐ, tư tưởng trên mạng đầy ra đấy ^^
quang : cách của quang là vét cạn
vậy thì sửa đề 1 chút , tìm xâu con đối xứng dài nhất , các kí tự trong xâu con này không nhất thiết phải liên tiếp nhau trong xâu chính
abdbcecggbbha
Gọi S là xâu đảo của S1 , T là xâu chung dài nhất của 2 xâu S, S1 . T là xâu đối xứng dài nhất
ngtrhieu0011
17-07-2009, 20:38
xâu con đối xứng dài nhất của xâu A hay B hay của 2 xâu
để tìm xâu con đối xứng của 1 xâu:
Tạo F[i,j] có ý nghĩa là độ dài xâu con đối xứng dài nhất của xâu A tính từ A[i] đến A[j] (i<=j)
Khởi tạo F[i,i] := 1;
Với mỗi F[i,j] (i<=j) ta tính:
Nếu A[i] <> A[j] thì F[i,j] = Max ( F[i-1,j], F[i,j-1] )
Nếu A[i] = A[j] thì F[i,j] = Max ( F[i-1,j], F[i,j-1] ) + k (k=1 nếu i+1=j; k-2 nếu i+1<>j)
Kết quả là F[1,Length(A)] ^^
mèn ơi , để mấy mem mới bắt đầu QHD giải chứ , sư phụ giải mấy bài đây như chơi mà...
còn phần truy vết mà
[=========> Bổ sung bài viết <=========]
xâu con đối xứng dài nhất của xâu A hay B hay của 2 xâu
để tìm xâu con đối xứng của 1 xâu:
Tạo F[i,j] có ý nghĩa là độ dài xâu con đối xứng dài nhất của xâu A tính từ A[i] đến A[j] (i<=j)
Khởi tạo F[i,i] := 1;
Với mỗi F[i,j] (i<=j) ta tính:
Nếu A[i] <> A[j] thì F[i,j] = Max ( F[i-1,j], F[i,j-1] )
Nếu A[i] = A[j] thì F[i,j] = Max ( F[i-1,j], F[i,j-1] ) + k (k=1 nếu i+1=j; k-2 nếu i+1<>j)
Kết quả là F[1,Length(A)] ^^
sao k gán
f(0,j)=f(i,0)=0
thì A[i] = A[j] thì F[i,j] = Max ( F[i-1,j], F[i,j-1] ) + 1
đỡ phức tạp hơn k ??
ngtrhieu0011
17-07-2009, 20:46
truy vết dễ mà, các bạn khi hiểu cách thành lập mảng F thì có thể truy vết rất nhanh ^^
(hình như forum mình sợ QHĐ nhỉ :| )
ý mình là còn phần truy vết cho các bạn . Hix
a hieu gửi mấy đề QHD cho mọi người luyện đi , yếu gì thì đánh vào cái nấy !
sẵn đây a hieu gợi ý giùm vụ này luôn đi , e nghĩ hoài ko ra
http://www.ddth.com/showthread.php?t=288086
ngtrhieu0011
17-07-2009, 21:03
em mới lên 11 àh, sao lại xưng hô thế?
Quy hoạch động (Dynamic Programing) là 1 cách giải mà trong đó ta làm các bước sau:
+ Chia bài toán thành các bài toán cơ sở "có thể giải được" và giải các bài toán cơ sở ấy.
+ Tập hợp các lời giải của "bài toán cơ sở" để giải các bài toán lớn hơn.
+ Truy vết lại lời giải.
Để giải QHĐ, chúng ta cần các thứ sau đây:
+ Bài toán cơ sở.
+ Công thức Truy hồi.
+ Mảng Quy hoạch động (để lưu kq các bài toán con)
Ví dụ 1 bài đơn giản:
Hãy xuất số ****nacci thứ n.
Ta xác định:
Bài toán cơ sở: Fib(0) = Bib(1) = 1;
Công thức truy hồi: Fib(i) = Fib(i-1) + Fib(i-2);
Mảng QHĐ: F[i] với F[i] là giá trị của số ****nacci thứ i;
Vậy sau khi chạy ra đã tìm được F[n] là giá trị của dãy ****nacci thứ n
Sau đây là 3 bài QHĐ kinh điển:
+ Longest (non) Inc/Dec Seq
+ Longest Common Seq
+ Knapsack
(đây cũng là 3 dạng QHĐ mà các bạn phải biết ^^)
(đây là bài giảng của thầy Vũ Tấn Hưng, em ghi lại và trình bày theo ý hiểu của em ^^, có dịp em sẽ trình bày sâu và cho 1 số bài tập kinh điển)
bld THCS đó ^^
mấy bài trên thì e biết hết rồi , có gì cụ thể hơn , lạ hơn ko a ?
ngtrhieu0011
17-07-2009, 21:12
post bài "tẩu thoát", tha hồ mà lạ + cụ thể nhé :|
1. cho bảng m[A..D,A..D] mỗi ô của bảng cũng mang 1 trong 4 giá trị A..D
cho xâu s chỉ gồm tối đa 4 kí tự trong A..D
phép co R(i) thay kí tự S[i] và S[i+1] = kí tự m[s[i],s[i+1]]
thực hiện các phép co để đổi xâu S thành kí tự X
2. dãy catalan là dãy nguyên dương bắt đầu và kết thúc = 0 , 2 phần tử liên tiếp nhau chênh 1 đơn vị
tìm số thứ p trong dãy tất cả các dãy catalan độ dài n đã được sắp xếp theo thứ tự từ điển
Giúp bld với anh
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.