Follow us on...
Follow us on Twitter Follow us on Facebook Watch us on YouTube

Reviews hay rinh note 4, galaxy V được vi vu Hàn Quốc

Gameshow “Ai Là Triệu Phú” trên VTV đang chờ đón bạn – Tải ngay!

Lời mời tham dự chương trình từ thiện "Giáng Sinh Trong Mắt Em"

Mời anh em tham gia Vn-zoom support team

Chiêm ngưỡng BaoMoi đẹp "tuyệt diệu" trên Windows Phone

Vn-Zoom.com tặng các bạn thành viên may mắn một chiếc Note 4
kết quả từ 1 tới 12 trên 12

Đề tài: day chung dai nhat

  1. #1
    duykhoa_12T's Avatar
    duykhoa_12T vẫn chưa có mặt trong diễn đàn Rìu Vàng
    Tham gia
    Nov 2009
    Đến từ
    Whitehouse
    Bài
    736
    Cảm ơn
    125
    Điểm
    431/149 bài viết

    Exclamation 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.

  2. #2
    Phuochung2807's Avatar
    Phuochung2807 vẫn chưa có mặt trong diễn đàn Rìu Bạc Đôi
    Tham gia
    May 2008
    Đến từ
    HCMC
    Bài
    506
    Cảm ơn
    290
    Điểm
    546/133 bài viết

    Default

    Đâ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õ.

  3. #3
    duykhoa_12T's Avatar
    duykhoa_12T vẫn chưa có mặt trong diễn đàn Rìu Vàng
    Tham gia
    Nov 2009
    Đến từ
    Whitehouse
    Bài
    736
    Cảm ơn
    125
    Điểm
    431/149 bài viết

    Default

    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!

  4. #4
    Phuochung2807's Avatar
    Phuochung2807 vẫn chưa có mặt trong diễn đàn Rìu Bạc Đôi
    Tham gia
    May 2008
    Đến từ
    HCMC
    Bài
    506
    Cảm ơn
    290
    Điểm
    546/133 bài viết

    Default

    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]);

  5. #5
    notname2010's Avatar
    notname2010 vẫn chưa có mặt trong diễn đàn Rìu Bạc Đôi
    Tham gia
    Feb 2010
    Bài
    615
    Cảm ơn
    13
    Điểm
    284/136 bài viết

    Default

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

  6. #6
    duykhoa_12T's Avatar
    duykhoa_12T vẫn chưa có mặt trong diễn đàn Rìu Vàng
    Tham gia
    Nov 2009
    Đến từ
    Whitehouse
    Bài
    736
    Cảm ơn
    125
    Điểm
    431/149 bài viết

    Wink

    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

  7. #7
    Phuochung2807's Avatar
    Phuochung2807 vẫn chưa có mặt trong diễn đàn Rìu Bạc Đôi
    Tham gia
    May 2008
    Đến từ
    HCMC
    Bài
    506
    Cảm ơn
    290
    Điểm
    546/133 bài viết

    Default

    Trích duykhoa_12T View Post
    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....

  8. #8
    duykhoa_12T's Avatar
    duykhoa_12T vẫn chưa có mặt trong diễn đàn Rìu Vàng
    Tham gia
    Nov 2009
    Đến từ
    Whitehouse
    Bài
    736
    Cảm ơn
    125
    Điểm
    431/149 bài viết

    Default

    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ạ?

  9. #9
    luuvanson_ML's Avatar
    luuvanson_ML vẫn chưa có mặt trong diễn đàn Rìu Sắt
    Tham gia
    Oct 2009
    Bài
    141
    Cảm ơn
    15
    Điểm: 1/1 bài viết

    Default Gần giống bài này. nhưng bài này là về chuỗi bạn ak

    Trích duykhoa_12T View Post
    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 
    s1s2s_results_tempstring;
     
    ijkinteger;
    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.

  10. #10
    lamdetien36's Avatar
    lamdetien36 vẫn chưa có mặt trong diễn đàn Rìu Vàng
    Tham gia
    Jun 2013
    Bài
    688
    Cảm ơn
    52
    Điểm
    196/164 bài viết

    Default

    Trích luuvanson_ML View Post
    PHP Code:
    uses crt;
    var 
    s1s2s_results_tempstring;
     
    ijkinteger;
    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

  11. #11
    LumeriJirinmo's Avatar
    LumeriJirinmo vẫn chưa có mặt trong diễn đàn Búa Gỗ
    Tham gia
    Jul 2013
    Bài
    13
    Cảm ơn
    0
    Điểm
    6/6 bài viết

    Default

    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;

  12. #12
    LumeriJirinmo's Avatar
    LumeriJirinmo vẫn chưa có mặt trong diễn đàn Búa Gỗ
    Tham gia
    Jul 2013
    Bài
    13
    Cảm ơn
    0
    Điểm
    6/6 bài viết

    Default

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

 

 

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
  •