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
 

tengiday

Happy life
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).
 
Mình làm theo cách này có đạt tối ưu bài toán ko bạn...
HTML:
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
 

tengiday

Happy life
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.
 
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:= s - 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:= s - 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...
 

tengiday

Happy life
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.
 

thanhhiepvo2003

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

45Wd06.png
 
Top