Kết quả 1 đến 8 của 8
  1. #1
    Ngày tham gia
    Aug 2015
    Bài viết
    0

    Ai giúp mình bài quy hoạch động này với!!!

    Cho một bảng A kích thước m x n (1 <= m, n <= 100), trên đó ghi các số nguyên aij (|aij| <= 100). Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được).
    Input

    Dòng 1: Ghi hai số m, n là số hàng và số cột của bảng.M dòng tiếp theo, dòng thứ i ghi đủ n số trên hàng i của bảng theo đúng thứ tự từ trái qua phải
    Output

    Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được

    Example

    Input:
    5 7
    9 -2 6 2 1 3 4
    0 -1 6 7 1 3 3
    8 -2 8 2 5 3 2
    1 -1 6 2 1 6 1
    7 -2 6 2 1 3 7
    Output:
    41

    Em có làm bài đó như sau mà nó ra có 39 à! Mong mọi người giúp đỡ e ạ
    Mã:
    uses crt;
    var  m,n,i,j:integer;
    a,f:array[0..100,0..100] of integer;
    procedure input;
    var  f:text;
    begin
            assign(f,'d:\pascal\dgdidai1\input.txt');
            reset(f);
            readln(f,n,m);
            for i:=1 to n do
            begin
                    for j:=1 to m do
                    read(f,a[i,j]);
            readln(f);
            end;
    end;
    function max(a,b:integer):integer;
    begin
            if a>b then exit(a) else exit(b);
    end;
    procedure qhd;
    begin
            fillchar(f,sizeof(f),0);
            for i:=1 to n do
            for j:=1 to m do
            f[i,j]:= max(f[i-1,j-1],max(f[i,j-1],f[i+1,j-1]))+a[i,j];
    end;
    procedure rslt;
    var kq:integer;
    begin   kq:=-maxint;
            for i:=1 to n do
            if f[i,m]>kq then kq:=f[i,m];
            write(kq);
    end;
    begin
    clrscr;
            input;
            qhd;
            rslt;
    readln;
    end.

  2. #2
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    Trong procedue qhd, bạn thử đổi thứ tự của 2 dòng loop i và j lại nhé. Bởi vì điền giá trị cho f[i,j] là theo cột, cho nên phải duyệt từng hàng i cho mỗi cột j. Ngoài ra, bạn nên tăng giá trị lên 101, chứ ko phải 100.

    Cải tiến thêm: cột j của mảng f chỉ phụ thuộc vào cột j-1 của nó và giá trị a[i,j] mà thôi. Như vậy, thay vì lưu mảng f 100 x 100, chúng ta chỉ cần 1 mảng m dòng 2 cột rồi đổi qua đổi lại. Cách làm này sẽ đỡ hao bộ nhớ hơn (thay vì lưu 1 mảng 10000 phần từ thì chỉ cần lưu 1 mảng 200 phần tử).

    Mã:
    begin
            fillchar(f,sizeof(f),0);
            t := 0;
            for j:=1 to m do
                 begin
                      for i:=1 to n do
                           f[i,t]:= max(f[i-1,1-t],max(f[i,1-t],f[i+1,1-t]))+a[i,j];
                      t:= 1-t;
                 end;
    end;

  3. #3
    Ngày tham gia
    Nov 2015
    Bài viết
    4
    [IMG]images/smilies/troll2/think.gif[/IMG] đọc 1 hồi mới hiểu đề dc
    tổng lớn nhất sẽ = max của mỗi cột + lại với nhau
    cầy xây dụng hàm tính max cho mỗi cột rồi lấy tổng thôi

  4. #4
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    Trích dẫn Gửi bởi Richard Annowit
    Cảm ơn bạn nhìu nha...Mình đổi vị trí i với j thì được nhưng lại không hiểu tại sao lại phải đổi...đó h mình làm mảng 2 chìu thì chỉ viết như vậy thôi
    Khi chúng ta viết như thế này
    Mã:
    for i:=1 to m do
       for j:=1 to n do
          a[i,j] ....
    tức có nghĩa là đang duyệt mảng theo từng dòng từ trên xuống dưới, mỗi dòng từ trái sang phải.
    Khi chúng ta viết như thế này
    Mã:
    for j:=1 to n do
       for i:=1 to m do
          a[i,j] ...
    tức có nghĩa là đang duyệt mảng theo từng cột từ trái sang phải, mỗi cột từ trên xuống dưới.
    Vì yêu cầu của bài toán: đi từ cột trái sang cột phải, nên phải duyệt mảng theo cột (phải có giá trị của cột thứ j rồi mới đi tiếp sang cột j+1). Bạn chạy theo vòng loop ghi rõ giá trị của i và j ra sẽ thấy rõ hơn.

  5. #5
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    Trích dẫn Gửi bởi tengiday
    Khi chúng ta viết như thế này
    <div class="bbcode_container">
    <div class="bbcode_description">Mã:
    tức có nghĩa là đang duyệt mảng theo từng cột từ trái sang phải, mỗi cột từ trên xuống dưới.
    Vì yêu cầu của bài toán: đi từ cột trái sang cột phải, nên phải duyệt mảng theo cột (phải có giá trị của cột thứ j rồi mới đi tiếp sang cột j+1). Bạn chạy theo vòng loop ghi rõ giá trị của i và j ra sẽ thấy rõ hơn.</div>

    </div>
    </div>
    </div>Sao bác tengiday giỏi thế, biết cả phần mềm, phần cứng kèm theo lập trình cũng rành nữa [IMG]images/smilies/funny/***y_girl.gif[/IMG]

  6. #6
    Ngày tham gia
    Nov 2015
    Bài viết
    5
    Trích dẫn Gửi bởi tengiday
    Trong procedue qhd, bạn thử đổi thứ tự của 2 dòng loop i và j lại nhé. Bởi vì điền giá trị cho f[i,j] là theo cột, cho nên phải duyệt từng hàng i cho mỗi cột j. Ngoài ra, bạn nên tăng giá trị lên 101, chứ ko phải 100.

    Cải tiến thêm: cột j của mảng f chỉ phụ thuộc vào cột j-1 của nó và giá trị a[i,j] mà thôi. Như vậy, thay vì lưu mảng f 100 x 100, chúng ta chỉ cần 1 mảng m dòng 2 cột rồi đổi qua đổi lại. Cách làm này sẽ đỡ hao bộ nhớ hơn (thay vì lưu 1 mảng 10000 phần từ thì chỉ cần lưu 1 mảng 200 phần tử).

    <div class="bbcode_container">
    <div class="bbcode_description">Mã:
    </div>
    </div>Cảm ơn bạn nhìu nha...Mình đổi vị trí i với j thì được nhưng lại không hiểu tại sao lại phải đổi...đó h mình làm mảng 2 chìu thì chỉ viết như vậy thôi

  7. #7
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    Trích dẫn Gửi bởi tengiday
    Khi chúng ta viết như thế này
    <div class="bbcode_container">
    <div class="bbcode_description">Mã:
    tức có nghĩa là đang duyệt mảng theo từng cột từ trái sang phải, mỗi cột từ trên xuống dưới.
    Vì yêu cầu của bài toán: đi từ cột trái sang cột phải, nên phải duyệt mảng theo cột (phải có giá trị của cột thứ j rồi mới đi tiếp sang cột j+1). Bạn chạy theo vòng loop ghi rõ giá trị của i và j ra sẽ thấy rõ hơn.</div>

    </div>
    </div>
    </div>À...mình hiểu rồi..mà bạn ơi...Bạn có tài liệu quy hoạch động nào hay không hay là rèn luyện tư duy j đó cho mình xin với

  8. #8
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    Trích dẫn Gửi bởi Richard Annowit
    À...mình hiểu rồi..mà bạn ơi...Bạn có tài liệu quy hoạch động nào hay không hay là rèn luyện tư duy j đó cho mình xin với
    Cái này thì mình ko có; mình học QHD đã 6-7 năm về trước rồi. Mình nghĩ có thể tìm trên mạng nhiều bài tập QHD tương tự (Google ra rất nhiều).
    Nếu bạn muốn đọc tài liệu tiếng Anh thì có thể search cụm từ dynamic programming.

 

 

Quyền viết bài

  • 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ể Sửa bài viết của mình
  •  
Múi giờ GMT +7. Bây giờ là 06:24 PM.
Diễn đàn sử dụng vBulletin® Phiên bản 4.2.5.
Bản quyền của 2024 vBulletin Solutions, Inc. Tất cả quyền được bảo lưu.
Ban quản trị không chịu trách nhiệm về nội dung do thành viên đăng.