SKKN Hướng dẫn học sinh rèn luyện kỹ năng giải các bài toán về dãy con liên tiếp

MỤC LỤC
Mở đầu.1
1.1. Lý do chọn đề tài...1
1.2. Mục đich nghiên cứu.1
1.3. Đối tượng nghiên cứu1
1.4. Phương pháp nghiên cứu...1
Nội dung sáng kiến kinh nghiệm.2
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm..2
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm...2
2.3. Các giải pháp đã sử dụng để giải quyết vấn đề.....................3
2.3.1 Cung cấp lý thuyết về chuyên đề dãy con liên tiếp.......3
2.3.2 Viết chương trình cho 4 bài tập cơ bản.........................................4
2.3.3 Làm các bài tập thực tế để vận dụng, cải tiến, hiệu chỉnh và nâng cấp chương trình 8
2.3.4 Giao bài tập về nhà..18
2.4. Hiệu quả của sáng kiến kinh nghiệm đối với hoạt động giáo dục, với bản thân, đồng nghiệp và nhà trường..19
Kết luận, kiến nghị.........................................................................................20
Mở đầu
Lý do chọn đề tài
Trong chương trình Tin học lớp 11, nội dung kiến thức về mảng một chiều trang bị cho học sinh chỉ bao gồm 2 tiết lí thuyết và 1 tiêt bài tập và 4 tiết thực hành. Vì vậy, lượng kiến thức và thời lượng đó đó chưa đủ để học sinh có thể vận dụng vào giải các bài tập liên quan đến các dãy con liên tiếp khi biểu diễn dãy bằng mảng một chiều. Rèn luyện tư duy , kỹ năng và tác phong lập trình có vai trò đặc biệt trong khi bỗi dưỡng học sinh giỏi môn tin học ở trường phổ thông. Hiệu quả của việc rèn luyện tư duy, kỹ năng và tác phong lập trình là động lực giúp học sinh nắm vững kiến thức, phát triển tư duy, hình thành kỹ năng và kỹ xảo. Từ đó có khả năng thích ứng khi đứng trước một vấn đề cần giải quyết. Học sinh cũng thấy được mỗi thuật toán như là một quá trình suy luận, tư duy của học sinh mà phương pháp tìm thuật toán không chỉ phụ thuộc vào đặc điểm của bài toán mà còn phụ thuộc tố chất tâm lý của bản thân người xây dựng thuật toán.
Thực tế cho thấy có những học sinh có tố chất tốt, xong do không nắm vững được khái niệm dãy con mà đề bài đưa ra và cách thức để bước đầu có thể xử lí bài toán thì cũng không giải quyết được bài toán. Nhưng có những học sinh chỉ có tố chất khá, xong nắm vững được khái niệm và quy luật của dãy con, thêm vào đó một niềm đam mê môn học thì các em hoàn toàn vẫn có thể đạt được hiệu quả cao khi giải quyết các bài toán liên quan đến dãy con liên tiếp. V	ì lí do đó nên tôi chọn đề tài: “Hướng dẫn học sinh rèn luyện kỹ năng giải các bài toán về dãy con liên tiếp” để nghiên cứu.
Mục đích nghiên cứu
Nghiên cứu một số vấn đề lý thuyết và thực tiễn việc rèn luyện cho học sinh các kỹ năng giải các bài toán về dãy con liên tiếp nhằm bồi dưỡng năng lực cũng như kỹ năng lập trình, góp phần nâng cao chất lượng bồi dưỡng học sinh giỏi môn Tin học ở trường phổ thông Hoằng Hóa 3. 
Đối tượng nghiên cứu
Đối tượng nghiên cứu: kỹ năng giải các bài toán về dãy con liên tiếp đối với môn tin học 11 của học sinh THPT.
Khách thể nghiên cứu: Học sinh thuộc đội tuyển học sinh giỏi môn Tin học của 
 trường THPT Hoằng Hóa 3
Phương pháp nghiên cứu
- Phương pháp nghiên cứu lý luận: Nghiên cứu các tài liệu, sách báo.
- Phương pháp điều tra thực tiễn: Quan sát việc học của học sinh trong quá trình khai thác các bài tập sách giáo khoa, sách bài tập và các đề thi học sinh giỏi.
- Phương pháp thực nghiệm sư phạm
2. Nội dung sáng kiến kinh nghiệm
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm
- Cơ sở tâm lý học:
+ Đặc điểm nhận thức của học sinh đối với môn Tin học:
Đối với khối THPT, hiện nay phần lớn học sinh coi bộ môn Tin học là môn học phụ, không quan tâm cho lắm, vẫn còn có một vài học sinh có hứng thú với môn Tin học. Từ số lượng ít ỏi đó vẫn có cơ hội để người giáo viên tìm ra các học sinh cho đội tuyển học sinh giỏi của mình.
+ Tư duy của học sinh:
Thông thường những học sinh có kỹ năng lập trình khá, giỏi là những em có kiến thức Toán học khá, giỏi, xong điều ngược lại thì chưa hẳn, lý do rất đơn giản là khả năng vận dụng kiến thức vào để giải quyết vấn đề khi giải quyết bài toán Tin học. Chẳng hạn, khi học giải bài tập môn toán các em có thể học theo dạng 1, dạng 2 nhưng trong tin học thì một bài toán có thể là sự kết hợp của nhiều bài toán cơ bản khác nhau.
Ở các em học sinh khối THPT thì môn lập trình Pascal các em bước đã làm quen nhưng không chú trọng nên khả năng tư duy vẫn còn hạn chế nên việc phân tích để hiểu được bản chất của vấn đề là rất khó. 
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm
- Thực trạng công tác bồi dưỡng học sinh giỏi môn Tin học hiện nay.
Thực tế đa số học sinh rất lúng túng về phương pháp cho loại toán này bởi vì trong sách giáo khoa hay sách bài tập không có nhiều bài tập loại này nhưng lại có trong đề thi học sinh giỏi những năm gần đây khiến cho học sinh rất bối rối về phương pháp. Một số học sinh tham khảo một số code về các bài toán liên quan đến dãy con trên mạng nhưng học sinh cũng khó hiểu và dẫn đến có thói quen lập trình thụ động, không tự nhiên. Điều đó làm giảm đi hứng thú với môn học.
 Qua những năm gần đây khi bồi dưỡng học sinh giỏi môn Tin học tôi nhận thấy mảng kiến thức về dãy con liên tiếp là loại bài tập khá thú vị. Do đó tôi lựa chọn đề tài này để nghiên cứu và trình bày. Bởi việc giúp các em tìm ra các cách giải cho loại bài tập này giúp các em rất tốt trong quá trình học và rèn luyện kỹ năng lập trình.
- Những thuận lợi và khó khăn:
+ Thuận lợi:
- Công tác bồi dưỡng học sinh giỏi hiện nay đối với môn Tin học đã được nhà trường quan tâm chỉ đạo sát sao đặc biệt là đã có những phần thưởng có tính khích lệ đối với giáo viên và học sinh hơn trước.
+ Khó khăn:
- Môn tin học ít có cơ hội chọn được học sinh tốt nhất.
- Phụ huynh học sinh cũng không thích cho con em mình vào đội tuyển mon Tin học vì sợ ảnh hưởng đến việc học và ôn thi Đại học.
2.3. Các giải pháp đã sử dụng để giải quyết vấn đề
2.3.1 Cung cấp lý thuyết về chuyên đề dãy con liên tiếp
- Đưa ra khái niệm dãy con: Dãy con là dãy các phần tử liên tục thuộc một dãy cho trước thỏa mãn một tính chất nào đó (ở đây ta cần hướng dẫn cho học sinh là dãy ta đang xét được lưu dưới dạng mảng một chiều). Tuy nhiên cần lưu ý với học sinh là cần phải đọc kỹ đề khi đề bài yêu cầu xác định một dãy con nào đó vì có thể đề bài đưa ra yêu cầu đưa ra một dãy con liên tiếp theo thứ tự xuất hiện (tức là không liền kề nnhau). 
- Để quản lý dãy con ta cần: một chỉ số đầu(chỉ nơi bắt đầu dãy con) và độ dài của dãy hoặc chỉ số đầu và chỉ số cuối (chỉ nơi kết thúc dãy con).
- Dãy con có thể có 1, 2,  N phần tử (tuỳ vào định nghĩa dãy con và yêu cầu đề bài). Nếu dãy mẹ có N phần tử thì ta có 2n dãy con.
- Để duyệt qua tất cả các dãy con của một dãy gồm n số ta dùng thuật toán vét cạn gồm 3 vòng For như sau:
For i:=1 to N do	{1}
	For j:=1 to N-i+1 do	{2}
	For k:=j to i+j-1 do	{3}
	(xử lý dãy con bắt đầu từ vị trí j đến vị trí i+j-1);	{4}
 Giải thích:
{1} Vòng for 1: Cho biết độ dài của dãy con có i phần tử;
{2} Vòng for 2: Cho biết dãy con bắt đầu từ vị trí j, vậy vị trí bắt đầu của dãy con cuối cùng có độ dài i sẽ là n-i+1;
{3} Vòng for 3: Dùng để duyệt qua các phần tử của dãy con bắt đầu từ vị trí đầu là j đến vị trí cuối là i+j-1 để xử lý.
{4} Các thao tác xử lý có thể là: Tính tổng của dãy con; Kiểm tra tính tăng, giảm; Kiểm tra tính đối xứng; .
* Nếu dãy con đang xét cần lưu lại thì: Lưu lại độ dài, chỉ số đầu dãy. Xác định lại độ dài, chỉ số đầu của dãy mới. 
 	* Nếu dãy con đang xét không cần lưu thì: Xác định lại độ dài, chỉ số đầu của dãy mới.
Khi dạy chuyên đề này ta có thể rèn luyện thêm cho học sinh cách viết và sử dụng các chương trình con, để các chương trình con này tham gia vào nhiệm vụ xử lý ở phần xử lý {4}, ví dụ chương trình con kiểm tra tính đối xứng của đoạn con từ j đến j+i-1, chương trình con kiểm tra tính tăng, giảm của đoạn con, chương trình con kiểm tra xem đoạn con đó có lập thành cấp số cộng hay không, 
2.3.2 Viết chương trình cho 4 bài tập cơ bản
Ở đây tôi đưa ra 4 loại bài tập cơ bản này để học sinh hiểu cách áp dụng lý thuyết về dãy con đã cung cấp ở phần trên, với 4 bài tập cơ bản này giáo viên chưa cần thiết đòi hỏi chương trình của học sinh làm ra phải chạy được bao nhiêu test mà chỉ cần giải đúng được một vài trường hợp test nhỏ là được. Nhưng yêu cầu đặt ra với học sinh là phải làm thành thạo được 4 bài toán cơ bản này thì mới có đủ kiến thức và kỹ năng để xử lý các bài dãy con khác một cách tốt nhất có thể.
Bài cơ bản 1
Cho dãy A gồm N số nguyên. Viết chương trình in ra các dãy con liên tiếp gồm 1 phần tử, 2 phần tử, ... gồm N phần tử của dãy đã cho (dãy con liên tiếp là dãy gồm một số phần tử liên tiếp của dãy đã cho có thể gồm 1 hoặc nhiều phần tử, bản thân dãy đã cho cũng là 1 dãy con bằng có số phần tử bằng chính nó)
VD: N=6
Dãy A: 1 2 3 4 5 6
In ra: 
Dc1:
1
Dc2:
2
Dc3:
3
Dc4:
4
Dc5:
5
Dc6:
6
Dc7:
1
2
Dc8:
2
3
Dc9
3
4
Dc10
4
5
Dc11
5
6
Dc12
1
2
3
Dc13
2
3
4
Dc14
3
4
5
Dc15
4
5
6
Dc16
1
2
3
4
Dc17
2
3
4
5
Dc18
3
4
5
6
Dc19
1
2
3
4
5
Dc20
2
3
4
5
6
Dc21
1
2
3
4
5
6
Với bài tập này học sinh chỉ cần vận dụng lý thuyết đã được cung cấp để giải quyết, mục đích của bài tập này là để học sinh đưa ra được cũng như thấy được hình ảnh cụ thể các dãy con của một dãy số cho trước.
Chương trình tham khảo như sau:
CONST NMAX=100;
VAR A: ARRAY[1..NMAX] OF INTEGER;
 N,I,J,T: INTEGER;
BEGIN
 WRITELN('NHAP N= ');
 READLN(N);
 FOR I:=1 TO N DO
 BEGIN
 WRITE('NHAP PHAN TU THU ',I);
 READLN(A[I]);
 END;
 FOR I:=1 TO N DO
 FOR J:=1 TO N-I+1 DO {DUET CAC DAY CON CO DO DAI I BAT DAU TU J}
 BEGIN
 FOR T:= J TO J+I-1 DO WRITE(A[T],' ');
 WRITELN;
 END;
READLN;
END.
Bài cơ bản 2
Cho dãy A gồm N số nguyên. Viết chương trình in ra các dãy con liên tiếp gồm 1 phần tử, 2 phần tử, ... gồm N phần tử của dãy đã cho (dãy con liên tiếp là dãy gồm một số phần tử liên tiếp của dãy đã cho có thể gồm 1 hoặc nhiều phần tử, bản thân dãy đã cho cũng là 1 dãy con bằng có số phần tử bằng chính nó)
VD: N=6
Dãy A: 1 2 3 4 5 6
In ra: 
Dc1:
1
2
3
4
5
6
Dc2:
1
2
3
4
5
Dc3:
2
3
4
5
6
Dc4:
1
2
3
4
Dc5:
2
3
4
5
Dc6:
3
4
5
6
Dc7:
1
2
3
Dc8:
2
3
4
Dc9
3
4
5
Dc10
4
5
6
Dc11
1
2
Dc12
2
3
Dc13
3
4
Dc14
4
5
Dc15
5
6
Dc16
1
Dc17
2
Dc18
3
Dc19
4
Dc20
5
Dc21
6
Mục đích của bài tập 2 này là rèn luyện thêm kỹ năng chuyển đổi giữa câu lệnh For tiến và For lùiviệc làm này có lợi khi giáo viên đưa ra yêu cầu tìm một dãy con ngắn nhất hoặc dài nhất thỏa mãn một điều kiện nào đó, khi đó học sinh sẽ biết nên chọn câu lệnh for nào để khi tìm thấy một dãy con như vậy thì thoát luôn không cần tìm tiếp.
Chương trình tham khảo như sau:
CONST NMAX=100;
VAR A: ARRAY[1..NMAX] OF INTEGER;
 N,I,J,T: INTEGER;
BEGIN
 WRITELN('NHAP N= ');
 READLN(N);
 FOR I:=1 TO N DO
 BEGIN
 WRITE('NHAP PHAN TU THU ',I);
 READLN(A[I]);
 END;
 FOR I:=N DOWNTO 1 DO
 FOR J:=1 TO N-I+1 DO 
 BEGIN
 FOR T:= J TO J+I-1 DO WRITE(A[T],' ');
 WRITELN;
 END;
READLN;
END.
Bài cơ bản 3
Cho dãy A gồm N số nguyên. Viết chương trình in ra các dãy con liên tiếp của dãy đã cho (dãy con liên tiếp là dãy gồm một số phần tử liên tiếp của dãy đã cho có thể gồm 1 hoặc nhiều phần tử, bản thân dãy đã cho cũng là 1 dãy con bằng có số phần tử bằng chính nó)
VD: N=6
Dãy A: 10 1 2 5 9 4
In ra: 
Dc1:
10
1
2
5
9
4
Dc2:
10
1
2
5
9
Dc3:
10
1
2
5
Dc4:
10
1
2
Dc5:
10
1
Dc6:
10
Với bài tập này ta tập cho học sinh thói quen đọc kỹ đề bài và xem xét kỹ output của bài toán để từ đó đưa ra những điều chỉnh trong cách duyệt để tìm đúng output, vì đề bài cũng yêu cầu đưa ra các dãy con nhưng chỉ khác là các dãy con có độ dài từ 1 đến N chỉ được đưa ra đúng một lần và các dãy con đó đều bắt đầu từ phần tử thứ 1 của dãy.
Từ đó có thể tự phân tích được cách làm, nếu học sinh còn lúng túng giáo viên có thể hướng dẫn học sinh để đưa ra nhận xét sau:
Có N lần duyệt, vậy ta dùng biến i là biến duyệt số lần, với i chạy từ 1 đến N
Với mỗi lần duyệt i, ta in ra các dãy con từ 1 đến N-i+1
Vậy khi đó chỉ cần có 2 vòng for là đủ để in ra các dãy con này, vậy so với thuật toán vét cạn đã được giới thiệu ở phần lý thuyết thì ta bỏ bớt đi vòng lặp thứ 3. 
Chương trình tham khảo như sau:
CONST NMAX=100;
VAR A: ARRAY[1..NMAX] OF INTEGER;
 N,I,J,T: INTEGER;
BEGIN
 WRITELN('NHAP N= ');
 READLN(N);
 FOR I:=1 TO N DO
 BEGIN
 WRITE('NHAP PHAN TU THU ',I);
 READLN(A[I]);
 END;
 FOR I:=1 TO N DO
 BEGIN
 FOR J:=1 TO N-I+1 DO 
 WRITE(A[J],' ');
 WRITELN;
 END;
READLN;
END.
Tương tự như vậy giáo viên có thể thay đổi cách in các dãy con để học sinh rèn luyện thêm kỹ năng, chẳng hạn thay đổi thành bài toán cơ bản 4 sau đây:
Bài cơ bản 4
Cho dãy A gồm N số nguyên. Viết chương trình in ra các dãy con liên tiếp của dãy đã cho (dãy con liên tiếp là dãy gồm một số phần tử liên tiếp của dãy đã cho có thể gồm 1 hoặc nhiều phần tử, bản thân dãy đã cho cũng là 1 dãy con bằng có số phần tử bằng chính nó)
VD: N=6 ;Dãy A: 10 1 2 5 9 4
In ra: 
Dc1:
10
Dc2:
10
1
Dc3:
10
1
2
Dc4:
10
1
2
5
Dc5:
10
1
2
5
9
Dc6:
10
1
2
5
9
4
Với bài này thì học sinh tự sửa lại chương trình của bài tâp cơ bản 3 ở trên là xong.
2.3.3 Làm các bài tập thực tế để vận dụng, cải tiến, hiệu chỉnh và nâng cấp chương trình
Đối với phần này khi làm bài tập giáo viên có thể đưa ra 3 mức độ để học sinh rèn luyện và nâng cao kỹ năng lập trình:
Mức độ 1: Yêu cầu học sinh cải tiến chương trình đã viết nếu có thể
Ở mức độ này giáo viên nên yêu cầu học sinh bám sát vào các đặc điểm của dữ liệu, dữ kiện mà đê bài yêu cầu, tuy nhiên giáo viên chưa đặt ra yêu cầu là phải chạy được nhiều test. Chỉ cần chạy được 1 đến 2 hoặc 3 test đúng là được. 
Mức độ 2: Hướng dẫn học sinh sử dụng các kỹ thuật lập trình khác để nâng cấp chương trình chạy được nhanh hơn (nhiều test hơn)
Ở mức độ này dựa vào vào các đặc điểm của dữ liệu, dữ kiện mà đê bài yêu cầu, giáo viên có thể hướng dẫn thêm học sinh các kỹ thuật khác để giúp học sinh nâng cấp chương trình nhưng chưa phải là chạy hết được các test. Chẳng hạn kỹ thuật dùng biến định vị (lính canh), kỹ thuật trượt cửa sổ, kỹ thuật đặ cờ hiệu
Mức độ 3: Tùy vào năng lực tiếp thu của học sinh giáo viên có thể hướng dẫn học sinh sử dụng các kỹ thuật lập trình khác để xử lý các bộ test lớn của bài toán. Chẳng hạn như quy hoạch động
Dưới đây là một số bài tập tôi đã sử dụng để rèn luyện kỹ năng cho học sinh:
Bài tập 1: Cho một mảng số nguyên gồm n phần tử. Tìm dãy con gồm m phần tử (m£ n £1000) sao cho dãy con này có tổng lớn nhất. (Dãy con là dãy các phần tử liên tiếp nhau trong mảng).
Ví dụ: nhập vào từ bàn phím
N=6
1 -3 2 -5 4 3
M=4
In ra màn hình: 2 -5 4 3
Khi làm bài tập này, dựa vào lý thuyết học sinh đã được cung cấp thuật toán vét cạn:
For i:=1 to N do	{1}
	For j:=1 to N-i+1 do	{2}
	For k:=j to i+j-1 do	{3}
	(xử lý dãy con bắt đầu từ vị trí j đến vị trí i+j-1);	{4}
thì học sinh sẽ có nhận xét sau:
Vì số phần tử của dãy con là m nên ta sẽ bỏ đi vòng lặp 1 mà thay i trong vòng lặp 2 và 3 bằng m. Mỗi lần xử lý dãy con thì ta tính tổng dãy con đó và so sánh để tìm ra tổng lớn nhất đồng thời lưu lại vị trí j của dãy con đó.
 Khi đó chỉ cần sử dụng 2 vòng lặp
For j:=1 to N-m+1 do	
	For k:=j to m+j-1 do	
	(xử lý dãy con bắt đầu từ vị trí j đến vị trí i+j-1);	
Khi đó học sinh có thể viết chương trình như sau:
Type M1C=ARRAY[1..1000] Of Integer;
Var A:M1C;
 n,m,i,j,k,vt:integer;
 S,Max:longint;
Begin
 Write('Nhap so phan tu cua mang: n= '); Readln(n);
 For i:=1 To n Do
 Begin
 Write('a[',i,']='); Readln(a[i]);
 End;
 Write('Nhap so phan tu cua day con: m= '); Readln(m);
 Max:=0; vt:=1;
 For j:=1 To n-m+1 Do
 Begin
 {Tính tổng của dãy con thứ j}
 S:=0;
 For k:=j To j+m-1 Do S:=S+A[k];
 If S>Max Then { Nếu dãy con tìm được có tổng lớn hơn dãy con trước}
 Begin
 Max:=S; {Thay tổng mới}
 vt:=j; { Thay vị trí đầu tiên của dãy con mới }
 End;
 End;
 Writeln('Day con co tong lon nhat la:');
 For i:=vt To vt+m-1 Do Write(A[i]:5);
 Readln;
End.
Sau khi đã viết được chương trình giáo viên có thể yêu cầu học sinh tự cải tiến chương trình nếu có thể, nếu học sinh còn lúng túng thì giáo viên mới đưa ra nhận xét để học sinh cải tiến chương trình của mình.
Hướng dẫn cải tiến chương trình: Giống như trong bài toán tìm giá trị lớn nhất của dãy số, ban đầu ta giả sử Max = A[1], thì ở đây ta cũng giả sử tổng Max ban đầu là tổng các phần tử từ 1 đến M, các lần sau ta chỉ tìm và so sánh tổng Max với các dãy con bắt đầu từ vị trí thứ 2 trở đi, chương trình tham khảo như sau:
Type M1C=ARRAY[1..1000] Of Integer;
Var A : M1C;
 n,m,i,j,k,vt:integer;
 S,Max:longint;
Begin
 Write('Nhap so phan tu cua mang: n= '); Readln(n);
 For i:=1 To n Do
 Begin
 Write('a[',i,']='); Readln(a[i]);
 End;
 Write('Nhap so phan tu cua day con: m= '); Readln(m);
 vt:=1; {Vị trí phần tử đầu tiên của dãy con}
 {Giả sử m phần tử đầu tiên của mảng A là dãy con có tổng lớn nhất}
 Max:=0;
 For i:=1 To m Do Max:=Max+A[i];
 {Tìm các dãy con khác}
 For j:=2 To n-m+1 Do
 Begin
{Tính tổng của dãy con thứ j}
 S:=0;
 For k:=j To j+m-1 Do S:=S+A[k];
 If S>Max Then { Nếu dãy con tìm được có tổng lớn hơn dãy con trước thì}
 Begin
 Max:=S; { Thay tổng mới }
 vt:=j; { Thay vị trí đầu tiên của dãy con mới }
 End;
 End;
 Writeln('Day con co tong lon nhat la:');
 For i:=vt To vt+m-1 Do Write(A[i]:5);
 Readln;
End.
Khi chương trình đã chạy đúng được một vài test giáo viên có thể yêu cầu học sinh sửa lại chương trình để thực hiện việc đọc dữ liệu từ tệp và ghi kết quả ra tệp, chạy chương trình với N=1000 nếu có thể.
Bài tập 2: Chia hết
Cho một dãy gồm N số nguyên dương A1, A2, ..., AN. Hãy lấy ra K số liên tiếp để tổng của chúng chia hết cho N với K bé nhất.
Dữ liệu: Đọc vào từ file văn bản DAY.INP:
Dòng đầu ghi N.
Dòng tiếp ghi các số A1, A2, ..., AN.
Kết quả: ghi ra file văn bản DAY.OUT gồm một dòng ghi giá trị K và chỉ số của số hạng đầu tiên được lấy ra.
Giới hạn: N và các Ai £ 32767.
Ví dụ:
DAY.INP
DAY.OUT
5
1 2 2 1 4
2 4
Khi làm bài tập này với thuật toán vét cạn để đưa ra các dãy con đã được cung cấp, học sinh có thể viết được chương trình ở mức độ chưa chính xác như sau:
program Bt2;
Type m1c = array[1..10000] of integer;
Var a:m1c;
 i, j, t,n, kmax,jmax:integer;
 tong:longint;
 thay:boolean;
 f1,f2:text;
BEGIN
 Assign(f1,'DAY.INP'); Reset(f1);
 readln(f1,n);
 for i:= 1 to n do Read(f1,a[i]);
 Close(f1);
 Assign(f2,'DAY.OUT'); Rewrite(f2);
 {xu ly}
 for i:=1 to N do
 for j:=1 to N- i+1 do
 begin
 tong:=0;
 for t:=j to j+i-1 do
 tong:=tong+a[t];
 if tong mod n =0 then
 begin	kmax:=i;	jmax:=j;	end;
 end;
 Write(f2,kmax, ' ', jmax);
 Close(f2);
END.
Chương trình trên cũng đưa ra được dãy con có tổng chia hết cho N nhưng không phải là dãy con ngắn nhất (k nhỏ nhất). Do vậy ở đây giáo viên phải hướng dẫn học sinh thêm kỹ thuật đặt cờ hiệu để thoát các vòng For khi tìm thấy dãy con đầu tiên, ngắn nhất thõa mãn có tổng chia hết cho N. Chương trình tham khảo như sau:
program Bt2;
Type m1c = array[1..10000] of integer;
Var a:m1c;
 i, j, t,n, kmax,jmax:integer;
 tong:longint;
 thay:boolean;
 f1,f2:text;
BEGIN
 Assign(f1,'DAY.INP'); Reset(f1);
 readln(f1,n);
 for i:= 1 to n do Read(f1,a[i]);
 Close(f1);
 Assign(f2,'DAY.OUT'); Rewrite(f2);
 for i:=1 to N do
 begin
 thay:=false;
 for j:=1 to N- i+1 do
 begin
 tong:=0;
 for t:=j to j+i-1 do	 tong:=tong+a[t];
 if tong mod n =0 then
 begin	kmax:=i;	jmax:=j;	thay:=true;	end;
 if thay then break;
 end;
 if thay then break;
 end;
 Write(f2,kmax, ' ', jmax);
 Close(f2);
END.
Với bài này đề bài không cho giới hạn của N nên giáo viên cũng chưa cần yêu cầu chương trình của học sinh phải chạy được nhiều test.
Bài tập 3: Đoạn con
 Cho dãy số nguyên a1, a2,..., aN (|ai| < 109, N < 105). Một tập hợp khác rỗng các số hạng liên tiếp {ai, ai+1,..., ak} (i £ k) gọi là một đoạn con của dãy đó. Với mỗi đoạn con ta tính tổng tất cả các số hạng của nó.
Yêu cầu: Tìm giá trị lớn nhất trong số các tổng của các đoạn con của dãy đã cho.
Dữ liệu vào: