Vn-Zoom Việt Nam Phiên bản Beta -
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.
-
Cách mạng mua sắm giảm giá cực sốc Mưa Sale Băng giảm giá cực tốt *** Bủng Nổ Cơn lốc công nghệ -
-
Đâ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
Thay đổi nội dung bởi duykhoa_12T; 10-03-2010 lúc 12:04.
Lý do: Hệ thống nhập bài tự động
-
-
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ạ?
-
-
Gần giống bài này. nhưng bài này là về chuỗi bạn ak
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.
Thay đổi nội dung bởi luuvanson_ML; 05-08-2013 lúc 21:40.
-
-
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
-
-
Cách mạng mua sắm giảm giá cực sốc Mưa Sale Băng giảm giá cực tốt *** Bủng Nổ Cơn lốc công nghệ
Quyền sử dụng
- Bạn không thể gửi chủ đề mới
- Bạn không thể gửi trả lời
- Bạn không thể gửi file đính kèm
- Bạn không thể tự sửa bài viết của mình
-
Quy định và Điều khoản [V-Z] | |