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

bài toán dãy con

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

    bài toán dãy con

    Cho dãy gồm : (n < 10000) số a1,a2,a3,...an. Hãy tìm dãy con liên tiếp dài
    nhất có tổng bằng 0.(|ai|<10^9).
    Ví dụ: dãy gồm 5 số 2, 1, -2, 3, -2 thì dãy con liên tiếp dài nhất có tổng bằng
    0 là: 1, -2, 3, -2
    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: bài toán dãy con

    Vì Pascal ko có hash map nên mình nghĩ làm bài này hơi khác với chuẩn một chút.
    - Bạn tạo một mảng S[0..1, 0..10000]. Trong đó: S[0, i] := S[0, i-1] + i và S[1, i] := i.
    - Sau đó sort mảng S này lại ưu tiên theo thứ tự tăng dần của S[0]. Nếu có cùng giá trị S[0] thì sort theo thứ tự tăng dần của S[1].
    - Dựa trên mảng S này sẽ làm việc. Mình đề nghị bạn làm bằng tay, ngẫm nghĩ kỹ xem có thấy đc cách làm ko nhé.
    Độ phức tạp của thuật toá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ừ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50

    Reply: bài toán dãy con

    Mình làm theo cách này có đạt tối ưu bài toán ko bạn...
    HTML Code:
    var a,s:array[0..100] of integer;
    n,i,j,max,vt:integer;
    begin
    write('N=');readln(n);
    for i:=1 to n do
    begin
    write('a[',i,']=');readln(a[i]);
    inc(s[i],s[i-1]+a[i]);
    end;
    for i:=1 to n do
    for j:=0 to i-1 do
    if (s[i]-s[j]=0) and (i-j>max) then
    begin
    max:=i-j;
    vt:=j;
    end;
    for i:=vt+1 to max+vt do write(a[i],' ');
    readln;
    end.
    Mình sợ cách này nếu yêu cầu >= 1s chắc sợ chạy ko nổi..
    các bạn có ý kiến

  5. Đã cảm ơn tuonglong:


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

    Reply: bài toán dãy con

    Câu hỏi của bạn rất hay. Đầu tiên bạn phải hiểu mảng 's' dùng làm gì và thuật toán đang dùng là muốn làm cái gì trước đã. Với bài này, mình kiến nghị làm tay rồi nhìn vào mảng s, xem thử 2 vị trí đánh dấu đoạn có tổng bằng 0 có gì đặc biệt.

  7. 2 thành viên đã cảm ơn tengiday:


  8. #5
    Ðến Từ
    Tỉnh Khác
    Thành Viên Thứ: 105315
    Bài gửi
    13

    Reply: bài toán dãy con

    nhìn nhức đầu đấy để tối suy nghĩ xem nào

  9. #6
    Ðến Từ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50

    Reply: bài toán dãy con

    Mảng s chính là mảng tổng cộng dồn các phần tử
    thuật toán đang dùng duyệt các tổng s
    bằng công thức
    s[u]:= s[u] - s[v-1];
    theo mình cách này duyệt cũng rất lâu.
    Tại mỗi i lại phải duyệt từ 0 -> i-1 để tìm s[u]:= s[u] - s[v-1] nào bằng = 0
    hình nhứ o(n)^2 phải ko bạn mình chưa dk học về tính cái này sai bạn thông cảm
    bạn cho mình biết thuật toán nào để nó tối ưu hơn ko ak...

  10. 2 thành viên đã cảm ơn tuonglong:


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

    Reply: bài toán dãy con

    Trọng tâm của thuật toán là mảng S, khi có đoạn có tổng bằng 0 thì trên S sẽ xuất hiện 2 giá trị bằng nhau. 2 vị trí càng xa nhau thì đoạn càng dài. Mình nói rồi, bạn làm bằng tay, sort lại mảng S (lưu giữ giá trị index) rồi quan sát xem nhé. Cách làm này chính là O(n log n), tốt hơn cách làm của đoạn code trên.
    Thật ra trong C/C++, bài này có thể dùng hash map (cách làm chuẩn), nhưng Pascal ko có cấu trúc dữ liệu này nên mới phải làm kiểu này.

  12. #8
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    Reply: bài toán dãy con

    Xin code tham khảo cách làm với bạn tengiday!

  13. #9
    Ðến Từ
    Đà Nẵng
    Thành Viên Thứ: 377739
    Bài gửi
    135

    Reply: bài toán dãy con

    Bài này làm sao đây mọi người, giúp với