Sáng kiến kinh nghiệm 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

 Sáng kiến kinh nghiệm
 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
GV Bùi Thiện Quý THPT Hưng Yên Sáng kiến kinh nghiệm
 ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU
 Phương pháp tinh chế từng bước và việc áp dụng vào dạy học thuật toán và lập trình đối
với thuật toán “Tìm kiếm nhị phân” cho học sinh phổ thông.
 Học sinh khối 11, trường THPT Hưng Yên năm học 2012-2013.
 PHƯƠNG PHÁP NGHIÊN CỨU
 Dựa trên cơ sở lý thuyết về phương pháp dạy học nói chung và phương pháp tinh chế 
từng bước đưa vào giảng thuật toán “Tìm kiếm nhị phân” cho học sinh lớp 11.
 Thu thập dữ liệu thông qua phiếu điều tra thông tin mức độ học sinh biết, hiểu và vận 
dụng thuật toán của học sinh sau khi học thuật toán.
 Phân tích đánh giá mức độ học sinh hiểu về thuật toán sau khi dạy, thông qua phân tích
các bảng số liệu và thông kê. 
 Tổng kết rút kinh nghiệm
 THỜI GIAN NGHIÊN CỨU
 Từ tháng 1 năm 2013 đến tháng 2 năm 2013
GV Bùi Thiện Quý 2 THPT Hưng Yên Sáng kiến kinh nghiệm
động đó mà các yêu cầu ở vùng phát triển gần nhất dần dần chuyển hóa thành vùng phát triển 
hiện tại và các vùng trước kia ở xa thì giờ đây được kéo lại trở thành vùng phát triển gần nhất. 
Cứ như vậy, trình độ học sinh cũng như các tri thức do học sinh chiếm lĩnh được được phát 
triển và hoàn thiện hơn.
 Thực tế hiện nay các môn học đều thực hiện việc đổi mới phương pháp, nâng cao hiệu 
quả chất lượng bài dạy. Đối với môn Tin học thì việc đổi mới phương pháp dạy là hết sức 
quan trọng, bởi môn học có sự phát triển về mặt tri thức và điều đặc biệt là nó liên quan hầu 
như tới các môn học khác. Điều này sẽ rất thuận lợi là nhờ có sự đổi mới ở các môn học khác 
làm tác động đến môn Tin học. Đổi mới phương pháp dạy học Tin học ở các trường phổ 
thông hiện nay chưa được thực hiện nhiều, mặc dù sự phát triển của môn học thì thường 
xuyên nhưng việc đổi mới phương pháp để dạy môn học ở các giáo viên trường phổ thông là 
hạn chế. Một mặt do đặc thù môn học liên quan đến máy tính, đến các môn học khác như: 
Toán, Vật lí, Tiếng Anh, . Một mặt do sự chậm trễ đổi mới ở giáo viên, việc bồi dưỡng 
thường xuyên chưa nhiều, chưa tìm tòi và phát hiện ra những phương pháp mới.
 Trong các nội dung chương trình Tin học phổ thông thì việc dạy học lập trình là một 
việc khó khăn, hầu như các giáo viên đều vấp phải. Bởi nó liên quan đến thuật toán, điều khó 
ở chỗ là để học sinh hiểu thuật toán đã cả là một khó khăn đối với học sinh. Ngoài ra, còn ứng 
dụng thuật toán vào các bài toán khác lại là một việc khó hơn, mà học sinh khi nghe đến thuật 
toán là chúng sợ bởi khả năng tư duy của chúng còn hạn chế. Nếu cứ dạy theo những phương 
pháp thông thường thì học sinh sẽ học một cách máy móc và không hiểu sâu thuật toán hoạt 
động dẫn đến việc chuyển hóa thuật toán để viết trên một ngôn ngữ lập là rất khó thực hiện 
được, do đó để ứng dụng thuật toán đó vào các bài tập đơn giản là không thể làm được. Chính 
vì vậy mà cần đưa ra một phương pháp dạy mới để có thể vừa hiểu thuật toán, vừa biết cách 
xây dựng thuật toán trên một ngôn ngữ lập trình là rất cần thiết. Phương pháp đó không chỉ 
thực hiện ở một thuật toán này mà có thể áp 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
GV Bùi Thiện Quý 4 THPT Hưng Yên Sáng kiến kinh nghiệm
 CHƯƠNG 2: 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
 2.1 PHƯƠNG PHÁP TINH CHẾ TỪNG BƯỚC
 Trước hết chúng ta nói về kỹ năng lập trình, đó là một kỹ năng mà người lập trình 
chuyển hóa thuật toán từ ngôn ngữ tự nhiên (liệt kê hay sơ đồ khối) thành một chương trình 
hoàn chỉnh. Rèn luyện kỹ năng này rất quan trọng bởi nó là một bước tư duy từ thuật toán cho 
đến chương trình trên một ngôn ngữ cụ thể. Nếu việc thực hiện kỹ năng này không tốt thì dẫn 
đến một chương trình tồi và không hiệu quả, thậm chí có thể còn lỗi và sai về thuật toán.
 Để giúp giáo viên, cũng như học sinh có một tư duy tốt về khả năng cài đặt thuật toán ta 
đưa ra một phương pháp gọi tinh chế từng bước hay có thể hiểu là phát triển chương trình 
bằng cách tinh chế từng bước. Một bài toán đưa ra có thể có nhiều lời giải (hay thuật toán) 
khác nhau, tuy nhiên để một giáo viên có thể tổ chức dạy hay hướng dẫn học sinh thực hiện 
viết chương trình sao cho thuật toán của bài toán đó dễ hiểu là một vấn để cần đặt ra. Do đó 
việc tinh chỉnh các bước cho bài toán trong máy tính là phương pháp khoa học, có hệ thống 
giúp chúng ta phân tích các thuật toán và cấu trúc dữ liệu từ đó thành một chương trình. Vậy 
cốt lõi của vấn đề là biết phương pháp phát triển dần dần để chuyển ý tưởng ra thành chương 
trình hoàn chỉnh.
 Một chương trình ban đầu hay nói gần hơn là thuật toán thường được viết dưới dạng tự 
nhiên (ở đây là ngôn ngữ tiếng Việt) thể hiện tổng thể quá trình thực hiện thuật toán. 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: a 1, 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à a i = 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 a 1, a2, ...,aN và số nguyên k;
 Output: Chỉ số i mà a i = 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.
GV Bùi Thiện Quý 6 THPT Hưng Yên Sáng kiến kinh nghiệm
 - 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
 + Tìm kiếm một quyển sách trong thư viện
 + Tìm kiếm một tập tin hay thư mục trong máy tính, .
 - Để đơn giản ta xét một bài toán tìm kiếm đơn giản như sau: Cho một dãy số gồm các 
phần tử a 1, a2, ., aN. Cho biết trong dãy này có phần tử nào có giá trị bằng k (cho trước) hay 
không?
 - Với bài toán trên, ta có thể đưa ra cách làm như sau:
 + So sánh k với phần tử đầu tiên trong dãy A, nếu thấy thì thông báo.
 + Còn lại không thấy thì tiếp tục tìm kiếm ở dãy bắt đầu từ phần tử thứ 2 đến N.
 + Việc làm trên có thể lặp lại N lần nếu phần tử đó nằm ở cuối dãy hoặc không có
phần tử nào.
GV Bùi Thiện Quý 8 THPT Hưng Yên Sáng kiến kinh nghiệm
kiếm ứng với trường hợp 2 học sinh (c và d), còn lại (k<b), sẽ so sánh chiều cao bạn đứng 
trước (a).
 Nếu k=b thì Thông báo
 còn lại nếu k>b thì Xét trường hợp 2 học sinh c và d 
 còn lại Xét trường hợp với 1 bạn học sinh a
 - Có N bạn học sinh xếp hàng theo thứ tự tăng dần theo chiều cao. (Giả sử chiều cao bạn
thứ nhất là a1, bạn thứ hai là a2,, bạn thứ N là aN; trong đó: a1<a2<  < aN).
 + Hãy chia đôi hàng học sinh đứng bằng bạn học sinh đứng ở giữa là có vị trí là (N+1)/2
(vị trí đứng giữa chỉ tương đối)
 + So sánh chiều cao bạn đứng ở giữa (a (N+1)/2) với k. 
 Nếu bằng (k= a(N+1)/2) thì thông báo.
 Nếu (k> a(N+1)/2), tìm kiếm k ứng với trường hợp hàng có (N/2)-1 bạn học sinh đứng phía
sau bạn đứng giữa (từ bạn thứ ((N+1)/2) +1 đến bạn thứ N).
 Còn lại (k< a (N+1)/2), tìm kiếm k ứng với trường hợp hàng có (N/2)-1 bạn học sinh đứng 
phía trước bạn đứng giữa (từ bạn thứ 1 đến bạn thứ ((N+1)/2) -1)
 Nếu k= a(N+1)/2 thì Thông báo 
 còn lại
 nếu k> a(N+1)/2 thì
 Xét trường hợp (N/2)-1 học sinh phía sau bạn đứng giữa (từ bạn thứ
 ((N+1)/2) +1 đến bạn thứ N) 
 còn lại
 Xét trường hợp (N/2)-1 học sinh phía trước bạn đứng giữa (từ bạn thứ 
 1 đến bạn thứ ((N+1)/2) -1)
 - Trường hợp (N/2)-1 học sinh quay lại làm tương tự như trường hợp với N học sinh. Quá
trình chia đôi hàng như vậy cho đến khi không còn học sinh nào để xét thì thông báo kết quả.
 Đưa ra trường hợp đặc biệt của dãy A là đã sắp xếp tăng dần (sử dụng thuật toán sắp xếp
mà học sinh đã biết). Như vậy bài toán tìm kiếm được phát biểu lại như sau:
 - Cho một dãy số tăng gồm các phần tử a 1, a2, ., aN (trong đó: a1<a2<  < aN). Cho biết 
trong dãy này có phần tử nào có giá trị bằng k (cho trước) hay không?
 - Xác định bài toán:
 Input: Dãy A là dãy tăng gồm N số nguyên a 1, a2, ...,aN và số nguyên k;
 Output: Chỉ số i mà a i = 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.
GV Bùi Thiện Quý 10 THPT Hưng Yên Sáng kiến kinh nghiệm
 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 
 tử thứ N) (?)
 else
 Xác định dãy (N/2)-1 phần tử phía trước (từ phần tử thứ 1 đến phần thứ
 Giua-1) (?)
 End.
 Dau Giua Cuoi
 Tinh chế lần 3:
 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;
 Giua:= (Dau + Cuoi) div 2; 
 if k= a[Giua] then Thông báo 
 else
 if k> a[Giua] then
 Dau:= Giua+1 {quay lại xác định vị trí giữa và tìm kiếm trên dãy 
 (Giua+1, N), Cuoi = 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 Cuoi
 Tinh chế lần 4:
 Program Tim_Kiem;
 Var a: array[1..N] of integer;
GV Bùi Thiện Quý 12 THPT Hưng Yên