kết quả từ 1 tới 11 trên 11

Viết chương trình nhập vào mảng gồm các số nguyên, chỉ ra đoạn con tăng có tổng lớn nhất

  1. #1
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 353068
    Giới tính: Nam
    Bài gửi
    22

    Viết chương trình nhập vào mảng gồm các số nguyên, chỉ ra đoạn con tăng có tổng lớn nhất

    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: nhờ mọi nguoi giai giup bai quy hoach dong

    Dùng QHĐ, mình sẽ gọi:
    Mã:
    F[i] = tổng lớn nhất của dãy con tăng từ a[1] tới a[i], bao gồm luôn a[i].
    Như vậy, công thức QHĐ sẽ là:
    Mã:
    F[i] = a[i] + max F[j],  khi j < i và a[j] < a[i]
    Khởi tạo mảng F là:
    Mã:
    F[1] = a[1]
    Muốn lấy kết quả, bạn tìm max trên mảng F; để in ra đoạn con thì giả sử F max tại i, như vậy chúng ta chỉ cần duyệt ngược từ i đến khi dãy không còn giảm nữa.
    Độ phức tạp của thuật toán là O(n^2). Nếu n lớn khoảng 10000 thì sẽ phải dùng cấu trúc cây nhị phân mới giải đc bài này còn O(n log n).
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. Đã cảm ơn tengiday:


  4. #3
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 353068
    Giới tính: Nam
    Bài gửi
    22

    Reply: nhờ mọi nguoi giai giup bai quy hoach dong

    nhờ bạn hướng dẫn cụ thể hơn chút được ko ak..mình mới làm quen qhd động thôi ạ ( nhờ bạn ghi code cách tính mảng f dk ko ak vì cái này quan trọng nhất của qhd)

  5. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: nhờ mọi nguoi giai giup bai quy hoach dong

    Mình mới đọc lại đề thì thấy có chỗ chưa rõ: đoạn con tăng dần có cần liên tiếp hay không vậy bạn?
    1) Nếu là đoạn con liên tiếp: bài này không khó, không cần tới qhđ. Chỉ cần 1 vòng lặp là đủ. Pseudo-code của nó đại loại như thế này:
    Mã:
    currentSum = maxSum := a[1];
    index := 1;
    for i := 2 to n do
       begin
          if (a[i - 1] < a[i]) then
             currentSum := currentSum + a[i]
          else
             currentSum := a[i];
          if (currentSum > maxSum) then
             begin
                maxSum = currentSum;
                index := i;
             end;
       end;
    Đây chỉ là pseudo-code, có thể còn lỗi. Thuật toán của mình là vừa đi vừa tính tổng khi nào dãy còn tăng, lưu vào 'currentSum'. Nếu dãy không còn tăng nữa thì reset lại 'currentSum'. Mỗi lần vậy cần so sánh 'currentSum' và 'maxSum'. Biến 'index' là lưu lại vị trí xảy ra tổng max. Sau khi hết vòng lặp rồi thì bạn duyệt ngược từ vị trí index cho tới khi dãy không còn giảm nữa để in ra dãy cần tìm. Thuật toán có độ phức tạp O(n).
    Ví dụ của bạn chính là trường hợp 1 này.

    2) Nếu là đoạn con không liên tiếp: bài này mới cần quy hoạch động. Công thức quy hoạch động giống như post #2 của mình nhé, nhưng mình sửa lại lúc khởi tạo phải là
    Mã:
    F[i] = a[i]
    Đoạn code đại khái như thế này:
    Mã:
    - Khởi tạo F[i] = a[i] cho toàn bộ 1 <= i <= n.
    - Khởi tạo track[i] = -1 cho toàn bộ 1 <= i <= n.   // Mảng track này sẽ lưu lại chỉ số của phần tử đến từ trước nó.
    - index := 1; // Lưu lại vị trí (chỉ số) của F max. Ban đầu giả sử tổng max ở vị trí 1.
    for i := 2 to n do
       begin
          for j := 1 to i - 1 do
             if (a[j] < a[i] and f[i] < a[i] + f[j]) then   // tìm đc dãy con có tổng lớn hơn
                begin
                   f[i] := a[i] + f[j];
                   track[i] := j;   // trước khi đến i phải qua j.
                end;
          if (f[i] > f[index]) then   // có tổng max mới
             index := i;   // tổng max mới ở vị trí i.
       end;
    Sau khi ra khỏi vòng loop, tổng max sẽ đc lưu ở 'f[index]'. Còn muốn in ra dãy con thì chúng ta phải duyệt ngược mảng 'track'. Kết quả sẽ như thế này, ví dụ sơ sơ:
    Mã:
    writeln(a[index]);
    k := track[index];
    while (k <> -1) do
       begin
          writeln(a[k]);
          k := track[k];
       end;
    Độ phức tạp của thuật toán O(n^2). Nếu n tới 10000 thì chạy không nổi. Cái khó phải optimize chính là vòng lặp j (hiện tại là O(n)), khi đó phải dùng cấu trúc cây nhị phân để tìm max trong thời gian O(log n).
    Ví dụ của bạn sẽ ra là 9, 8, 7, 6, 5, 4, 2, 1.

  6. Đã cảm ơn tengiday:


  7. #5
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 353068
    Giới tính: Nam
    Bài gửi
    22

    Reply: nhờ mọi nguoi giai giup bai quy hoach dong

    mình làm theo cách 1 nhờ bạn xem cho mình sai chỗ nào vậy ban
    const fi ='dct.inp';
    fo='dct.out';
    var a: array[1..1000] of longint;
    n: longint;
    tbd,tst,imax: longint;
    procedure nhap;
    var f: text;
    i: longint;
    begin
    assign(f,fi);
    reset(f);
    readln(f,n);
    for i:= 1 to n do
    read(f,a[i]);
    close(f);
    end;
    procedure xuli;
    var i: longint;
    begin
    tbd:=a[1];
    tst:=a[1];
    imax:= 1;
    for i:= 2 to n do
    begin
    if a[i-1]< a[i] then
    tbd:= tbd+a[i]
    else
    tbd:=a[i];
    if tbd>tst then
    tst:= tbd;
    imax:=i;
    end; end;
    procedure xuat;
    var i: longint;
    f: text;
    begin
    assign(f,fo);
    rewrite(f);
    i:=a[imax];
    while i > a[imax-1] do
    begin
    write(f,a[i]);
    i:=a[imax-1]
    end;
    close(f);
    end;
    begin
    nhap;
    xuli;
    xuat;
    end.

  8. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Viết chương trình nhập vào mảng gồm các số nguyên, chỉ ra đoạn con tăng có tổng lớn nhất

    1) Trong procedure xuli, chỗ này bạn cần thêm begin .. end
    Mã:
    if tbd > tst then
       begin
          tst := tbd;
          imax := i;
       end;
    2) Trong procedure xuat, i := imax (đây là chỉ số), và bạn cần so sánh a[i] và a[i - 1], với lại update cho i bằng cách giảm 1 cho i. Bạn lưu ý kiểm tra cận dưới i > 1. Khi in ra thì phải in 'a[i]'. Sau cùng, bạn cần chú ý phần tử cuối cùng nhé.

    Good luck.

  9. Đã cảm ơn tengiday:


  10. #7
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 353068
    Giới tính: Nam
    Bài gửi
    22

    Reply: Viết chương trình nhập vào mảng gồm các số nguyên, chỉ ra đoạn con tăng có tổng lớn nhất

    bạn giúp mình code doan lấy các a[i] dk ko ak minh xoay mãi ma ko pit phải làm sao?
    với lại cho mình hỏi muốn lấy dãy xuôi mình phải làm thế nào vậy bạn?( mình thấy ở đây là lấy ngược dãy thì phải)

  11. #8
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Viết chương trình nhập vào mảng gồm các số nguyên, chỉ ra đoạn con tăng có tổng lớn nhất

    1) Để in ra thì bạn bắt đầu từ vị trí 'index' rồi đi ngược lại. Bạn cứ nghĩ bài này là: cho 1 dãy số và 1 vị trí 'index', in ra dãy con giảm / tăng dần từ 'index'.
    Mã:
    write(a[index]);
    for i:=index-1 downto 1 do
       begin
          if (a[i] >= a[i + 1]) then break;
          write(' ', a[i]);
       end;
    2) Bởi vì cách mình duyệt dãy nên nó in ngược. Nếu muốn in thuận chiều thì có nhiều cách. Ví dụ như có thể đảo vòng 'for' loop trong procedure xuli, đổi lại khởi tạo, và đoạn code in ra dãy. Bạn đã hiểu phần xử lí chính rồi thì có thể suy nghĩ viết ngược lại, xem như 1 cách practice nhé.

  12. Đã cảm ơn tengiday:


  13. #9
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 353068
    Giới tính: Nam
    Bài gửi
    22

    Reply: Viết chương trình nhập vào mảng gồm các số nguyên, chỉ ra đoạn con tăng có tổng lớn nhất

    cảm ơn bạn mình đã text được bài làm theo cách 1 rồi
    phần 2(dãy con không liên tiếp có tổng lớn nhất)
    : có một phần mình thắc mắc nữa muốn hỏi bạn xíu nữa
    1. mình làm phần 2 làm theo qhd(mình text bài làm của bạn : chỗ này mình cảm thấy ko rõ khj chạy bộ text này
    6
    1 2 3 -4 -1 2
    tại sao lại không lấy dãy tăng dần dài nhất là tổng
    6 và dãy là
    1 2 3
    mà lại lấy
    3
    6 1
    2. nếu muốn in dãy con theo chiều thuận ta nên khởi tạo các mảng như thế nào vậy bạn
    nhờ bạn giải thích giùm//

  14. #10
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Viết chương trình nhập vào mảng gồm các số nguyên, chỉ ra đoạn con tăng có tổng lớn nhất

    Trích Nguyên văn bởi tuongsonqt Xem bài viết
    cảm ơn bạn mình đã text được bài làm theo cách 1 rồi
    phần 2(dãy con không liên tiếp có tổng lớn nhất)
    : có một phần mình thắc mắc nữa muốn hỏi bạn xíu nữa
    1. mình làm phần 2 làm theo qhd(mình text bài làm của bạn : chỗ này mình cảm thấy ko rõ khj chạy bộ text này
    6
    1 2 3 -4 -1 2
    tại sao lại không lấy dãy tăng dần dài nhất là tổng
    6 và dãy là
    1 2 3
    mà lại lấy
    3
    6 1
    2. nếu muốn in dãy con theo chiều thuận ta nên khởi tạo các mảng như thế nào vậy bạn
    nhờ bạn giải thích giùm//
    1) Bạn cho mình xem đoạn code thế nào nhé.
    2) Nếu muốn in ngược thì có thể đảo ngược lại trong lúc tính mảng 'f'. Bạn cứ nghĩ chúng ta duyệt ngược từ n, tức là index := n, sau đó tìm dãy con giảm dần có tổng lớn nhất.
    Mã:
    for i := n - 1 downto 1 do
       begin
          for j := i + 1 to n do
             if ........ // chỗ này cần đổi một chút.
                begin
                   .......... // bên trong này không đổi.
                end;
          if ........  // chỗ if này không đổi.
       end;
    Đoạn code lúc truy vết thì cũng ko cần đổi nhé.

  15. Đã cảm ơn tengiday:


  16. #11
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 353068
    Giới tính: Nam
    Bài gửi
    22

    Reply: Viết chương trình nhập vào mảng gồm các số nguyên, chỉ ra đoạn con tăng có tổng lớn nhất

    cảm ơn bạn nhiều nhé mình làm được rồi
    good luck

  17. Đã cảm ơn tuongsonqt: