SÁNG KIẾN KINH NGHIỆM

ĐỀ TÀI:
"DẠY HỌC THUẬT TOÁN TÌM KIẾM NHỊ PHÂN TRONG TIN
HỌC LỚP 11 THEO PHƯƠNG PHÁP TINH CHẾ TỪNG BƯỚC"


PHẦN I: MỞ ĐẦU
LÝ DO CHỌN ĐỀ TÀI
Phương pháp dạy học có vai trò quan trọng trong quá trình giáo dục, đó là những hoạt
động và giao lưu của thầy và trò nhằm đạt được mục tiêu giáo dục. Để đạt được mục tiêu
giáo dục thì việc lựa chọn phương pháp dạy học thích hợp là vấn đề quan trọng. Mỗi bài
dạy có thể có nhiều phương pháp dạy khác nhau, và mỗi phương pháp dạy thì có thể thực
hiện ở nhiều bài học. Mặt khác, trên thực tế hiện nay, các phương pháp dạy học truyền
thống không đáp ứng được nhu cầu và mục tiêu dạy học. Việc đổi mới phương pháp là
vấn đề then chốt để có được những bài dạy hay và đạt hiệu quả cao. Văn kiện Đại hội đại
biểu toàn quốc lần thứ XI của Đảng cộng sản Việt Nam họp tháng 01 năm 2011 đưa ra
chiến lược phát triển kinh tế - xã hội 2011 – 2020 có nêu yêu cầu: “Đổi mới mạnh mẽ nội
dung, chương trình, phương pháp dạy và học ở tất cả các cấp, bậc học”. Như vậy, việc
cấp bách hiện nay là cần phải đổi mới phương pháp dạy học để đáp ứng nhu cầu học tập
của người học và xã hội.
Đối với môn Tin học hiện nay trong trường phổ thông vẫn còn là mới mẻ, bên cạnh
đó phương pháp để dạy học môn học còn chưa tiếp cận nhiều đến giáo viên. Chính vì
điều này thì việc dạy môn Tin học cũng sẽ là một thử thách đối với các giáo viên Tin học
trong tỉnh nói chung. Trong đó, việc dạy lập trình cho học sinh cần phải có những
phương pháp thích hợp để đạt hiệu quả cho học về hiểu thuật toán và cài đặt thuật toán
trên một ngôn ngữ lập trình. Trong sáng kiến kinh nghiệm này tôi muốn đưa ra áp dụng
một phương pháp dạy học để phát triển tư duy cho học sinh trong việc cài đặt thuật toán
đó là phương pháp tinh chế từng bước. Phương pháp này được áp dụng thông qua đề tài:
“Dạy học thuật toán tìm kiếm nhị phân trong tin học lớp 11 theo phương pháp tinh chế
từng bước”. Mặc dù nội dung thuật toán tìm kiếm nhị phân đã được giảm tải

CHƯƠNG 1: CƠ SỞ LỰA CHỌN ĐỀ TÀI
1.1 CƠ SỞ LÝ LUẬN
Việt Nam đang trong thời kỳ hội nhập nền kinh tế thế giới WTO (World Trade
Organizasion) với những bước biến chuyển mới đã tạo cơ hội và thách thức không ít đến
các lĩnh vực trong đó có giáo dục. Giáo dục là lĩnh vực được xem là quan trọng của đất
nước, một đất nước có mạnh hay không là nhờ vào nền giáo dục. Việc phát triển nền giáo
dục của đất nước cần phải đáp ứng yêu cầu của một nền kinh tế tri thức và xã hội tri thức
trong thời kỳ này. Một trong những vần đề không kém phần quan trọng trong nền giáo
dục đó là công tác dạy học. Để dạy học tốt thì mục tiêu đặt ra làm thế nào để người học
chiếm lĩnh được tri thức nhân loại, vận dụng nó vào đời sống thực tiễn của xã hội. Muốn
vậy người thầy cần phải có cách thức hay nói một cách tổng quát đó là phương pháp dạy
học đạt hiệu quả. Việc đổi mới phương pháp được đưa ra rất nhiều trong các văn kiện,
nghị quyết, chiến lược của Đảng và Nhà nước về giáo dục trong xu thế hiện nay. Nghị
quyết Hội nghị lần thứ hai, Ban chấp hành Trung ương Đảng khóa VIII: "Đổi mới mạnh
mẽ phương pháp giáo dục và đào tạo, khắc phục lối truyền thụ một chiều, rèn luyện thành
nếp tư duy sáng tạo của người học, từng bước áp dụng các phương pháp tiên tiến và
phương pháp hiện đại vào quá trình dạy học, bảo đảm thời gian tự học, tự nghiên cứu của
học sinh...”.


Trên cơ sở khái niệm về phương pháp dạy học, một cách thức tiến hành các hoạt
động giao lưu của giáo viên gây ra các cách thức hoạt động và giao lưu của học sinh để
đạt được mục tiêu giáo dục. Việc đổi mới phương pháp ở đây là đổi mới cách thức, đổi
mới các hoạt động tạo ra niềm vui, niềm hứng thú cho học sinh chiếm lĩnh tri thức một
cách có hiệu quả. Điều này thể hiện ở ngay trong các bài dạy, người giáo viên có vai trò
mới điều khiển các hoạt động giao lưu ấy, tức là các tình huống để học sinh tìm hiểu tự
kiến tạo tri thức.
Tri thức mà học sinh chiếm lĩnh được thực hiện theo lý thuyết của vùng phát triển
gần nhất do nhà tâm lí học người Nga Vưgôtxki L.X đưa ra. Đó là, những tri thức mà học
sinh đã có được nằm ở vùng phát triển hiện tại và những tri thức cần yêu cầu học sinh đạt

dụng vào thuật toán khác, hoặc có thể cho các nội dung khác nội bộ trong môn Tin học.
1.2 CƠ SỞ THỰC TIỄN
Đặc điểm môn
Môn Tin học đến nay không còn là môn học mới mẻ đối với học sinh phổ thông, bởi
học sinh đã được làm quen nó ngay ở các cấp học dưới. Đây là một thuận lợi cho học
sinh, học sinh không phải học từ đầu để làm quen với môn học. Tuy nhiên, môn học này
có đặc thù riêng đó là nó liên quan đến việc sử dụng công cụ máy tính để thực hiện và
những nội dung trong môn học dễ bị lạc hậu do sự phát triển ngành khoa học Tin học là
rất nhanh. Sự liên quan của môn Tin học với các môn học khác là nhiều, vì vậy học sinh
sẽ phải vất vả để xem lại, tìm kiếm lại tri thức ở các môn học khác. Đặc biệt nội dung lập


trình trong môn học Tin học lại có liên quan rất nhiều đến tư duy Toán học, mà nếu học
sinh yếu tư duy về Toán học thì sẽ rất là khó khăn. Muốn giải quyết được việc này thì
giáo viên cần phải làm sao tách ra, đưa học sinh nhìn theo một tư duy mới gần gũi với
học sinh để học sinh dễ dàng hiểu hơn.
Giáo viên
Nhiều giáo viên còn hạn chế về nội dung Tin học, trình độ, khả năng cập nhật thông
tin. Không chỉ vậy, một số giáo viên còn yếu khả năng tư duy về thuật toán, hay nói cách
khác là chưa hiểu rõ thuật toán để diễn đạt trong việc dạy lập trình. Chính điều này đã
làm cho giáo viên hạn chế trong việc đổi mới phương pháp, có khi giáo viên dạy thuật
toán hay dạy lập trình còn theo kiểu hàn lâm, kinh viện, có khi cứ dạy lập trình là sử dụng
máy tính gõ luôn chương trình và chạy. Dẫn đến học sinh mất đi khả năng tìm hiểu và tư
duy giải quyết các thuật toán, hứng thú trong việc học lập trình.
Nhà trường
Về phía nhà trường thì một mặt còn chưa hiểu thấu đáo về học môn Tin học, cho
rằng học môn Tin học là học cách sử dụng máy tín, đó là sai lầm về mục tiêu dạy học
môn học. Ngoài ra về mặt cơ sở vật chất như phòng máy, số lượng máy tính, các phần
mềm hỗ trợ dạy học, thiết bị liên quan, … chưa đáp ứng được yêu cầu cho dạy và học
môn Tin học.

Phương pháp tính chế từng bước sẽ thực hiện phân tích các câu lệnh chi tiết hơn có thể là
ở trên một ngôn ngữ lập trình Pascal. Nói một cách dễ hiểu là phương pháp tình chế từng


bước sẽ làm rõ dần các bước thực hiện trong thuật toán bằng quá trình chuyển nó thành
chương trình trên một ngôn ngữ cụ thể. Các bước của thuật toán dần dần được làm rõ lên
để người đọc cảm nhận thuật toán viết trên ngôn ngữ lập trình. Đây là một phương pháp
mà khi giáo viên sẽ hướng học sinh nhìn rõ dần thuật toán trên ngôn ngữ cụ thể, khi đó
việc cài đặt thuật toán sẽ dễ áp dụng cho các bài toán đơn giản khác sẽ dễ dàng hơn và
tối ưu hơn, dễ hiểu hơn.
2.2 BÀI TOÁN TÌM KIẾM
Cho dãy A gồm N số nguyên khác nhau: a1, a2, ...,aN và một số nguyên k (gọi tắt là
khóa k). Cần biết có hay không chỉ số i (0 ≤ i ≤ N) mà ai = k. Nếu có hãy cho biết chỉ số
đó.
Xác định bài toán:
Input: Dãy A gồm N số nguyên khác nhau a1, a2, ...,aN và số nguyên k;
Output: Chỉ số i mà ai = k hoặc thông báo không có phần tử nào của dãy A có giá
trị bằng k.
2.3 THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Xét bài toán ở một trường hợp đặc biệt của Input đó là dãy A đã được sắp xếp tăng
dần (a1
Yêu cầu:
- Học sinh phát biểu được bài toán tìm kiếm và đưa ra được ý tưởng thuật toán tìm
kiếm nhị phân.
- Học sinh thực hành áp dụng được thuật toán tìm kiếm nhị phân cài đặt chương
trình cho một bài toán đơn giản (tìm kiếm một phần tử thỏa mãn điều kiện nào đó trong
dãy các phần tử đã biết).
Đối tượng học sinh:
- Học sinh lớp 11.
- Mức độ: Trung bình khá
Mức độ khó của thuật toán đối với học sinh:
- Xác định dãy để thực hiện tìm kiếm. Sự thay đổi biến Dau và Cuoi trong quá trình
lặp
- Xác định phần tử ở giữa của dãy cần xét để so sánh với khóa tìm kiếm. Sự thay đổi
biến Giua trong quá trình lặp
- Điều kiện để lặp lại việc tìm kiếm trên dãy mới và kết thúc quá trình tìm kiếm,
thông báo kết quả.
Phương pháp thực hiện:
- Tinh chế thuật toán từng bước một để đi đến chương trình cụ thể.
- Giáo viên có thể thực hiện bằng việc sử dụng máy tính, máy chiếu và phần mềm
trình chiếu Microsoft Powerpoint để trình chiếu các Slide đã được chuẩn bị sẵn.
Thực hiện bài giảng:


Giáo viên đặt vấn đề để đưa ra những tình huống hướng học sinh vào việc tìm hiểu ý
tưởng thuật toán tìm kiếm nhị phân:
Bài toán tìm kiếm và việc tìm kiếm tuần tự
- Tìm kiếm là một yêu cầu rất thường xuyên trong đời sống hàng ngày cũng như
trong tin học
- Ví dụ:
+ Tìm kiếm một học sinh trong một lớp học

- Có 2 bạn học sinh có chiều cao a và b, trong đó a
Xác định vị trí phần tử đứng giữa. (?)
Nếu k= Phần tử đứng giữa thì Thông báo
Còn lại
nếu k> Phần tử đứng giữa thì
Xét trường hợp (N/2)-1 phần tử phía sau (từ sau phần tử đứng giữa đến
phần tử thứ N) (?)
còn lại
Xét trường hợp (N/2)-1 phần tử phía trước (từ phần tử thứ 1 đến phần
tử trước phần tử đứng giữa) (?)

Tinh chế lần 2:
Program Tim_Kiem;
Var a: array[1..N] of integer;
i, k, Dau, Cuoi, Giua: integer;
Begin
Write(‘Nhap N =’); readln(N);
for i:=1 to N do
Begin
Write(‘a[’ ,i, ‘] =’); readln(a[i]);


End;
Dau:= 1; Cuoi:= N; {dùng biến Dau va Cuoi để lưu giữa vị trí đầu và cuối của dãy
ban đầu. Ký hiệu để xác định dãy số như sau: (Dau, Cuoi), với dãy ban đầu sẽ là (1,N)}
Giua:= (Dau + Cuoi) div 2; {dùng biến Giua để lưu giữ vị trí phần tử đứng
giữa_chia lấy phần nguyên để lấy vị trị giữa tương đối}
if k= a[Giua] then Thông báo
else
if k> a[Giua] then
Xác định dãy (N/2)-1 phần tử phía sau (từ phần tử thứ Giua+1 đến phần

else
Cuoi:= Giua-1; {quay lại xác định vị trí giữa và tìm kiếm trên dãy (1,
Giua-1), Dau = 1 (?)}
End.

Cuoi = Giua-1
Dau

Dau = Giua+1

Tinh chế lần 4:
Program Tim_Kiem;
Var a: array[1..N] of integer;
i, k, Dau, Cuoi, Giua: integer;
Begin

Cuoi


Write(‘Nhap N =’); readln(N);
for i:=1 to N do
Begin
Write(‘a[’ ,i, ‘] =’); readln(a[i]);
End;
Dau:= 1; Cuoi:= N;
Đoạn lệnh lặp lại với dãy mới (1, Giua-1) hoặc (Giua+1,N) và dãy mới lại tiếp tục
được chia đôi để tìm kiếm nên số lần lặp chưa biết trước (?)
Begin
Giua:= (Dau + Cuoi) div 2;
if k= a[Giua] then Thông báo

End.


Tinh chế lần 6:
Program Tim_Kiem;
Var a: array[1..N] of integer;
i, k, Dau, Cuoi, Giua: integer;
Begin
Write(‘Nhap N =’); readln(N);
for i:=1 to N do
Begin
Write(‘a[’ ,i, ‘] =’); readln(a[i]);
End;
Dau:= 1; Cuoi:= N;
{Việc chia đôi dãy để tìm kiếm kết thúc khi dãy không còn phần tử, khi đó quá
trình lặp kết thúc. Mà hai biến Dau, Cuoi dùng để xác định dãy đang xét nên ta sẽ so sánh
giá trị hai biến này (tức là khi Dau
i, k, Dau, Cuoi, Giua: integer;
Tim_thay: boolean;
Begin
Write(‘Nhap N =’); readln(N);
for i:=1 to N do
Begin
Write(‘a[’ ,i, ‘] =’); readln(a[i]);
End;


Dau:= 1; Cuoi:= N;
Tim_thay:=False;
While Dau a[Giua] then
Dau:= Giua+1
else
Cuoi:= Giua-1;
End;
if Tim_thay then writeln(‘Tim thay, vi tri’, Giua)
else writeln(‘Khong co phan tu nao trong day co gia tri la ’, k);
End.
Vậy sau 8 lần tinh chế từ ý tưởng thuật toán tìm kiếm nhị phân của bài toán tìm kiếm
ta đã có một chương trình cụ thể viết trên ngôn ngữ lập trình Pascal.
Mô phỏng thuật toán với dãy số có 10 phần tử như sau: (2, 4, 5, 6, 9, 21, 22, 30, 31,
33) với k = 21.