SKKN Xây dựng một số bài toán về dãy con trong mảng một chiều để bồi dưỡng học sinh giỏi Tin Học

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ 
TRƯỜNG THPT NÔNG CỐNG II
SÁNG KIẾN KINH NGHIỆM
 XÂY DỰNG MỘT SỐ BÀI TOÁN VỀ DÃY CON TRONG MẢNG MỘT CHIỀU ĐỂ BỒI DƯỠNG 
HỌC SINH GIỎI TIN HỌC
Người thực hiện: Hoàng Thị Yến
Chức vụ: Giáo viên
SKKN thuộc lĩnh mực (môn): Tin học
THANH HOÁ NĂM 2016
MỤC LỤC
	 	 TRANG
1. MỞ ĐẦU	2
Lý do chọn đề tài	2
Mục đích nghiên cứu	2
Đối tượng nghiên cứu	2
1.4. Phương pháp nghiên cứu	3
2. NỘI DUNG CỦA SÁNG KIẾN KINH NGHIỆM	3
 Cơ sở lý luận của sáng kiến kinh nghiệm	3
Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm	3
Các sáng kiến kinh nghiệm hoặc các giải pháp đã sử dụng	
để giải quyết vấn đề	5
2.3.1. Dãy con gồm các phần tử liên tiếp	5
Dãy con gồm các phần tử liên tiếp hoặc không liên tiếp	11
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
3. KẾT LUẬN, KIẾN NGHỊ	20
Kết luận	20
Kiến nghị	20
TÀI LIỆU THAM KHẢO	21
1. MỞ ĐẦU
Lí do chọn đề tài.
	Tin học trở thành một phần tất yếu của thế giới hiện đại. Tin học đã thay đổi cách sống, cách nghĩ, và cách làm. Con người đang sống trong thế giới hóa, máy tính hóa và lập trình hóa. Để sống trong thế giới công nghệ số và hiểu biết về thế giới số hóa đó, học sinh cần đến tin học. Công dân tương lai không chỉ là người sử dụng thông thái, chủ động, thậm chí còn là những nhà sáng chế, đẩy nhanh sự tiến bộ của cuộc cách mạng tin học. 
	Tin học là hành trang thiết yếu trên con đường nghề nghiệp. Phần lớn các ngành nghề trong xã hội hiện đại đòi hỏi hiểu biết tin học. Thêm nữa, rất nhiều ngành nghề mới xuất hiện trong lĩnh vực tin học như: lập trình viên, quản trị mạng, thiết kế cơ sở kỹ thuật, an ninh mạng, Đối với chính ngành giáo dục, tin học là cơ sở hạ tầng của giáo dục. Tin học là môi trường dạy học, công cụ quản lý giáo dục, công cụ sư phạm, thiết bị học tập cá nhân, làm việc của nhóm giáo viên, học sinh.
	Một trong những mục tiêu khi đưa Tin học vào trường học là nhằm giúp học sinh có khả năng phân tích, tổng hợp, trừu tượng hoá, khái quát vấn đề và phát triển tư duy. Muốn vậy ngoài dạy học chính khóa Tin học trong nhà trường nhằm đảm bảo tính phổ thông, hướng nghiệp và dạy nghề, ta cần phải tạo điều kiện cho các học sinh có năng khiếu về Tin học phát triển về khả năng lập trình để giải quyết bài toán. Góp phần nâng cao chất lượng dạy và học Tin học 11 ở nhà trường phổ thông, bồi dưỡng các học sinh có năng khiếu và yêu thích môn tin học. Đặc biệt khi lập trình giải các bài toán về dãy con trong mảng một chiều thường rất phức tạp, khó khăn. Bồi dưỡng học sinh giỏi là nhiệm vụ khó không chỉ từ việc lựa chọn học sinh, lựa chọn phương pháp mà còn đòi hỏi nhiều kiến thức, kỹ năng vận dụng cao. Qua việc tham khảo những đề thi học sinh giỏi cấp tỉnh trung học phổ thông môn Tin học thì xu hướng rất nhiều đề tính toán xử lý dãy con trong mảng một chiều. Vì vậy để nâng cao chất lượng dạy học môn Tin học 11, bồi dưỡng học sinh khá giỏi, định hướng cho các em khi xử lý tốt các bài toán về dãy con, làm cho chương trình dễ đọc, dễ hiệu chỉnh và dễ nâng cấp, nên tôi quyết định chọn đề tài :“Xây dựng một số bài toán về dãy con trong mảng một chiều để bồi dưỡng học sinh giỏi Tin học”. 
Mục đích nghiên cứu.
	Đưa ra một số phương pháp để giải quyết các bài toán cơ bản về dãy con trong mảng một chiều, nâng cao khả năng tư duy sáng tạo cho học sinh, nâng cao chất lượng học sinh giỏi. Nêu vấn đề, phân dạng bài toán tin học có liên quan, thực hiện ví dụ minh họa để học sinh quan sát qua đó nắm vững kiểu mảng một chiều. Đặc biệt hình thành ở học sinh kỹ năng phân tích, xử lý các vấn đề thường gặp trong khi làm việc với kiểu dữ liệu có cấu trúc. 
Đối tượng nghiên cứu.
	+ Học sinh khá giỏi lớp 11 trường THPT Nông Cống II 
	+ Một số bài toán về dãy con trong mảng một chiều
	+ Máy tính, máy chiếu để chạy mô tả các thuật toán.
Phương pháp nghiên cứu.
	+ Phương pháp nghiên cứu xây dựng cơ sở lý thuyết
	+ Kỹ thuật phân tích thuật toán
	+ Phát triển tư duy học sinh
	+ Tìm hiểu và phát triển kỹ năng.
	+ Tham khảo các tài liệu lấy từ nhiều nguồn nhất là các học liệu mở trên mạng internet và phân tích có hệ thống các dạng bài tập theo nội dung đã đề ra.
2. NỘI DUNG SÁNG KIẾN KINH NGHIỆM
Cơ sở lí luận của sáng kiến kinh nghiệm.
	 - Nghị quyết Hội nghị trung ương 8 khóa XI về đổi mới căn bản, toàn diện giáo dục và đào tạo xác định “Tiếp tục đổi mới mạnh mẽ và đồng bộ các yếu tố cơ bản của giáo dục đào tạo theo hướng coi trọng phát triển phẩm chất, năng lực của người học”; “tập trung phát triển trí tuệ, thể chất, hình thành phẩm chất, năng lực công dân, phát hiện và bồi dưỡng năng khiếu, định hướng nghề nghiệp cho học sinh. Nâng cao chất lượng giáo dục toàn diện, chú trọng giáo dục lý tưởng, truyền thống, đạo đức, lối sống, ngoại ngữ, tin học, năng lực và kỹ năng thực hành, vận dụng kiến thức vào thực tiễn. Phát triển khả năng sáng tạo, tự học, khuyến khích học tập suốt đời”. 
	- Luật Giáo dục số 38/2005/QH11, Điều 28 quy định: “Phương pháp giáo dục phổ thông phải phát huy tính tích cực, tự giác, chủ động, sáng tạo của học sinh; phù hợp với đặc điểm của từng lớp học, môn học; bồi dưỡng phương pháp tự học, khả năng làm việc theo nhóm; rèn luyện kỹ năng kiến thức vào thực tiễn; tác động đến tình cảm, đem lại niềm vui, hứng thú học tập cho học sinh”
	Căn cứ vào những quan điểm, định hướng trên để xác định ra nhiệm vụ cụ thể của môn Tin học, tổ chức hoạt động đào tạo góp phần thực hiện mục tiêu giáo dục mà Đảng và nhà nước đề ra. Ngoài việc tạo điều kiện cho học sinh chiếm lĩnh những tri thức và kỹ năng Tin học cần thiết, Tin học còn có tác dụng phát triển năng lực trí tuệ chung như: phân tích, tổng hợp, trừu tượng hoá, khái quát hoá, rèn luyện những đức tính, phẩm chất của người lao động mới. Học sinh sẽ thấy rõ hiệu quả mạnh mẽ của công nghệ thông tin và nhận thức cần có.
Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm.
Thực trạng chung:
Phần lớn học sinh đang ngồi trên ghế nhà trường THPT đều nhận thức bộ môn Tin học không liên quan gì đến kỳ thi THPT quốc gia nên các em không chú trọng nhiều tới vấn đề trang bị kiến thức Tin học phổ thông, làm hành trang cho tương lai. Kiến thức Tin học ngày càng nhiều, thời gian các em học chính khóa và bồi dưỡng các môn thi đại học chiếm gần như cả tuần, nên việc dạy học lập trình Pascal bồi dưỡng học sinh giỏi càng gặp nhiều khó khăn hơn. 
 Nhu cầu xã hội đang rất cần những kỹ sư công nghệ thông tin, người lập trình viên thật sự giỏi nhưng việc bồi dưỡng học sinh yêu thích lập trình Pascal trong trường THPT chưa đáp ứng được những yêu cầu cơ bản. Do vậy việc dạy học sinh những kiến thức lập trình cơ bản sẽ giúp các em tiếp cận những ngôn ngữ khác một cách nhanh chóng và chiếm lĩnh được tri thức mới. Học sinh yêu thích môn tin học nhưng gặp khó khăn về tài liệu, thời gian và luôn phải lo lắng cho các kỳ thi nên thời gian dành cho môn tin không có. 
Lập trình Pascal là môn học khó, trừu tượng học sinh khó nắm được kiến thức. Khả năng nhận dạng, phân tích đề của học sinh chưa chắc nhắn, đôi khi sai kiến thức cơ bản về cú pháp và ngữ nghĩa. Kiến thức cơ bản về kiểu mảng một chiều trong Tin học 11 chưa đủ để học sinh làm tốt các đề thi học sinh giỏi. Đa số kiến thức thi học sinh giỏi là những kiến thức trong sách tham khảo, nâng cao. Vì thế giáo viên dạy bồi dưỡng học sinh giỏi phải có chương trình bồi dưỡng thường xuyên, tập hợp, biên soạn tư liệu phù hợp với đối tượng học sinh và đảm bảo mức độ của đề thi học sinh giỏi.
Thuận lợi và khó khăn khi thực hiện đề tài ở trường THPT Nông Cống II
- Thuận lợi:
+ Nhà trường:
	Bộ môn Tin học được đưa vào giảng dạy cấp trung học phổ thông đã được 10 năm, nhà trường đã tạo điều kiện về cơ sở vật chất như máy tính, trang thiết bị để phục vụ cho việc dạy và học môn Tin học.
+ Giáo viên:
	Giáo viên được đào tạo chuẩn kiến thức cơ bản và nâng cao về Tin học.
	Giáo viên giảng dạy đã qua đào tạo chuyên ngành Sư phạm Tin học, bồi dưỡng kiến thức qua các đợt tập huấn do Sở giáo dục và đào tạo tổ chức.
+ Học sinh:
	Phần lớn học sinh có kiến thức, tư duy toán học cơ bản do đó tiếp cận lập trình một cách dễ dàng hơn. Một số học sinh có khả năng phát triển về lập trình và yêu thích lập trình.
- Khó khăn:
+ Nhà trường:
	Nhà trường đã có phòng máy vi tính để cho học sinh học nhưng vẫn còn hạn chế về số lượng cũng như chất lượng. 
	Điều kiện phục vụ dạy học, tài liệu, sách báo cho giáo viên và học sinh tham khảo chưa được phong phú.
+ Giáo viên:
	Mức độ tiếp thu kiến thức của học sinh là khác nhau nên tính hiệu quả chưa đồng đều. Đòi hỏi sự đầu tư thời gian công sức của giáo viên nhiều.
	Giáo viên thường gặp khó khăn về phân hoá học sinh và bồi dưỡng học sinh yêu thích và học khá giỏi môn tin. Do đó việc lựa chọn học sinh giỏi là rất khó khăn vì học sinh giỏi thường học tốt các môn tự nhiên.
+ Học sinh:
	Học sinh không có điều kiện tiếp cận các tài liệu về lập trình. Đa số học sinh trong trường đều là con em nông dân nên điều kiện kinh tế còn nhiều khó khăn nên rất ít học sinh ở nhà có máy tính.
	Chương trình học, thi cử ở phổ thông khá nặng và chiếm lượng thời gian lớn nên việc học sinh bỏ thời gian đầu tư cho một môn không tham gia thi THPT Quốc gia là không nhiều.
Các sáng kiến kinh nghiệm hoặc các giải pháp đã sử dụng để giải quyết vấn đề.
Ngôn ngữ lập trình Pascal có quy tắc cho phép tạo ra các kiểu dữ liệu có cấu
trúc để người lập trình mô phỏng được dữ liệu thực tế. Từ đó có khả năng giải quyết được những bài toán đặt ra trên thực tế. Kiểu mảng một chiều là kiểu dữ liệu có cấu trúc được xây dựng từ những kiểu dữ liệu cơ sở theo một số cách thức tạo kiểu do ngôn ngữ lập trình quy định. Kiểu dữ liệu được xác định bởi hai yếu tố là phạm vi đối tượng và các thao tác trên những đối tượng này.
	Bài toán về kiểu mảng một chiều rất đa dạng. Mỗi thuật toán chỉ giải một bài toán, nhưng có thể có nhiều thuật toán khác nhau cùng giải một bài toán. Cần thiết phải lựa chọn một thuật toán phù hợp, để lập trình bài toán thường dựa trên hai yếu tố quan trọng là thời gian và không gian. Một bài toán được hiểu là khó nếu ta sử dụng thuật giải mới nảy sinh trong đầu khi vừa biết yêu cầu bài toán thì hoặc là ta thu được kết quả sai hoặc lời giải thu được sẽ không hữu hiệu theo nghĩa chương trình đòi hỏi quá nhiều bộ nhớ hoặc/và chạy quá lâu. Thuật giải đó gọi là thuật giải tự nhiên. Dĩ nhiên điều này chỉ là tương đối. Nếu học sinh đã nắm vững nhiều dạng thuật toán và thử sức với nhiều bài toán khó thì đến một lúc nào đó thuật giải tự nhiên sẽ đáng tin cậy. Vì vậy để khuyến khích tính tích cực chủ động tiếp thu kiến thức của học sinh, tôi giới thiệu một số bài toán cơ bản về dãy con trong mảng một chiều như sau:
Dãy con gồm các phần tử liên tiếp 
	Dãy con là dãy các phần tử liên tục thuộc một dãy có trước thỏa mãn một tính chất nào đó. Giải thuật cơ bản áp dụng cho bài toán dãy con liên tục là sử dụng 2 vòng lặp WHILE lồng nhau để duyệt dãy số một lần từ đầu đến cuối dãy. Ngoài ra có thể dùng phương pháp quy hoạch động.
Bài toán 1. Chia mảng tỉ lệ 1:K
Cho mảng gồm N phần tử là số nguyên a1, a2,, aN, và số nguyên K. 
Yêu cầu chia mảng trên thành 2 phần có tổng gấp nhau K lần. Mỗi phần gồm các phần tử liên tiếp nhau.
Dữ liệu: Vào từ file BAI.INP:
- Dòng 1: ghi 2 số N, K (0 < N, K ≤30000);
- Dòng 2: ghi N số a1, a2,,aN cách nhau bởi dấu cách (|ai|≤ 32000).
Kết quả: Ghi vào file BAI1.OUT:
- Nếu không chia được: ghi số 0
- Nếu chia được: ghi 2 phần có tổng gấp nhau K lần, mỗi phần ghi trên 1 dòng (các phần tử mỗi phần cách nhau bởi dấu cách).
Ví dụ:
BAI1.INP
BAI1.OUT
5 3
2 3 4 6 5
2 3
4 6 5
Ý tưởng:
Gọi S là tổng các phần tử của mảng: S = sum(a[1..n]). Muốn chia mảng thành 2 phần a[1..i] và a[i+1..n] có tổng gấp nhau k lần ta phải có:
+ S chia hết cho (k+1). Đặt S1 = S div (k+1) và S2= S - S1
+ (Nếu tồn tại i: 1 ≤ i ≤ n): sum(a[1..i]) = S1 hoặc sum(a[1..i]) = S2.
Chương trình:
var f1, f2: text; kt: boolean;
 i, j, n, k: integer; s, s1, s2, s3: int64;
 a: array[1..32000] of integer;
begin
 assign(f1, 'BAI1.INP'); reset(f1);
 assign(f2, 'BAI1.OUT'); rewrite(f2);
 readln(f1, n, k); s:= 0;
 for i:=1 to n do
 begin read(f1, a[i]); s:= s+a[i]; end;
 if s mod (k+1) 0 then write(f2, 0) else
 Begin 	kt:= false;
 	s1:= s div (k+1); s2:= s-s1;s3:= 0;
 	for i:=1 to n do
 	begin
 	s3:= s3+a[i];
 	if (s3= s1) or (s3= s2) then 
	begin kt:= true; break; end;
 	end;
 	if kt then begin
 	for j:=1 to i do write(f2, a[j], ' ');
 	writeln(f2);
 	for j:=i+1 to n do write(f2, a[j], ' ');
 	 	end else write(f2, 0);
 	end;
 	close(f1); close(f2);
	end.
Dạng bài tập áp dụng: 
+ Chia mảng tỉ lệ 1:1.
Bài toán 2: Dãy con gồm các số dương liên tiếp nhiều nhất.
Cho dãy số gồm N số nguyên a1, a2, ..., aN, (1 ≤ N ≤ 60000; |ai| ≤ 1000).
Hãy tìm số lượng các phần tử một dãy con dài nhất gồm các phần tử dương liên tiếp trong dãy số trên.
Dữ liệu: Vào từ file văn bản BAI2.INP
- Dòng 1: Chứa số N;
- Dòng 2: Chứa N số a1, a2, ..., aN cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản BAI2.OUT:
Một dòng ghi số lượng các phần tử dương liên tiếp của một dãy con dài nhất
Ràng buộc: Có ít nhất một phần tử dương trong dãy số.
Ví dụ:
BAI2.INP
BAI2.OUT
10
-5 -2 -3 4 -6 7 -8 9 -1 -20
1
Ý tưởng:
 Biến d để đếm số phần tử của dãy con tạm thời gồm các phần tử dương liên tiếp. Biến Max để lưu số lượng phần tử dương liên tiếp của dãy con dài nhất. 
- Bước 1: Khởi tạo Max ß 0;
- Bước 2: Xét các phần tử của dãy. Bắt đầu từ vị trí đầu tiên (i) của dãy, nếu phần tử đang xét ai là số nguyên dương thì kiểm tra nếu phần tử tiếp theo ai+1 là số nguyên dương thì nạp phần tử ai+1 vào dãy con tạm thời, xét tiếp phần tử tiếp theo. Đến khi nào gặp phần tử là số nguyên không dương thì ta kiểm tra số lượng phần tử dãy con hiện thời d xem có lớn hơn giá trị Max không. Nếu lớn hơn thì gán lại Max ß d. Tiếp tục xem các dãy sau cho đến hết dãy A.
Chương trình:
var f1, f2: text;
 kt: boolean;
 i, j, n, max, d: longint;
 a: array[1..60000] of integer;
begin
 assign(f1, 'bai2.inp'); reset(f1);
 assign(f2, 'bai2.out'); rewrite(f2);
 readln(f1, n);
 for i:=1 to n do read(f1, a[i]);
 i:= 1; max:= 0;
 while i <= n do
 if a[i] > 0 then begin j:= i; d:= 0;
 	while (j 0) do
 	begin inc(j); inc(d); end;
 	if max < d then max:= d;
 	i:= i+d; 	{inc(i,d);}
 	end 
	else inc(i);
 write(f2, max);
 close(f1); close(f2);
end.
 Dạng bài tập áp dụng: 
+ Số lượng các số hạng dương liên tiếp có tổng lớn nhất
+ Số lượng các số hạng âm liên tiếp nhiều nhất
Bài toán 3: Dãy con không giảm dài nhất
Cho dãy gồm N số nguyên a1, a2, a3, , aN. Tìm dãy con không giảm dài nhất 
gồm các phần tử liên tiếp.
Dữ liệu: Vào từ file văn bản BAI3.INP
- Dòng 1: Chứa số N (0 < N ≤ 105);
- Dòng 2: Chứa N số a1, a2,, aN cách nhau ít nhất một dấu cách ( |ai|≤32000).
Kết quả: Ghi ra file văn bản BAI3.OUT
- Chỉ gồm một dòng ghi số lượng các phần tử dãy con không giảm dài nhất
Ví dụ:
BAI3.INP
BAI3.OUT
10
6 -4 -2 1 4 3 1 5 3 45
4
Ý tưởng:
Biến d để đếm số phần tử của dãy con không giảm tạm thời. Biến Max để lưu số lượng phần tử của dãy con không giảm lớn nhất là max. 
- Bước 1: Khởi tạo dãy con không giảm lớn nhất có số phần tử là 0.
- Bước 2: Xét các phần tử của dãy. Bắt đầu từ vị trí đầu tiên (i) của dãy, kiểm tra tiếp theo nếu ai+1 ≥ ai thì nạp phần tử ai+1 vào dãy con tạm thời, xét tiếp phần tử tiếp theo. Đến khi nào gặp phần tử kế tiếp nhỏ hơn phần tử hiện tại thì ta kiểm tra d > Max? Nếu d > Max thì Max ß d. Tiếp tục xem các dãy sau cho đến hết dãy A.
Chương trình:
var f1, f2:text;
 kt: boolean;
 i, j, n, max, d: longint;
 a: array[1..100000] of integer;
begin
 assign(f1, 'BAI3.INP'); reset(f1);
 assign(f2, 'BAI3.OUT'); rewrite(f2);
 readln(f1, n);
 for i:=1 to n do read(f1, a[i]);
 i:= 1; max:= 0;
 while i < n do
 if a[i] <= a[i+1] then 
	begin j:= i; d:= 1;
 	while (j < n) and (a[j] <= a[j+1]) do
 begin inc(j); inc(d); end;
 	if max < d then max:= d;
 	i:= i+d;
 end else inc(i);
 write(f2, max);
 close(f1); close(f2);
	end.
Dạng bài tập áp dụng:
+ Dãy con không tăng dài nhất
+ Dãy con có các số hạng liên tiếp đan dấu nhiều nhất.
Bài toán 4: Dãy con nguyên tố dài nhất
Cho dãy gồm N số nguyên a1, a2, a3, , aN. Tìm dãy con dài nhất gồm các phần tử liên tiếp nhau và đều là số nguyên tố. Số nguyên tố là số tự nhiên lớn hơn 1 chỉ có các ước là 1 và chính nó.
Dữ liệu: Vào từ file văn bản BAI4.INP
- Dòng 1: Chứa số n (0 < N ≤ 106);
- Dòng 2: Chứa n số a1, a2,, aN cách nhau ít nhất một dấu cách ( |ai|≤105).
Kết quả: Ghi ra file van bản BAI4.OUT
Chỉ gồm một dòng ghi dãy con cần tìm. Nếu có nhiều dãy con thì đưa ra dãy con đầu tiên.
Ví dụ:
BAI4.INP
BAI4.OUT
10
1 -10 2 5 7 4 6 11 2 18
2 5 7
Ý tưởng:
- Xây dựng 1 hàm kiểm tra Kt xem 1 số X có phải là số nguyên tố không.
- Biến d để đếm số phần tử của dãy con nguyên tố tạm thời. Xâu S để lưu lại các phần tử số nguyên tố trong dãy con đang xét.
- Biến Max để lưu số lượng phần tử của dãy con nguyên tố lớn nhất; Xâu t để lưu lại các phần tử trong dãy con nguyên tố dài nhất
+ Bước 1: Khởi tạo Max ß 0.
+ Bước 2: Xét các phần tử của dãy. Bắt đầu từ vị trí đầu tiên (i) của dãy, dùng hàm Kt kiểm tra nếu phần tử đang xét ai là số nguyên tố thì kiểm tra phần tử ai+1 là số nguyên tố hay không. Nếu phải thì nạp ai+1 vào dãy con tạm thời, xét tiếp phần tử tiếp theo. Đến khi nào gặp phần tử kế tiếp không phải là số nguyên tố thì ta kiểm tra d > Max? Nếu d > Max thì gán lại Max ß d và t ß s. Tiếp tục xem các dãy sau cho đến hết dãy A.
Chương trình:
Var f1, f2: text;
 a: array[1..round(1e6)] of longint;
 n, i, j, max, d: longint;
 tg, s, t: ansistring;
function kt(x: longint): boolean;
var k: longint;
begin if x < 2 then kt:=false else
	begin	k:=2;
	while (x mod k 0) and (k < sqrt(x)) do inc(k);
	if k > sqrt(x) then kt:=true else kt:=false;
	end;
end;
begin 	
	assign(f1, 'bai4.inp'); reset(f1);
 assign(f2, 'bai4.out'); rewrite(f2);
 readln(f1, n);
 for i:=1 to n do read(f1, a[i]);
 i:= 1; max:= 0;
 while i <= n do
 if kt(a[i]) then
 begin s:= ''; j:= i; d:= 0;
 while (j <= n) and (kt(a[j])) do
 begin str(a[j], tg); s:= s+tg+' ';
 inc(j); inc(d);
 end;
 if max < d then begin max:= d; t:= s; end;
 i:= i+d;
 end else inc(i);
 write(f2, t);
 close(f1); close(f2);
end.
Dạng bài tập áp dụng:
+ Dãy con chính phương dài nhất gồm phần tử liên tiếp là số chính phương 
+ Dãy con hoàn hảo dài nhất gồm phần tử liên tiếp là số hoàn hảo. Số hoàn hảo là số nguyên dương có giá trị bằng tổng các ước của nó (trừ chính số đó).
Bài toán 5: Tính tổng của dãy số 
	Cho một dãy gồm n số nguyên dương a1, a2, ..., an và hai số nguyên x và y 
(1 ≤ x ≤ y ≤ n).
Yêu cầu: Hãy tính tổng các phần tử liên tiếp từ ax  ay
Dữ liệu: Vào từ file BAI5.INP:
Dòng 1: ghi 3 số n, x, và y cách nhau bởi ít nhất 1 dấu cách, (1 ≤ n ≤ 104);
Dòng 2: ghi n số nguyên a1, a2, ..., an được ghi theo đúng thứ tự cách nhau ít nhất một dấu cách, (|ai| ≤ 32000).
Kết quả: ghi vào file BAI5.OUT:
- Một dòng ghi một số nguyên là tổng giá trị của các phần tử trong đoạn ax  ay
Ví dụ:
BAI5.INP
BAI5.OUT
10 3 6
-9 5 1 4 6 2 16 5 87 5
13
Ý tưởng:
Dùng phương pháp quy hoạch động:
Gọi S[i] là tổng giá trị các phần tử a1, a2, a3, ,ai (1 ≤ i ≤ n)
Ta có công thức quy hoạch động tính S[i] như sau:
S[i]:= S[i-1] +a[i];
Như vậy, việc tính S[n] được thực hiện bằng vòng lặp:
S[0] :=0;
For i:= 1 to n do S[i]:= S[i-1] + a[i];
Kết quả: Tổng các phần tử liên tiếp từ ax đến ay được tính theo công thức:
Sum := S[y] – S[x-1];
Chương trình:
var f1, f2: text;
 n, k, i, x, y: longint;
 a: array[1..10000] of integer;
 s: array[0..100000] of int64;
begin
 assign(f1, 'BAI5.INP'); reset(f1);
 assign(f2, 'BAI5.OUT'); rewrite(f2);
 readln(f1, n, x, y); s[0]:= 0;
 for i:=1 to n do
 begin read(f1, a[i]); 
	 s[i]:= s[i-1]+a[i]; 
	 end;
 write(f2, s[y]-s[x-1]);
 close(f1); close(f2);
end.
Dạng bài tập áp dụng:
+ Dãy con gồm phần tử liên tiếp có tổng lớn nhất chia hết cho K.
Dãy con gồm các ph