Đề tài: day chung dai nhat

Bài tóan tìm dãy chung lớn nhất của hai hai dãy cho trước có độ dài khác nhau.
vd:
1 2 3 4 5 6 7 8 8 0 8 0
1 4 2 7 3 4 8 6 7 0
--> 1 2 3 4 6 7 0
khi xem phần hướng dẫn thì nó đưa ra thuật toán sau:
thiết lập mảng c [i,j] có m dong n cot
với
gán cho c:=0;
c[i,1]=1 khi b[1] có trong a[i];
c[1,j]=1 khia a[1] co trong b[j];
trường hợp khác
c[i,j]:=max(c[i-1,j],c[i,j-1],c[i-1,j-1] +ord(a[i]=b[j]);
ord(a[i]=b[j])=1 khi a[i]=b[j],0 trong TH còn lại.
anh chị giúp giảng nghĩa thiệt kĩ dùm em tại sao lại như vậy với nha?
à mà mấy anh có tài liệu về vấn đề này không cho em với! thanks trước nha.

Đây là kĩ thuật trong tin học gọi là quy hoạch động. Tức là c[i,j] sẽ là động dài dãy con chung dài nhất tính cho đến vị trí thứ i của dãy thứ nhất và vị trí thứ j của mảng thứ 2.
Như vậy kq cần tìm sẽ là c[n,m].

p/s mấy cái này phải tự nghiền ngẫm rỗi chạy thử mới thấy đc rõ.

uh mình đọc nó trong chương quy hoạch động nhưng không hiểu tại sao phải giải quyết bài toán theo công thức như vậy.
pác có tài liệu nào về cái nì thì cho mình xin với!

Cái này đơn giản lắm. Nhưng viết theo kiểu đó thí khó hiểu đó.
Ta sẽ xây dựng mảng C[0..n,0..m] theo cách cũng tương tự nhưng có cơ sở và dễ hiểu hơn nhiều. Ý nghĩa của C[i,j] thì ko có gì thay đổi vẫn là độ dài dãy con chung dài nhất tính cho đến vị trí thứ i của dãy thứ nhất và vị trí thứ j của mảng thứ 2. Kết quả sẽ là c[n,m].
Đương nhiên nếu 1 bên là dãy rỗng thì dãy con chung dài nhất cũng là dãy rỗng. Vậy C[i,0]=0 và C[0,i]=0 với mọi i.
Thay vì công thức truy hồi để dễ hiểu mính viết luôn Source cho bạn:

Code:

 for i:=1 to n do
  for j:=1 to m do
    if a[i]=b[j] then l[i,j]:=l[i-1,j-1]+1
    else l[i,j]:=max(l[i,j-1],l[i-1,j]);

Bài này giải bằng prolog nhanh lắm!

ah hay thật như vậy mảng c sẽ có chỉ số từ 0..n để xét phần tử thứ nhất
cách này hay thật thanks!
mà bạn có tài liệu nào về vấn đề quy hoạch động không cho mình xin với

duykhoa_12T

ah hay thật như vậy mảng c sẽ có chỉ số từ 0..n để xét phần tử thứ nhất
cách này hay thật thanks!
mà bạn có tài liệu nào về vấn đề quy hoạch động không cho mình xin với

Hay mà ko thấy thank.
Bạn có thể tham khảo cuốn DSAP TextBook của Lê Minh Hoàng. Hoặc là cuốn chuyên đề bồi dưỡng HSG THPT Bài Tập Quy Hoach Động của NXB Giáo Dục....

ah bạn cho minh hỏi tí lạc đề cái làm sao tạo bảng chèn code có scroll được dạ?

duykhoa_12T

Bài tóan tìm dãy chung lớn nhất của hai hai dãy cho trước có độ dài khác nhau.
vd:
1 2 3 4 5 6 7 8 8 0 8 0
1 4 2 7 3 4 8 6 7 0
--> 1 2 3 4 6 7 0
khi xem phần hướng dẫn thì nó đưa ra thuật toán sau:
thiết lập mảng c [i,j] có m dong n cot
với
gán cho c:=0;
c[i,1]=1 khi b[1] có trong a[i];
c[1,j]=1 khia a[1] co trong b[j];
trường hợp khác
c[i,j]:=max(c[i-1,j],c[i,j-1],c[i-1,j-1] +ord(a[i]=b[j]);
ord(a[i]=b[j])=1 khi a[i]=b[j],0 trong TH còn lại.
anh chị giúp giảng nghĩa thiệt kĩ dùm em tại sao lại như vậy với nha?
à mà mấy anh có tài liệu về vấn đề này không cho em với! thanks trước nha.

PHP Code:

uses crt;
var s1, s2, s_result, s_temp: string;
 i, j, k: integer;
begin
 clrscr;

 write('Nhap chuoi ky tu 1: '); readln(s1);
 write('Nhap chuoi ky tu 2: '); readln(s2);

 s_result:= '';

 for i:=1 to length(s1) do
 begin
   k:=i;
   s_temp:='';

   for j:=1 to length(s2) do
   begin
     if (s1[k] <> s2[j]) then
     begin
       if (length(s_result) < length(s_temp)) then
         s_result := s_temp;

       k:=i;
       s_temp:='';
     end
     else
     begin
       s_temp := s_temp + s1[k];
       inc(k);
     end;
   end;

   if (length(s_result) < length(s_temp)) then
     s_result := s_temp;
 end;

 writeln(s_result);

 readln;
end. 


luuvanson_ML

PHP Code:

uses crt;
var s1, s2, s_result, s_temp: string;
 i, j, k: integer;
begin
 clrscr;

 write('Nhap chuoi ky tu 1: '); readln(s1);
 write('Nhap chuoi ky tu 2: '); readln(s2);

 s_result:= '';

 for i:=1 to length(s1) do
 begin
   k:=i;
   s_temp:='';

   for j:=1 to length(s2) do
   begin
     if (s1[k] <> s2[j]) then
     begin
       if (length(s_result) < length(s_temp)) then
         s_result := s_temp;

       k:=i;
       s_temp:='';
     end
     else
     begin
       s_temp := s_temp + s1[k];
       inc(k);
     end;
   end;

   if (length(s_result) < length(s_temp)) then
     s_result := s_temp;
 end;

 writeln(s_result);

 readln;
end. 


Khác 1 trời 1 vực.
Bài của thớt là dãy con không yêu cầu liên tiếp.
Bài của bạn là dãy con liên tiếp.
Khác quá ấy chứ

P.s: đào mộ hơi quá đấy, bài này 3 năm rồi

Luc moi doc de ma chua xem phan goi y minh nghi lm the nay, mn xem thu co on k nhe, minh chua chay thu
neu goi mang 1 la a co do dai n va mang 2 la b co do dai m thi
if (n>0) and (m>0) then
begin
repeat
for i:=1 to n do
begin
for j:=1 to m do
if a[i]=b[j] then
begin
write(a[i]);
for k:=j to m-1 do
b[k]:=b[k+1];
m:=m-1;
end;
end;
until (m=0) or (i=n);
end;

A minh hoi nham 1 chut, phai la i:=i+1 chu k phai chay for