Cựu Học Sinh Lê Quý Đôn - Long An
Trang 1/3 1 23 >
Hiển thị 40 bài trong cũng một trang

Cựu Học Sinh Lê Quý Đôn - Long An (http://www.lqdlongan.com/forum/index.php)
-   Tin học phổ thông (http://www.lqdlongan.com/forum/forumdisplay.php?f=117)
-   -   Một số bài toán cần nắm trong tin học (http://www.lqdlongan.com/forum/showthread.php?t=7904)

duyhung123abc 28-07-2009 10:30 AM
Một số bài toán cần nắm trong tin học
 
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á :x

duyhung123abc 28-07-2009 10:32 AM
Ðề: Một số bài toán cần nắm trong tin học
 
Một bài toán về dãy số

Trích:
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 30-07-2009 05:54 PM
Ðề: Một số bài toán cần nắm trong tin học
 
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.
Code:
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 :D

johnceduy 30-07-2009 09:24 PM
Ðề: Một số bài toán cần nắm trong tin học
 
Đây là code của em, nếu thíu xót hay tối tăm chỗ nào nhờ anh góp ý :teeth_smile:
Code:
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 30-07-2009 09:37 PM
Ðề: Một số bài toán cần nắm trong tin học
 
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 30-07-2009 09:41 PM
Ðề: Một số bài toán cần nắm trong tin học
 
dạ rồi ạ, khi T tăng vọt quá m thì nó dừng lại ngay, không lố đâu :D

duyhung123abc 30-07-2009 10:09 PM
Ðề: Một số bài toán cần nắm trong tin học
 
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ý :D

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

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 31-07-2009 08:47 PM
Ðề: Một số bài toán cần nắm trong tin học
 
Trích:
Nguyên văn bởi duyhung123abc (Post 59128)
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.
Code:
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 :D
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 31-07-2009 10:05 PM
Ðề: Một số bài toán cần nắm trong tin học
 
Em thấy giới hạn n cao quá liệu có ai nhập nổi để test? :teeth_smile:

myhanh 01-08-2009 10:08 AM
Ðề: Một số bài toán cần nắm trong tin học
 
Trích:
Nguyên văn bởi johnceduy (Post 59174)
Em thấy giới hạn n cao quá liệu có ai nhập nổi để test? :teeth_smile:
Người ta test bằng máy em à!


Múi giờ GMT +7. Hiện tại là 05:52 PM.
Trang 1/3 1 23 >
Hiển thị 40 bài trong cũng một trang

Website sử dụng phần mềm vBulletin phiên bản 3.6.8
do Công ty TNHH Jelsoft giữ bản quyền từ 2000 - 2024.
Hội CHS Lê Quý Đôn-Long An giữ bản quyền nội dung của website này