//
you're reading...
00 - Chủ đề chung, Bài tập huấn luyện, Chủ đề quy hoạch động

Chuyên đề quy hoạch động: Dãy con chung dài nhất


Đề bài


Cho hai dãy số nguyên (a1,a2,…,am), (b1,b2,…,bn). Tìm dãy con chung có độ dài lớn nhất của hai dãy trên (coi dãy không có số nguyên nào là dãy con của mọi dãy và có độ dài bằng 0).


Hướng dẫn


Chúng ta có thể thấy ngay rằng độ phức tạp của bài toán trên phụ thuộc vào hai số m, n. Xét hai trường hợp:

+Trường hợp1:; m=0 hoặc n=0.

Đây là trường hợp đặc biệt, có duy nhất một dãy con chung của hai dãy có độ dài  bằng 0. Vì vậy dãy con chung có độ dài lớn nhất của chúng có độ dài bằng 0.

+Trường hợp 2: m# 0 và n # 0.

Trong trường hợp này, ta xét các bài toán nhỏ hơn là tìm dãy con chung có độ dài lớn nhất của hai dãy (a1,a2,…,ai), (b1,b2,…,bj) với 0 <= i <= m, 0 <= j <= n. Gọi [i,j] là độ dài của dãy con chung lớn nhất của hai dãy (a1,…,ai), (b1,…,bj). ; Như vậy ta phải tính tất cả các l[i,j] trong đó 0<=i<=m, 0<=j<=n.

Chúng ta có thể  thấy ngay rằng  l[0,0]=0. Giả sử ta tính được l[s,t] với 1

– Nếu ii # bj thì l[i,j]=max{l[i-1,j], l[i,j-1]}.

– Nếu ii=bj thì l[i,j]= 1+l[i-1,j-1].

Với những nhận xét trên, ta hoàn toàn tính được l[m,n] chính là độ dài dãy con chung dài nhất của (a1,..am), (b1,..bn).

Để tìm phần tử của dãy con, ta xuất phát từ ô l[m,n] tới ô l[0,0]. Giả sử ta đang ở ô l[i,j]. Nếu ai=bj thì ta thêm ai vào dãy con rồi nhảy tới ô l[i-1,j-1]. Nếu aibj thì l[i,j]=l[i-1,j] hoặc l[i,j]=l[i,j-1]. Nếu l[i,j]=l[i-1,j] thì nhảy tới ô l[i-1,j], ngược lại thì nhảy tới ô l[i,j-1].


Chương trình


(bằng ngôn ngữ Pascal)

uses crt;

const  fi=’b2.inp’;

var  a:array[1..10] of integer;

b:array[1..10] of integer;

kq:array[0..10,0..10] of integer;

i,j,maxa,maxb:integer;

f:text;

procedure init;

begin   

assign(f,fi);  reset(f);  i:=0;
    while not(eoln(f)) do
                begin
                     inc(i);
                     read(f,a[i]);
               end;
maxa:=i;
readln(f);
i:=0;
while not(eoln(f)) do
begin

                  inc(i);
read(f,b[i]);
end;
maxb:=i;
close(f);
end;
function max(a,b:integer):integer;
begin
if
a>b then max:=a
else max:=b;
end;
begin
init;
kq[0,0]:=0;
for i:=1 to maxa do
for
j:=1 to maxb do
if
a[i]<>b[j] then
kq[i,j]:=max(kq[i-1,j],kq[i,j-1])
else kq[i,j]:=kq[i-1,j-1]+1;
writeln(‘Do dai day con chung lon nhat:’,kq[maxa,maxb]);
i:=maxa;
j:=maxb;
while (i>0)or(j>0) do
if
a[i]=b[j] then
begin

write
(a[i]);
dec(i);
dec(j);
end
else

if
kq[i-1,j]=kq[i,j] then
dec(i)
else dec(j);
end.

Với nội dung file ‘b2.inp’ chứa 2 dãy (a1,a2,..am) ,(b1,b2,..bn) sau:

1 2 3 2 3 4 6

6 9 8 7

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: