Giáo viên: Nguyễn Thị Phương Ngân

Tổ: Lý – Tin - KTCN

THÔNG TIN CHUNG VỀ SÁNG KIẾN

1. Tên sáng kiến:
Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải bài
toán trên máy tính.
2. Lĩnh vực áp dụng sáng kiến:
Áp dụng trong giảng dạy lập trình môn tin học 11.
3. Thời gian áp dụng sáng kiến:
Từ ngày 20, tháng 09, năm 2014 đến ngày 20, tháng 4, năm 2016.
4. Tác giả:
Họ và tên: Nguyễn Thị Phương Ngân.
Năm sinh: 1986.
Nơi thường trú: Khu Tập thể giáo viên trường THPT Mỹ Tho.
Trình độ chuyên môn: cử nhân sư phạm tin học.
Chức vụ công tác: Giáo viên dạy môn Tin học.
Nơi làm việc: Trường THPT Mỹ Tho.
Điện thoại: 0975061791.
5. Đơn vị áp dụng sáng kiến:
Tên đơn vị: Trường THPT Mỹ Tho.
Địa chỉ: xã Yên Chính – Ý Yên – Nam Định.

Trường THPT Mỹ Tho

1


Giáo viên: Nguyễn Thị Phương Ngân

mới, chẳng hạn như máy hơi nước – đối với nền văn minh công nghiệp, máy
tính điện tử - đối với nền văn minh thông tin. Máy tính chính là công cụ trợ
giúp cho sự phát triển Tin học, có thể đáp ứng nhu cầu tính toán, lưu trữ, tìm
kiếm,.., và xử lý thông tin một cách có hiệu quả.
Máy tính có tốc độ xử lý nhanh (hàng tỉ lệnh trên 1 giây) nhưng nó cũng có
giới hạn. Tất cả các máy tìm kiếm (ví dụ như google, yahoo hay gmail…) đều
được lập trình bằng các đoạn lệnh của một Ngôn ngữ lập trình nào đó nhưng
máy nào sử dụng thuật toán tối ưu (tốt nhất ) thì tìm kiếm được nhanh, chính
xác và sẽ được đông đảo người dùng lựa chọn sử dụng.
Với một bài toán cũng vậy, một bài toán có thể có nhiều thuật toán để giải
nhưng ta nên lựa chọn thuật toán tối ưu (có số phép tính ít nhất). Vậy việc lựa
chọn một thuật toán đưa tới kết quả nhanh là một đòi hỏi thực tế cần được
quan tâm đặc biệt. Do đó, trong khi viết chương trình ta nên tìm cách viết sao
cho chương trình thực hiện càng ít phép toán càng tốt. Xuất phát từ thực tế đó
tôi đưa ra đề tài: “Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập
trình giải bài toán trên máy tính” nhằm định hướng cho các em học sinh
biết phân tích, lựa chọn thuật toán tối ưu trước khi lập trình giải bài toán trên
máy tính.
II. Mô tả giải pháp
1. Thực trạng
Nhận thấy tầm quan trọng của Tin học đối với thực tế cuộc sống, mọi lĩnh
vực, ngành nghề, từ năm học 2007- 2008 Bộ giáo dục và đào tạo đã đưa môn
Tin học thành môn học chính thức ở tất cả các trường Trung học cơ sở, Trung
Trường THPT Mỹ Tho

3


Giáo viên: Nguyễn Thị Phương Ngân



4


Giáo viên: Nguyễn Thị Phương Ngân

Tổ: Lý – Tin - KTCN

2.2.1. Nhắc lại các bước lập trình giải bài toán trên máy tính
Thông thường khi lập trình giải bài toán trên máy tính học sinh hay bị mắc
sai lầm là viết chương trình luôn mà bỏ qua các bước giải bài toán trên máy
tính, vì vậy có khi chương trình đã chạy nhưng sai kết quả vì hiểu sai đề, hoặc
thuật toán chưa khả thi…
Vì vậy khi dạy lập trình giáo viên nhắc học sinh không nên ngay lập tức
viết chương trình mà nên nhớ lại các bước giải bài toán trên máy tính. Việc
giải bài toán trên máy tính thường được tiến hành qua 5 bước sau:
+ Bước 1: Xác định bài toán;
+ Bước 2: Lựa chọn hoặc thiết kế thuật toán;
+ Bước 3: Viết chương trình;
+ Bước 4: Hiệu chỉnh;
+ Bước 5: Viết tài liệu.
Trong 5 bước giải bài toán trên máy tính thì bước lựa chọn hoặc thiết kế
thuật toán đặc biệt rất quan trọng để các em có thể phân tích đề bài, tìm ra
hướng giải, thuật toán phù hợp.
2.2.2. Một số khái niệm
2.2.2.1. Khái niệm thuật toán
2.2.2.1.1. Thuật toán là gì
Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp
xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy từ
Input của bài toán, ta nhận được Output cần tìm.

được chứng minh và thường được gọi tắt là độ phức tạp của thuật toán, kí hiệu
là O(..). Độ phức tạp của thuật toán càng nhỏ thì thuật toán càng chạy nhanh
và khả thi.
Thời gian thực hiện một thuật toán phụ thuộc vào rất nhiều yếu tố như: kích
thước của dữ liệu đưa vào, lựa chọn, bố trí kiểu dữ liệu có hợp lý không…
Vậy để tính toán thời gian thực hiện thuật toán ta sẽ đếm số câu lệnh mà nó
thực hiện, hoặc trong một số trường hợp có thể đếm cụ thể phép tính số học,
so sánh, gán…mà thuật toán đòi hỏi thực hiện hoặc có thể chạy trực tiếp
chương trình bằng một ngôn ngữ lập trình cụ thể và thử nghiệm nó nhờ một số
bộ dữ liệu nào đấy rồi so sánh kết quả thử nghiệm với kết quả mà ta đã biết.
c. Ngôn ngữ thuật toán
Trường THPT Mỹ Tho

6


Giáo viên: Nguyễn Thị Phương Ngân

Tổ: Lý – Tin - KTCN

- Ngôn ngữ dùng để miêu tả thuật toán gọi là ngôn ngữ thuật toán.
- Thuật toán thường được mô tả bằng một dãy các lệnh. Bộ xử lý sẽ thực
hiện các lệnh đó theo một trật tự nhất định cho đến khi gặp lệnh dừng thì kết
thúc.
- Ngôn ngữ thuật toán bao gồm:
+ Ngôn ngữ liệt kê từng bước;
+ Sơ đồ khối;
+ Ngôn ngữ lập trình
- Trong đề tài này tôi ưu tiên sử dụng ngôn ngữ liệt kê từng bước và ngôn
ngữ lập trình Pascal.

đổi và sắp xếp nhanh Quick sort để độc giả có sự so sánh và sử dụng linh hoạt
trong trường hợp cụ thể.
2.2.3.1.2.1. Thuật toán sắp xếp bằng tráo đổi
* Ý tưởng phương pháp: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu
số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. Việc đó được lặp lại cho
đến khi không có sự đổi chỗ nào nữa.
* Thuật toán:
Procedure sapxeptraodoi;
Var i, j, tg: integer;
begin
For i:=1 to n-1 do
For j:= n downto i+1 do
If a[j]< a[j-1] then
Begin
Tg:=a[j];
A[j]:=a[j-1];
A[j-1]:=tg;
End;
End;
* Nhận xét: Thuật toán trên sử dụng 2 vòng lặp for… => mỗi lần duyệt i phải
thực hiện n-1 phép so sánh để tìm ra giá trị lớn nhất đẩy về cuối dãy. Vậy số

Trường THPT Mỹ Tho

8


Giáo viên: Nguyễn Thị Phương Ngân

phép toán cần thiết là: (n-1)+(n-2)+…+1=

end;

Trường THPT Mỹ Tho

9


Giáo viên: Nguyễn Thị Phương Ngân

Tổ: Lý – Tin - KTCN

until i>j;
qs(l,j); qs(i,h);
end;
* Nhận xét: Thuật toán Qick-sort có độ phức tạp cỡ ~ O(nlogn)
2.2.3.1.3. Nhận xét chung
So sánh hai thuật toán trên ta thấy thuật toán sắp xếp nổi bọt tuy dễ cài đặt
nhưng có độ phức tạp cỡ O(n 2) còn thuật toán Qick-sort chỉ có độ phức tạp cỡ
O(nlogn), có nghĩa là thời gian thực hiện của Qick-sort nhanh hơn rất nhiều.
Vậy tùy vào từng bài toán cụ thể mà ta nên lựa chọn phương pháp sắp xếp phù
hợp. Nếu tập dữ liệu đưa vào nhỏ (
else write(f2,'khong tim thay');
* Nhận xét:
Tìm kiếm tuần tự là kỹ thuật tìm kiếm rất đơn giản và cổ điển, trong thuật
toán ta sử dụng thêm câu lệnh break để sau khi đã tìm thấy khóa k có trong
dãy thì thoát luôn ra khỏi vòng lặp và kết thúc chương trình, điều này giúp
giảm đi đáng kể số lượng phép toán.
Ta thấy với giải thuật trên, trường hợp tốt nhất là tìm thấy khóa k nằm ngay
đầu dãy thì chỉ cần 1 phép so sánh; trường hợp trung bình là khóa k nằm ở vị
trí giữa dãy cần

n +1
phép so sánh, trường hợp xấu nhất là tìm thấy khóa k
2

nằm ở cuối dãy cần n+1 phép so sánh => Thời gian thực hiện của giải thuật
trên là ~ O(n).
2.2.3.2.1.2. Thuật toán tìm kiếm nhị phân
* Xác định bài toán:

Trường THPT Mỹ Tho

11


Giáo viên: Nguyễn Thị Phương Ngân

Tổ: Lý – Tin - KTCN

- Input: dãy a gồm N số nguyên khác nhau a1, a2,…, aN (dãy A đã được sắp
theo thứ tự tăng dần) và một số nguyên k.

12


Giáo viên: Nguyễn Thị Phương Ngân

Tổ: Lý – Tin - KTCN

if k>a[giua] then i:=giua+1
else j:=giua;
end;
if a[i]=k then vt:=i
else vt:=0;
if vt>0 then writeln('da tim thay tai vi tri:',vt)
else write('khong tim thay');
* Nhận xét:
Trong giải thuật trên trường hợp tốt nhất là tìm thấy khóa k = a Giua thì việc
tìm kiếm kết thúc quá đơn giản (chỉ cần 1 phép so sánh). Còn nếu không
trường hợp xấu nhất người ta cũng chứng minh được thời gian thực hiện của
giải thuật trên là ~ O(log2n).
2.2.3.2.2 Nhận xét chung
So với thuật toán tìm kiếm tuần tự, thuật toán tìm kiếm nhị phân thực hiện
tìm kiếm trên bảng không lớn hơn [n/2] phần tử. Vậy trong trường hợp bảng
liệt kê đã được sắp thứ tự thì thuật toán tìm kiếm nhị phân tốt hơn thuật toán
tìm kiếm tuần tự rất nhiều, còn trong trường hợp dãy khóa chưa được sắp xếp
thì thời gian chi phí cho sắp xếp cũng phải kể đến. Vì vậy tùy từng trường hợp
đề bài ra ta nên cân nhắc lựa chọn thuật toán sao cho phù hợp để chi phí thực
hiện là ít nhất.
2.2.4. Một số ví dụ minh chứng
2.2.4.1. Ví dụ 1
Giải bài toán cổ (SGK trang 51):

write('So ga la: ',g,' So cho la: ',c);
end;
end.
* Nhận xét: Ta thấy tổng số gà và chó là 36 và tổng số chân là 100. Giả sử tất
cả là chó, thì số con tối đa là 100/4 = 25 (con); tối thiểu là 36 / 4 = 9 (con).
Như vậy chúng ta chỉ cần sử dụng vòng lặp for từ 9->25. Cách này sẽ tối ưu
hơn.
Chương trình minh họa:
Program bai_toan_co_2;

Trường THPT Mỹ Tho

14


Giáo viên: Nguyễn Thị Phương Ngân

Tổ: Lý – Tin - KTCN

uses crt;
var g,c: integer;
begin
clrscr;
for c:=9 to 25 do
begin
g:=36-c;
if ((4*c+2*g)=100) then
write('So ga la: ',g,' So cho la: ',c);
end;
end.

writeln;
{ Bat dau tao b}
for i:=1 to n do
begin
b[i]:=0;
for j:=1 to i do b[i]:=a[i]+a[j];
end;
{ Ket thuc tao b}
for i:=1 to n do write(b[i]:6);
readln
end.
- Chạy thử chương trình với một số bộ test ngẫu nhiên ta có:
n

Mảng a

Mảng b

3

103 226 -37

103 329 292

4

-106 -47 -212 48

-106 -153 -365 -317


Ta có chương trình minh họa khi thay như sau:
program subsum2;
const nmax=100;
type myarray= array[1..nmax] of integer;
var a,b:myarray;
n,i,j:integer;
begin
randomize;
write ('nhap n');
readln(n);
{ Tao ngau nhien mang gom n so nguyen}
for i:=1 to n do a[i]:=random(300)-random(300);
Trường THPT Mỹ Tho

17


Giáo viên: Nguyễn Thị Phương Ngân

Tổ: Lý – Tin - KTCN

for i:=1 to n do write(a[i]:5);
writeln;
b[1]:=a[1];
for i:= 2 to n do b[i]:=b[i-1]+a[i];
for i:=1 to n do write(b[i]:6);
readln
end.
* Chạy lại chương trình với một số bộ test ngẫu nhiên ta có:


10
45

subsum2
2
3
8

* Nhận xét: Nếu sử dụng cách 1 để giải bài toán này thì máy phải thực hiện
n(n+1)/2phép cộng => độ phức tạp của thuật toán ~ O(n2), trong khi sử dụng
cách 2 thì máy chỉ phải thực hiện n-1 phép cộng, tức độ phức tạp của thuật
toán ~ O(n). Vì vậy nhờ việc phân tích như trên ta có thể tiết kiệm được một
lượng tính toán đáng kể giúp chương trình chạy nhanh hơn.
2.2.4.3. Ví dụ 3 (Đề thi học sinh giỏi tỉnh nam định năm học 2015 – 2016)

Trường THPT Mỹ Tho

18


Giáo viên: Nguyễn Thị Phương Ngân

Tổ: Lý – Tin - KTCN

Sở công an Nam Định thực hiện công việc cấp thẻ căn cước công dân năm
2016. Mỗi ngày Sở tiếp nhận N người dân, người thứ i mất t i thời gian (phút)
hoàn thành cấp thẻ. Biết rằng Sở cấp cho người dân theo thứ tự lần lượt, xong
việc người này mới đến người tiếp theo.
Yêu cầu: Em hãy xếp thứ tự cho N người dân sao cho tổng thời gian chờ và
hoàn thành cấp thẻ của N người là ít nhất.

…
+ Thời gian hoàn thành cấp thẻ của người thứ n là tn = tn-1 + A[n]
=> Tổng thời gian chờ và hoàn thành cấp thẻ của N người là t1 +t2 +..+tn
* Lựa chọn thuật toán:
- Vì đề bài cho biết số lượng người dân N <=10 4 => tập dữ liệu đưa vào lớn
=> Ta nên sử dụng thuật toán Qick-sort để sắp xếp (cách này đạt được điểm
tối đa).
- Sau đó ta đi tính tổng thời gian ít nhất.
* Chương trình minh họa:
const fi='CANCUOC.INP';
fo='CANCUOC.OUT';
var n:longint;
a:array[1..10001]of longint;
f1,f2:text;
procedure inp;
begin
assign(f1,fi);
assign(f2,fo);
reset(f1);
rewrite(f2);
end;
procedure out;
begin
close(f1); close(f2);
end;
procedure swap(var x,y:longint);
var tg:longint;
Trường THPT Mỹ Tho

20

for i:=1 to n do read(f1,a[i]);
qs(1,n);
t:=0; s:=0;
Trường THPT Mỹ Tho

21


Giáo viên: Nguyễn Thị Phương Ngân

Tổ: Lý – Tin - KTCN

for i:=1 to n do
begin
inc(t,a[i]);
inc(s,t);
end;
write(f2,s);
end;
begin
inp;
optimiz;
out;
end.
III. Hiệu quả do sáng kiến đem lại
1. Hiệu quả kinh tế
Lựa chọn thuật toán tối ưu trong mỗi bài toán giúp tiết kiệm được một
lượng tính toán đáng kể, làm cho chương trình chạy nhanh hơn, tiết kiệm bộ
nhớ, tài nguyên máy tính.
2. Hiệu quả về mặt xã hội

tìm cách đề xuất thuật toán và viết biết nên lựa chọn thuật toán nào sao
chương trình sao cho chương trình cho chương trình thực hiện càng ít
chạy được và đưa ra được kết quả phép toán càng tốt.
như đề bài yêu cầu.
=> Đứng trước một bài toán các em => Đa số các em nắm được vì sao cần
chưa biết cách phân tích lựa chọn phải lựa chọn thuật toán tối ưu. Từ đó
thuật toán tối ưu, chưa hiểu được vì đứng trước một bài toán các em biết
sao cần phải lựa chọn thuật toán tối cách phân tích lựa chọn thuật toán tốt
ưu khi lập trình giải bài toán trên nhất sao cho chương trình thực hiện
máy tính.

càng ít phép toán càng tốt.

b. Đối với công tác bồi dưỡng học sinh giỏi
Ngay từ những buổi học đầu tiên tôi đã phân tích, giảng giải cho các em
thuật toán tối ưu là gì, sự cần thiết của việc lựa chọn thuật toán tối ưu khi lập
trình giải bài toán trên máy tính; đưa ra các thuật toán cơ bản cần phải nắm

Trường THPT Mỹ Tho

23


Giáo viên: Nguyễn Thị Phương Ngân

Tổ: Lý – Tin - KTCN

vững: sắp xếp mảng, tìm kiếm.. để các em phân tích tìm ra thuật toán tối ưu,
hiểu được vai trò của việc lựa chọn thuật toán tối ưu, tạo tiền đề cho các em tư
duy giải quyết các bài tập phức tạp để đạt kết quả tốt nhất.



Giáo viên: Nguyễn Thị Phương Ngân

Tổ: Lý – Tin - KTCN

PHỤ LỤC
Danh mục các tài liệu tham khảo:
1. SGK tin học 10_NXB Giáo dục;
2. SGK tin học 11_NXB Giáo dục;
3. Toán rời rạc_ Nguyễn Đức Nghĩa – Nguyễn Tô Thành;
4. Cấu trúc dữ liệu và giải thuật_Đỗ Xuân Lôi;
5. Tài liệu giáo khoa chuyên Tin_Lê Minh Hoàng.

Trường THPT Mỹ Tho

25