Một số bài toán cần nắm trong tin học

[duyhung123abc]

Topic này đc mở ra cho tất cả những ai thích lập trình, không phân biệt già trẻ. Em nhỏ thì học hỏi, mấy anh lớn thì truyền kinh nghiệm nhá

[duyhung123abc]

Một bài toán về dãy số

Cho một dãy gồm n số nguyên dương
a[1] a[2] a[3] … a[n]
với ai>0

Một dãy con liên tiếp của dãy trên là:
a[i] a[i+1] a[i+2] … a[j]
với (1<=i<=j<=N)

Hãy in ra độ dài dãy con liên tiếp dài nhất của dãy số trên có tổng các phần tử của dãy con <=M.

Giới hạn: N<=100000, M<=10^9

*Input: nhập từ file seq.inp với:
_ dòng đầu tiên chứa 2 số N, M
_ N dòng tiếp theo, dòng thứ i chứa duy nhất 1 số nguyên là giá trị ptử thứ i.

*Output: xuất ra file seq.out:
_ Gồm 1 dòng duy nhất chứa số phần tử của dãy con liên tiếp dài nhất

VD:
*input:
7 6
1 2 3 4 3 2 1
*output:
3

[duyhung123abc]

Bài toán này có 1 cách làm đơn giản là dùng 2 biến chạy i,j với j>=i. Với mỗi cặp i,j ta kiểm tra xem đoạn con liên tiếp từ phần tử thứ i đến phần tử thứ j có thỏa điều kiện <=M hay ko, nếu thỏa thì tính độ dài và cập nhật để thu đc độ dài đoạn con dài nhất.

kq:=0; {biến kq lưu độ dài lớn nhất tìm được, ban đầu gán kq=0}
for i:=1 to n-1 do
  for j:=i to n do
    begin
      tong:=0;
      for k:=i to j do tong:=tong+a[k]; {tính tổng các số từ i đến j}
      if (tong<=m) and (j+1-i>kq) then kq=j+1-i; (*)
    end;
writeln(kq);

trong đó phần được đánh dấu (*) diễn tả: "kiểm tra 2 điều kiện: tổng của dãy số phải <=m và chiều dài đoạn từ i đến j phải lớn hơn chiều dài lớn nhất tìm được trước đó"

Nhưng với cách làm này rõ ràng không quan trọng a[i] âm hay dương, nhưng đề bài lại cho dãy số dương, nên ta có một cách làm khác có thể tăng tốc hơn rất nhiều. Cách này sẽ đc post sau

[johnceduy]

Đây là code của em, nếu thíu xót hay tối tăm chỗ nào nhờ anh góp ý

Begin
     Write('Nhap vao n:');readln(n);
     For i:=1 to n do begin
     Write ('Nhap vao a[',i,']:');readln(a[i]);
     end;
     Write('Nhap vao m:');readln(m);
For i:=1 to n-1 do begin
 T:=a[i]+a[i+1];
 If T<=m then begin
 dem:=2;
 For j:=1 to n-1-i do begin
 If a[i+1+j]>0 then begin
 T:=T+a[i+1+j];
 If T<=m then dem:=dem+1
else break;
 end;
 end;
 end
else break;
 b[i]:=dem;
end;
max:=0;
For i:=1 to n do
 If b[i]>max then max:=b[i];
write('Dai nhat:',max);
readln;
end.

[khanhan2006_2009]

Bài này đã test thử trong pascal chưa.
A nghĩ là ko đúng vì biến T chỉ toàn cộng vào....nói chung là nhìn ko có lý lắm.

[johnceduy]

dạ rồi ạ, khi T tăng vọt quá m thì nó dừng lại ngay, không lố đâu

[duyhung123abc]

Bài của em sẽ sai trong trường hợp khi cộng đến số thứ n mà tổng vẫn <=M, thì j sẽ tăng lên tiếp. Do pascal mặc định các số ban đầu của mảng =0, nên biến j sẽ chạy đến giá trị (j=n) và độ dài max có thể lên đến (n+2) => vô lý

Cám ơn sự hợp tác của pác An

Tuy nhiên cách này chỉ giải đc với n<=1000. Có ai nghĩ ra cách giải quyết với n<=100 000 chưa

[duyhung123abc]

Nguyên văn bởi duyhung123abc

Bài toán này có 1 cách làm đơn giản là dùng 2 biến chạy i,j với j>=i. Với mỗi cặp i,j ta kiểm tra xem đoạn con liên tiếp từ phần tử thứ i đến phần tử thứ j có thỏa điều kiện <=M hay ko, nếu thỏa thì tính độ dài và cập nhật để thu đc độ dài đoạn con dài nhất.

kq:=0; {biến kq lưu độ dài lớn nhất tìm được, ban đầu gán kq=0}
for i:=1 to n-1 do
  for j:=i to n do
    begin
      tong:=0;
      for k:=i to j do tong:=tong+a[k]; {tính tổng các số từ i đến j}
      if (tong<=m) and (j+1-i>kq) then kq=j+1-i; (*)
    end;
writeln(kq);

trong đó phần được đánh dấu (*) diễn tả: "kiểm tra 2 điều kiện: tổng của dãy số phải <=m và chiều dài đoạn từ i đến j phải lớn hơn chiều dài lớn nhất tìm được trước đó"

Nhưng với cách làm này rõ ràng không quan trọng a[i] âm hay dương, nhưng đề bài lại cho dãy số dương, nên ta có một cách làm khác có thể tăng tốc hơn rất nhiều. Cách này sẽ đc post sau

Với cùng cách tiếp cận trên, có thể giảm xuống còn 2 vòng lặp lồng nhau chứ không cần đến 3 vòng lặp. Nhận xét là ta xét cặp (i,j-1) trước và ngay sau đó xét tới cặp (i,j), nên ta có thể tính tổng cặp (i,j) dựa và tổng cặp (i,j-1). Gọi x là tổng của (i,j-1) thì tổng của (i,j) là (x + a[j]). Ta chuyển độ phức tạp từ O(N^3) xuống còn O(N^2)

[johnceduy]

Em thấy giới hạn n cao quá liệu có ai nhập nổi để test?

[myhanh]

Nguyên văn bởi johnceduy

Em thấy giới hạn n cao quá liệu có ai nhập nổi để test?

Người ta test bằng máy em à!