Go Back   Cựu Học Sinh Lê Quý Đôn - Long An > :: Góc Học Tập :: > Tin học > Tin học phổ thông

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

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

this thread has 25 replies and has been viewed 15298 times

Gởi Ðề Tài Mới Trả lời
 
Ðiều Chỉnh Xếp Bài
Old 28-07-2009, 11:30 AM   #1
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default 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á

thay đổi nội dung bởi: duyhung123abc, 30-07-2009 lúc 07:07 PM.
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 28-07-2009, 11:32 AM   #2
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: 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

thay đổi nội dung bởi: duyhung123abc, 28-07-2009 lúc 12:00 PM.
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 30-07-2009, 06:54 PM   #3
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: 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

thay đổi nội dung bởi: duyhung123abc, 30-07-2009 lúc 07:05 PM.
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Đã có thành viên gửi lời cám ơn đến duyhung123abc vì bạn đã đăng bài:
thieftran A07 (04-09-2009)
Old 30-07-2009, 10:24 PM   #4
Hồ sơ
johnceduy
Senior Member
 
johnceduy's Avatar
 
Tham gia ngày: Dec 2008
Cư ngụ: Lê Quý Đôn
Số bài viết: 115
Tiền: 25
Thanks: 54
Thanked 83 Times in 18 Posts
johnceduy is on a distinguished road
Post Ðề: 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 ý
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.
__________________
Nhớ, nhớ, nhớ quá đi!


thay đổi nội dung bởi: johnceduy, 30-07-2009 lúc 11:20 PM. Lý do: a
johnceduy is offline   Trả Lời Với Trích Dẫn
Old 30-07-2009, 10:37 PM   #5
Hồ sơ
khanhan2006_2009
Senior Member
 
khanhan2006_2009's Avatar
 
Tham gia ngày: Sep 2007
Cư ngụ: Nhà
Số bài viết: 827
Tiền: 25
Thanks: 135
Thanked 392 Times in 190 Posts
khanhan2006_2009 is on a distinguished road
Default Ðề: 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.
__________________
"hcmiu.edu.vn"
khanhan2006_2009 is offline   Trả Lời Với Trích Dẫn
Old 30-07-2009, 10:41 PM   #6
Hồ sơ
johnceduy
Senior Member
 
johnceduy's Avatar
 
Tham gia ngày: Dec 2008
Cư ngụ: Lê Quý Đôn
Số bài viết: 115
Tiền: 25
Thanks: 54
Thanked 83 Times in 18 Posts
johnceduy is on a distinguished road
Default Ðề: 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
__________________
Nhớ, nhớ, nhớ quá đi!

johnceduy is offline   Trả Lời Với Trích Dẫn
Old 30-07-2009, 11:09 PM   #7
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: 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ý

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

thay đổi nội dung bởi: duyhung123abc, 30-07-2009 lúc 11:22 PM.
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 31-07-2009, 09:47 PM   #8
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: Một số bài toán cần nắm trong tin học

Trích:
Nguyên văn bởi duyhung123abc View Post
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
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)
__________________
Quyết tâm thành pro
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 31-07-2009, 11:05 PM   #9
Hồ sơ
johnceduy
Senior Member
 
johnceduy's Avatar
 
Tham gia ngày: Dec 2008
Cư ngụ: Lê Quý Đôn
Số bài viết: 115
Tiền: 25
Thanks: 54
Thanked 83 Times in 18 Posts
johnceduy is on a distinguished road
Default Ðề: 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?
__________________
Nhớ, nhớ, nhớ quá đi!

johnceduy is offline   Trả Lời Với Trích Dẫn
Old 01-08-2009, 11:08 AM   #10
Hồ sơ
myhanh
 
myhanh's Avatar
 
Tham gia ngày: Dec 2004
Cư ngụ: Love Planet
Tuổi: 43
Số bài viết: 7,404
Tiền: 0
Thanks: 2,119
Thanked 5,463 Times in 2,040 Posts
myhanh is on a distinguished road
Default Ðề: Một số bài toán cần nắm trong tin học

Trích:
Nguyên văn bởi johnceduy View Post
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 à!
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog
myhanh is offline   Trả Lời Với Trích Dẫn
Trả lời


Ðiều Chỉnh
Xếp Bài

Quyền Sử Dụng Ở Diễn Ðàn
Bạn không được quyền gởi bài
Bạn không được quyền gởi trả lời
Bạn không được quyền gởi kèm file
Bạn không được quyền sửa bài

vB code đang Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt
Chuyển đến

Chủ đề tương tự
Ðề tài Người Gởi Chuyên mục Trả lời Bài mới gởi
Muốn con thông minh, cha mẹ phải sáng tạo trong trò chơi nhk Chuyện trẻ thơ 0 16-04-2009 12:44 PM
Rối loạn giấc ngủ peanux Chia sẻ kinh nghiệm 0 11-03-2008 08:45 AM
Chúng Ta trong Thế giới phẳng Gem ..:: Thảo luận nghiêm túc ::.. 2 09-09-2007 04:44 PM
Ufo VÀ SỰ SỐng NgoÀi TrÁi ĐẤt LeGiang Thiên văn học 0 25-05-2007 11:13 AM


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.
Múi giờ GMT +7. Hiện tại là 01:11 PM.

Hội CHS Lê Quý Đôn-Long An giữ bản quyền nội dung của website này

Tự động[F9]TELEX VNI VIQR VIQR* TắtKiểm chính tảDấu cũ
phan mem quan ly ban hang | thuê vps