Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    Cho một dãy X[1..n]. Tìm dãy con liên tiếp cạnh nhau của X có tổng lớn nhất.

    Ban QT: Kể cũng vui thật.


    ================

    Admin


    Quản trị viên
    Quản trị viên
    Thử xem code này được không? Ở đây chỉ viết gợi ý, Khách viếng thăm hãy hoàn thiện thêm input, output nha. Tôi thì cố gắng thi lấy 5 điểm thôi, còn bài dạng này nhường các bạn giỏi, cũng viết gợi ý để các bạn làm cho nó tốt nha:

    1. Mô hình
    Cho dãy X1, X2,.. Xn. Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy.
    Đặc trưng:
    i) Các phần tử trong dãy kết quả chỉ xuất hiện 1 lần. Vì vậy phương pháp làm là ta sẽ dùng vòng FOR duyệt qua các phần tử Xi trong dãy, các phần tử trong dãy có thể được chọn nhiều lần nên ta thực hiện bằng phương pháp cho giá trị cần quy đổi tăng dần từng đơn vị.
    ii) Thứ tự của các phần tử được chọn phải được giữ nguyên so với dãy ban đầu.
    Đặc trưng này có thể mất đi trong một số bài toán khác tùy vào yêu cầu cụ thể. Chẳng hạn bài Tam giác bao nhau.

    2. Công thức quy hoạch động QHĐ
    Hàm mục tiêu : f = độ dài dãy con.
    Vì độ dài dãy con chỉ phụ thuộc vào 1 yếu tố là dãy ban đầu nên bảng phương án là bảng một chiều. Gọi L(i) là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ X1 đến Xi và phần tử cuối cùng là Xi.
    Nhận xét với cách làm này ta đã chia 1 bài toán lớn (dãy con của n số) thành các bài toán con cùng kiểu có kích thước nhỏ hơn (dãy con của dãy i số). Vấn đề là công thức truy hồi để phối hợp kết quả của các bài toán con.
    Ta có công thức QHĐ để tính L(i) như sau:
    • L(1) = 1. (Hiển nhiên)
    • L(i) = max (1, L(j)+1 với mọi phần tử j: 0 < j < i và Xj ≤ Xi).
    Tính L(i) : phần tử đang được xét là Xi . Ta tìm đến phần tử Xj < Xi có L(j) lớn nhất. Khi đó nếu bổ sung Xi vào sau dãy con ...Xj ta sẽ được dãy con tăng dần dài nhất xét từ X1...Xi.
    A)
    Dãy con có nhiều phần tử tăng nhất:
    FOR i := 1 TO n DO
              L[i] := 1;
              FOR j := 1 TO i – 1 DO
                        IF (X[j] ≤ X[i]) & (L[i] < L[j] + 1) THEN L[i] := L[j] + 1;
    B)
    Dãy con có tổng lớn nhất:
    FOR i := 1 TO n DO
              S[i] := X[i];
              FOR j := 1 TO i – 1 DO
                        IF(X[j] ≤ X[i]) & (S[i] < S[j] + X[i]) THEN S[i] := S[j] + X[i];

    Các bài khác tương tự... Tôi đưa đường link để mọi người có thể down về xem bằng cách nháy vào đây, ở đây có hầu như các loại toán quy hoạch động cho thí sinh thích đạt 10 điểm, ai không thích được 10 điểm thì đừng có mà nháy vào nha.



    Được sửa bởi Admin ngày Tue Aug 09, 2011 10:54 am; sửa lần 1.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    max := x[1];
    io := 1; jo := 1;

    FOR i := 1 TO n DO
              S := 0;
              FOR j := i TO n DO
                        S := S + a[j]; /* Tính tổng từ x[i] đến x[j] */
                        IF S > max THEN
                                  max := S;
                                  io := i; jo := j;

    Output a[io],..., a[jo]; max;


    ================
    [You must be registered and logged in to see this image.]

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    Đúng như anh Admin nói những bài này giành cho những người khá và muốn kiếm điểm 10.
    Bài toán anh Admin đưa ra khác hẳn bài này. Vả lại anh Admin viết giả mã sai rồi, không đúng. Ah nghiên cứu và viết lại nhé.
    Giải thuật của anh Phương sai rồi. Ví dụ: 13 -15 2 3 4 7 8 0 -5. Anh dùng giải thuật của anh xem kết quả thế nào.

    Ban QT: Down File Admin gửi link kèm bài viết trên, đã rõ hết rồi


    ================

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    Chú chưa thử bài của anh mà dám phán luôn là sai, bựa nhân quá.

    Anh chạy tay cho chú xem thế nào nhé.

    Max= 13;

    i= 1
    s= 0;
    j= 1, s= 13
    j= 2, s= -2
    j= 3, s= 0
    j= 4, s= 3
    j= 5, s= 7
    j= 6, s= 14, max= 14
    j= 7, s= 22, max= 22
    j= 8, s= 22
    j= 9, s= 17


    i= 2;
    s= 0;
    j= 2, s= -15
    j= 3, s= -13
    j= 4, s= -10
    j= 5, s= -6
    j= 6, s= 1
    j= 7, s= 9
    j= 8, s= 9
    j= 9, s= 4


    i= 3;
    s= 0;
    j= 3, s= 2
    j= 4, s= 5
    j= 5, s= 9
    j= 6, s= 16
    j= 7, s= 24, max= 24
    j= 8, s= 24
    j= 9, s= 19

    tương tự cho i=4,5,6,7,8,9 nhé. Bởi vì nhìn qua cũng thấy là max=24 rồi, trong trường hợp này tương ứng với i=3, j=7, có nghĩa là tổng dãy a3, a4, a5, a6, a7 là lớn nhât.


    ================
    [You must be registered and logged in to see this image.]

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    Uh. Đúng rồi. Sorry a.Phương nhé. Em nhìn lướt qua, không nhìn kỹ. Cách của a cũng được. Bản chất là anh duyệt hết. Cách này được 0.5 điểm. Còn hơn là không làm được.

    Để được 1 điểm bài này phải dùng quy hoạch động. Dựa vào tính chất của dãy.


    ================

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Have a free blog with Sosblogs