SKKN Lựa chọn thuật toán tối ưu giải bài toán trong Pascal để bồi dưỡng học sinh lớp 11

MỞ ĐẦU
 Lý do chọn đề tài
Đối với học sinh THPT ngoài việc cung cấp học sinh cách tư duy và giải các bài toán bằng ngôn ngữ Pascal, một số học sinh có tư tưởng chỉ cần giải bài toán bằng tư duy thông thường với bộ test nhỏ. Nhưng khi giới hạn test tăng lên thì chương trình thường bị mất test. Vì thế, muốn giải quyết các test lớn thì lựa chọn thuật tối là bước quan trọng nhất trong giải bài toán.
Có thể có nhiều thuật toán khác nhau cùng giải một bài toán, vì vậy chúng ta cần chọn một thuật toán phù hợp đã có để giải bài toán đó. Khi lựa chọn thuật toán chúng ta thường quan tâm đến các tài nguyên như: thời gian thực hiện, ô nhớ, số lượngTrong các loại tài nguyên đó, nguời ta quan tâm nhiều nhất về thời gian vì nếu mộ thuật toán cho ra kết quả đúng nhưng thời gian thực hiện thuật toán lớn thì vô nghĩa. Một nguyên nhân khác nữa đó là tài nguyên thời gian là dạng tài nguyên không tái tạo được. Thêm tiêu chí nữa cần thiết để lựa chọn thuật toán là chọn thuật toán sao cho việc viết chương trình ít phức tạp. Một thuật toán hay là thuật toán có thời gian thực hiện nhanh và tiết kiệm tài nguyên của máy tính.
Xuất phát từ lý do trên tôi chọn đề tài “Lựa chọn thuật toán tối ưu giải bài toán trong Pascal để bồi dưỡng học sinh lớp 11”.
 Mục đích nghiên cứu
Đưa ra một số thuật toán tối ưu để giải các bài toán, nâng cao khả năng tư duy sáng tạo của học sinh.
Đối tượng nghiên cứu
Học sinh lớp 11 trường THPT Nông Cống I
Nội dung kiến thức dạy học của giáo viên: Rèn luyện kĩ năng tìm, phân tích các thuật toán tối ưu để giải các bài toán
Máy tính, máy chiếu, các thiết bị hỗ trợ để mô tả thuật toán, thực hiện chạy các chương trình.
Phương pháp nghiên cứu
Kĩ thuật phân tích thuật toán
Kĩ thuật đánh giá thuật toán
Thao khảo các tài liệu từ nhiều nguồn khác nhau: các sách tham khảo, internet
NỘI DUNG
Cơ sở lý luận
 - Nghị quyết TW2 (khóa VIII) của Đảng khẳng định : “Phải đổi mới phương pháp dạy học, khắc phục lối truyền đạt kiến thức một chiều, rèn luyện nếp tư duy sáng tạo của người học”. Đổi mới phương pháp dạy học hiện nay chính là hướng tới việc dạy tốt học tốt theo phương châm: lấy người học làm trung tâm dạy học. Muốn vậy giáo viên cần phải hiểu sâu sắc và vận dụng sáng tạo các phương pháp dạy học trong mỗi tiết dạy.
 - Chương trình giáo dục đào tạo ban hành kèm theo quyết định số 16/2006 đã nêu:” phải phát huy tính tích cực, chủ động, sáng tạo của học sinh, phù hợp với đặc trưng bộ môn, đặc điểm đối tượng học sinh, điều kiện của từng lớp học, bồi dưỡng học sinh phương pháp tự học, khả năng hợp tác, rèn luyện kỹ năng vận dụng kiến thức vào thực tế.
 - Thực hiện mục tiêu của môn tin học THPT
 - Tạo điều kiện cho học sinh chiếm lĩnh tri thức, kỹ năng tin học cần thiết, để học sinh thấy rõ hiệu quả của công nghệ thông tin.
- Học sinh thực hiện tốt lựa chọn thuật toán tối ưu để giải bài toán thì chất lượng học sinh sẽ nâng cao, nhất là trong lập trình.
2.2 Thực trạng
 * Thực trạng chung
	Môn tin học giữ vai trò chủ đạo trong việc chuẩn bị cho học sinh khả năng tiếp nhận, mở rộng tri thức và sáng tạo trong thời đại thông tin, kết nối và toàn cầu hóa. Môn tin học cũng hỗ trợ đắc lực học sinh tự học tập và nghiên cứu; tạo cơ sở vững chắc cho việc ứng dụng công nghệ, kĩ thuật số phục vụ phát triển cho nội dung kiến thức mới, triển khai phương thức giáo dục mới và hiện đại cho môn tin học.
	Nhưng do môn tin học không có trong các kì thi trung học phổ thông quốc gia nên hầu hết học sinh không chú trọng tới kiến thức THPT. Do đó, việc dạy học đặc biệt học lập trình gặp rất nhiều khó khăn. Mặt khác do luôn luôn dành thời gian cho các kỳ thi, các môn thi nên thời gian các em dành cho môn tin học hầu như không có, lại thêm gặp khó khăn về tài liệu.
*Một số thuận lợi và khó khăn khi thực hiện đề tài
Thuận lợi:
Bộ môn tin học đã đưa vào chương trình THPT hơn 10 năm, nhà trường tạo có 2 phòng máy tính, trong đó có máy chiếu để phục vụ việc dạy và học môn tin học.
Giáo viên
Đào tạo chính quy chuyên ngành sư phạm tin học
Hàng năm nhà trường tổ chức cuộc thi giáo viên giỏi cấp trường, nên kiến thức giáo viên được nâng cao.
 	Học sinh
Yêu thích môn tin học, đặc biệt là những tiết thực hành.
Một số học sinh yêu thích môn lập trình (Pascal lớp 11)
 Khó khăn:
 	 Giáo viên: 
Là môn đặc thù có kiến thức khó (lập trình Pascal 11) nhưng bị xem nhẹ, bị xem là “môn phụ”, nên việc dạy, bồi dưỡng học sinh vô cùng khó khăn.
 	Học sinh:
Tuy nhà trường có 2 phòng máy tính để học sinh học nhưng số lượng máy ít và hạn chế về chất lượng.
Nhiều gia đình học sinh khó khăn nên học sinh không có máy tính ở nhà để tự học.
 Các giải pháp sử dụng để giải quyết vấn đề
Thông thường khi giải quyết một bài toán, chúng ta có thể đưa ra các thuật toán khác nhau nhưng sẽ phải chọn một thuật toán tốt nhất. Thông thường ta căn cứ vào các tiêu chuẩn sau:
	+ Thuật toán đúng đắn
	+ Thuật toán đơn giản
	+ Thuật toán thực hiện nhanh
Một thuật toán hay là thuật toán có thời gian thực hiện nhanh và tiết kiệm tài nguyên của máy tính. Khi lựa chọn thuật toán để giải bài toán cụ thể cần căn cứ vào lượng tài nguyên mà thuật toán đòi hỏi và lượng tài nguyên thực tế cho phép. Khi học sinh nắm vững nhiều dạng thuật toán và đã làm nhiều bài toán khó thì việc lựa chọn thuật toán tối ưu sẽ hiệu quả hơn. Vì thế tôi giới thiệu một số bài toán cơ bản về lựa chọn thuật toán tối ưu để giải bài toán.
2.3.1 Bài toán tìm ước chung lớn nhất (ƯCLN) của 2 số nguyên dương M, N
Thuật toán để giải bài toán:
Sử dụng phép trừ
Sử dụng phép chia lấy dư.
 Ý tưởng thuật toán sử dụng phép trừ
Nếu M= N thì giá trị chung là ƯCLN của M, N
Nếu M > N thì ƯCLN (M,N) = ƯCLN (M – N, N)
Nếu M < N thì ƯCLN (M,N) = ƯCLN (M , N - M)
Chương trình con
Function UCLN (M, N:longint):longint;
Beginh
	While M N do 
	if M > N then M:= M – N
	else N:= N – M;
 UCLN:= M;
End;
 Ý tưởng thuật toán sử dụng phép chia lấy dư
ƯCLN của 2 số M, N cũng là ƯCLN của 2 số (M và M mod N nếu M > N) hoặc (N và N mod M nếu M < N)
Function UCLN (M, N:longint):longint;
Begin
	While (M 0) or (N 0 ) do 
	if M > N then M:= M mod N
	else N:= N mod M;
 UCLN:= M + N;
End;
Đánh giá 2 thuật toán: Thuật toán sử dụng phép chia lấy dư tối ưu hơn do phải thực hiện ít phép tính hơn.
2.3.2 Bài toán sắp xếp
Trên thực tế, việc lựa chọn thuật toán sắp xếp dựa vào nhiều yếu tố như: dữ liệu vào có số lượng như thế nào? có sắp xếp sẵn hay không? Dung lượng bộ nhớ? tốc độ xử lí CPU?
Để giải bài toán sử dụng:
 - Thuật toán sắp xếp nổi bọt
- Thuật toán sắp xếp chọn
- Thuật toán sắp xếp nhanh
Ý tưởng thuật toán sắp xếp nổi bọt:
-So sánh 2 phần tử đầu tiên nếu số trước lớn hơn số sau à đổi chỗ chúng cho nhau
- Tiếp tục làm như vậy với các cặp phần tử tiếp theo cho đến khi không có sự đổi chỗ nào xảy ra nữa.
Thủ tục sắp xếp nổi bọt:
	procedure SX_noibot;
	var i,j, y:longint;
	begin
	for i:= 2 to n do
	for j:= n downto i do
	if a[j] < a[j - 1] then
	begin
	y:=a[i];
	a[i]:=a[j];
	a[j]:=y;
	end;
	end;	
Ý tưởng thuật toán sắp xếp chọn:
- Chọn phần tử nhỏ nhất N phần tử đầu, đưa phần tử này về đúng vị trí.
- Không quan tâm tới nó nữa, dãy hiện tại còn n-1 phần tử bắt đầu từ vị trí 2
- Lặp lại đến khi dãy còn 1 phần tử
Thủ tục sắp xếp chọn
	Procedure SX_chon;
	Var i,j,min, y:longint;
	Begin
	for i:=1 to n-1 do
	begin
	k:=i;
	min:=a[i];
	for j:=i + 1 to n do
	if a[j] < min then 
	begin
	min:= a[j];
	k:=j;
	end;
	y:=a[i];
	a[i]:=a[k];
	a[k]:=y;
	end;
	end;
Ý tưởng thuật toán sắp xếp nhanh:
 Trong đoạn cần sắp xếp từ làr chọn điểm chốt
 Mọi giá trị < điểm chốt được xếp trước
 Mọi giá trị > điểm chốt được xếp sau
 Đoạn (l,r) được chia thành 2 đoạn
 Tiếp tục với 2 đoạn vừa được phân chia này bằng lời gọi đệ quy
Thủ tục sắp xếp nhanh
	Procedure SX_nhanh(l,r:longint);
	Var i, j, x, y: longint;
	Begin
	i:=l;
	j:=r;
	x:=a[(l+r) div 2];
	repeat
	while a[i ] < x do inc(i);
	while a[j] > x do dec(j);
	if i <= j then
	begin
	y:=a[i];
	a[i]:=a[j];
	a[j]:=y;
	inc(i);
	dec(j);
	end;
	until i>j;
	if i < r then SX_chon(i,r);
	if j > l then SX_chon(j,l);
	end;
Đánh giá 2 thuật toán:
 Thuật toán sắp xếp nhanh chạy nhanh (nhanh nhất trong các thuật toán sắp xếp dựa trên việc so sánh các phần tử).
 Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n2), sắp xếp chọn là O(n2), sắp xếp nhanh O(nlog n)
2.3.3 Bài toán tìm kiếm
 - Sử dụng thuật toán tìm kiếm tuần tự
 - Sử dụng thuật toán tìm kiếm nhị phân
Ý tưởng thuật toán tìm kiếm tuần tự
So sánh từng phần tử của dãy a, từ a[1] àa[n] với giá trị x
Nếu tìm thấy x thì thoát ra và thông báo thứ tự phần tử i thỏa mãn a[i] = x
Nếu duyệt hết mà không tìm thấy thì việc tìm kiếm với kết quả = 0
Thủ tục
	 Procedure TK_tuantu;
	 Var i: longint;
	 Begin
	For i:= 1 to n do
	If a[i] = x then write(‘tim thay’)
	else write(‘khong tim thay’);
	end;
Ý tưởng thuật toán tìm kiếm nhị phân
Giả sử dãy a đã sắp xếp tăng, ta có: aG = a[(n +1)/2]
 Nếu aG = k đưa ra chỉ số G, kết thúc
 Nếu aG > k à tìm trên dãy (a1, a2,aG-1)
 Nếu aG < k àtìm trên dãy (aG1, aG2, aN )
Quá trình lặp lại cho đến khi hoặc tìm thấy hoặc phạm vi tìm kiếm bằng rỗng.
Thủ tục
	 Procedure TK_nhiphan;
	var d,c:longint;	
	begin	
	d:=1;
	c:=n;
	while d<=c do
	begin
	G:=(d+c) div 2;
	if a[G] = k then 
	begin
	writeln(‘tim thay’);
	break;
	end
	 	else
	if a[G] > k then c:=G-1
	else d:=G +1;
	end;
 end;
Nhận xét: 
 Do độ phức tạp của thuật toán tìm kiếm nhị phân là O(logn) và độ phức tạp của thuật toán tìm kiếm tuần tự là O(n) nên thời gian thực hiện chương trình nhanh, thuật toán tìm kiếm nhị phân tối ưu hơn.
2.3.4 Bài toán số nguyên tố
	- Sử dụng định nghĩa (tính chất chia hết sử dụng vào lặp for- do)
	- Sử dụng sàng nguyên tố
	- Sử dụng tính chất chia hết cho 2 và 3
 Ý tưởng thuật toán sử dụng tính chất chia hết dùng vòng lặp for- do
- Kiểm tra lần lượt từng số nguyên N trong [2, N]
- Nếu N=1 thì N không phải số nguyên tố
- Nếu 1 < N < 4 thì N nguyên tố
- N>= 4 và không có ước trong [ 2, N] à nguyên tố
 Hàm sử dụng định nghĩa:
	Function KT1(N:longint): boolean;
	Var i: longint;
	Begin
	if N = 1 then exit (false);
	for i:= 2 to trunc(sqrt(N)) do
	if N mod i = 0 then exit(false);	
	exit(true);
	end;
 Sử dụng sàng nguyên tố 
- Đánh dấu tất cả các số đều là số nguyên tố
- Với mỗi số nguyên tố < N
	+ Đánh dấu các bội lớn hơn nó không phải số nguyên tố
	+ Tìm số tiếp theo đánh dấu là số nguyên tố, nếu không còn số nào thì thoát chương trình
-Các số bị đánh dấu là các số nguyên tố
 Thủ tục sàng nguyên tố
	Procedure Sang_NT;;
	var i,j: longint
	begin
	fillchar(F,sizeof(F),true);
	F[1]:= false;
	for i:= 2 to trunc(sqrt(N)) do
	if F[i] then
	for j:=2 to n div I do
	F[i*j] := false;
	End;
Sử dụng tính chất chia hết cho 2 và 3
Thuật toán:	- Các số nguyên tố là số lẻ (trừ số 2)
	- Các số nguyên tố có dạng 6k ± 1, 6k -1 (trừ số 2 và số 3) vì số có dạng 6k ± 2 thì chia hết cho 2; dạng 6k ± 3 thì chia hết cho3
	- Kiểm tra xem N có chia hết cho 2,3 và các số có dạng 6k ± 1 trong đoạn [5, N]
Hàm sử dụng tính chất chia hết cho 2 và 3
	Function KT2(N:longint): boolean;
	var i,x:longint;
	begin	
	if (N = 2) or (N = 3) then exit(true);
	if (N = 1 ) or (N mod 2 = 0) or (N mod 3 = 0) then exit(false); 
	x:=trunc(sqrt(N));
	i:=-1;
	repeat
	inc(i,6);
	if (n mod i = 0) or (n mod (i+2)=0)
	then break;
	until i > x;
	exit(i>x);
end;
Nhận xét:
- Thuật toán theo sử dụng tính chất chia hết cho 2 và 3 giảm các số cần kiểm tra trong [2, N] à các số có dạng 6k ± 1,trong [5, N].
- Thuật toán sàng nguyên tố chỉ dùng khi dữ liệu cho <=108.
- Độ phức tạp thuật toán 1: O(n), thuật toán sàng nguyên tố O(log n)
2.3.5 Bài toán đoạn con gồm các phần tử liên tiếp và không liên tiếp tổng bằng S
	- Dùng quay lui
	- Dùng quy hoạch động
Ý tưởng thuật toán dùng quay lui
Chọn các dãy con bằng dãy nhị phân có độ dài n: t[1], t[2], t[n], t[i] = 1 thì phần tử thứ i chọn.
Ta cần tìm dãy nhị phân thỏa mãn: t[1].a[1] + t[2].a[2] + +t[n].a[n] = S
Ta có 2n lần duyệt.
Gọi Td là tổng các số dương, Ta là tổng các số âm của dãy. Nếu bài toán thỏa thì Ta Td thì bài toán vô nghiệm.
Ta thấy S thuộc khoảng (Tmin, Tmax). Với t[1] thì Tmin = Ta và Tmax = Td
Với t[i]: + Nếu t[i] = 0 thì nếu t[i] < 0 thì Tmin := Tmin – t[i]
 nếu t[i] > 0 thì Tmax:= Tmax – t[i]
	+ Nếu t[i] =1 thì nếu t[i] < 0 thì Tmin := Tmin + t[i]
 Nếu t[i] < 0 thì Tmin := Tmin + t[i]
Thủ tục dùng quay lui:
	Procedure Quaylui(j,Tmax,Tmin:longint);
	Var i: byte;
	t1, t2:longint;
	begin
	for i:=0 to 1 do
	begin
	t1:= Tmin;
	t2:=Tmax;
	if i = 0 then if t[i] < 0 then t1:=t1 – t[i]
	else t2:= t2 – t[i]
	else if t[i] < 0 then t2:=t2 + t[i]
	 else t1:=t1 + t[i];
	if (t1 <= S) and (S <= t2) then
begin
 a[j]:=i;
 if j = n then begin inc(d);
 if d= 1 then x:=y;
	 { x, y: array[1..max] of byte;}
	 end
 else Quaylui(j+1,t1,t2);
	 end;
 end;
 end; 
Ý tưởng thuật toán dùng quy hoạch động:
Ta có bài toán cơ sở: f[i]:=’0’
g[i]:=n+1
Công thức quy hoạch động:
 f[j]:=CongSL(f[j] , f[j - a[i]])
Nếu f[j] > ‘0’ thì g[j]:= Min(g[j] , i)
(Hàm CongSL: Hàm cộng 2 số lớn)
Đoạn chương trình thực hiện thuật toán:
f[0]:=1;
for i:=1 to S do f[i]:=’0’;
for i:=1 to S do g[i]:= n + 1;
for i:=1 to n do 
	begin
	if a[i] > S then continue;
	for j:= S downto a[i] do 
	begin
	f[j]:= CongSL(f[j], f[j – a[i]]);
 if (f[j] > ‘0’) then 
	g[j]:= min(g[j],i);
 end;
 end;
Nhận xét:
- Bài toán dùng thuật toán quay lui khi xây dựng bài toán tìm dãy nhị phân ta đã loại bỏ được 1 số dãy đáng kể, nhưng nhược điểm thuật toán chạy chậm. Do đó, dùng thuật toán quy hoạch động để quét được hết các test của bài toán.
2.4 Hiệu quả của sáng kiến kinh nghiệm
	- Giúp học sinh biết cách lựa chọn và cài đặt thuật toán tối ưu, hiệu quả đem lại rất rõ nét, tránh học sinh mất test khi giải toán và mất điểm khi thực hành cũng như trong các bài thi.
	- Học sinh nâng cao tính tư duy, sáng tạo, vận dụng linh hoạt các thuật toán tối ưu khi đã lựa chọn. Do đó thời gian để học sinh thiết kế và giải toán nhanh hơn. Đồng thời giúp học sinh yêu thích môn tin học, đặc biệt là lập trình.
	- Chương trình THPT hiện nay, ngôn ngữ lập trình và phần mềm thay đổi qua thời gian, nhưng các thuật toán cũng như việc lựa chọn thuật toán phù hợp với từng bài toán là bắt buộc.
	- Qua các cuộc thi giáo viên giỏi cấp trường tổ chức hàng năm, bản thân tôi có thêm nhiều kinh nghiệm, nâng cao chuyên môn. Tôi tiếp tục tìm tòi, học hỏi ở bạn bè, đồng nghiệp, nghiên cứu sách, học qua các tài liệu, internetđể tìm thêm nhiều thuật toán hay phục vụ cho công việc.
3. KẾT LUẬN, KIẾN NGHỊ
3.1 Kết luận
Thông qua việc lựa chọn các thuật toán tối ưu để giải các bài toán:
 - Chương trình THPT hiện nay, ngôn ngữ lập trình thay đổi qua thời gian, có thể nói ngôn ngữ lập trình Pascal trong chương trình lớp 11 xem như đã “cũ”. Thế nhưng các sử dụng thuật toán, đặc biết là lựa chọn và thiết kế thuật toán luôn quan trọng.
 - Thông qua các tiết bài tập và các tiết thực hành, giáo viên biết được những nhược điểm của học sinh trong tư duy về thuật toán. Từ đó giúp học sinh dần hình thành tư duy logic chặt chẽ, biết sử dụng tư duy thuật toán để giải quyết các bài toán cụ thể.
 - Khi học Pascal hầu hết học sinh thấy khó và thấy “mới”, từ môn học đến cách học. Những thao tác và thực hành nhiều như cách sử dụng internet, sử dụng phần mềm soạn thảo văn bản word,không còn tác dụng, học thuộc bài cũng khó. Lúc này học sinh phải học cách tư duy logic, tìm hiểu các thuật toán, biết cách lựa chọn thuật toán nào là tối ưu, viết những dòng lệnh trên máy tính phải chính xác đến từng dấu chấm, dấu phẩy
3.2 Kiến nghị
 	Để giúp học sinh yêu thích môn tin học, đặc biệt là lập trình rất mong sự quan tâm, tạo điều kiện của nhà trường về mặt cơ sở vật chất (tương đối đủ máy tính, máy chiếu, chất lượng máy nâng lên, bảo trì sửa chữa thường xuyên hơn).
	Mặc dù đã cố gắng nhưng đề tài tôi viết còn nhiều hạn chế, mong sự góp ý của bạn bè, đồng nghiệp để đề tài hoàn thiện và có tính thực tiễn hơn trong công việc giảng dạy của mình. Tôi xin chân thành cảm ơn.
XÁC NHẬN CỦA THỦ TRƯỞNG ĐƠN VỊ
Thanh Hóa, ngày 20 tháng 4 năm 2019
Tôi xin cam đoan đây là SKKN do tôi viết, không sao chép nội dung của người khác.
 Nguyễn Thị Đào
TÀI LIỆU THAM KHẢO
1. Giải thuật và lập trình – thầy Lê Minh Hoàng
2. https://drive.google.com/file/d/0BwcTB8a10LBweWxNcExnVzF5dG8/view 
 (Tài liệu giáo khoa chuyên tin)
3. https://drive.google.com/file/d/0BwcTB8a10LBwZHh0c3p0M2NqZ1E/view
 (Một số vấn đề đáng chú ý môn tin học)
4. Giáo trình thuật toán và kỹ thuật lập trình Pascal- Nhà xuất bản Hà Nội 
5. https://tailieu.vn/doc/sang-tao-trong-thuat-toan-va-lap-trinh-945871.html
	(Sáng tạo trong thuật toán và lập trình)
DANH MỤC
SÁNG KIẾN KINH NGHIỆM ĐÃ ĐƯỢC HỘI ĐỒNG SÁNG KIẾN KINH NGHIỆM SỞ GIÁO DỤC VÀ ĐÀO TẠO XẾP LOẠI 
Họ và tên tác giả: Nguyễn Thị Đào
Chức vụ: Giáo viên 
Đơn vị công tác: Trường THPT Nông Cống 1.
TT
Tên đề tài SKKN
Cấp đánh giá xếp loại
Kết quả đánh giá xếp loại
Năm học đánh giá xếp loại
1.
Xây dựng hệ thống trực tuyến trong mạng nội bộ
Sở GD&ĐT Thanh Hóa
C
2016 – 2017
----------------------------------------------------