Sáng kiến kinh nghiệm


LÝ DO CHỌN ĐỀ TÀI 2
MỤC ĐÍCH NGHIÊN CỨU 2
ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU 3
PHƯƠNG PHÁP NGHIÊN CỨU 3
THỜI GIAN NGHIÊN CỨU 3

CHƯƠNG 1: CƠ SỞ LỰA CHỌN ĐỀ TÀI 4
1.1 CƠ SỞ LÝ LUẬN 4
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 8
2.1 PHƯƠNG PHÁP TINH CHẾ TỪNG BƯỚC 8
2.2 BÀI TOÁN TÌM KIẾM 9
2.4 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 10


GV Bùi Thiện Quý THPT Hưng Yên
Sáng kiến kinh nghiệm

GV Bùi Thiện Quý THPT Hưng Yên
1
Sáng kiến kinh nghiệm
 !
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

học của học sinh. Đặc biệt là tạo học sinh có được cách tư duy khi học thuật
toán và lập trình.
%&'()(#$
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.
&*+#$
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
,#$
Từ tháng 1 năm 2013 đến tháng 2 năm 2013
GV Bùi Thiện Quý THPT Hưng Yên
3
Sáng kiến kinh nghiệm

-). +/012 
34&*+56&37
&**89 !
*8
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

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
GV Bùi Thiện Quý THPT Hưng Yên
5
Sáng kiến kinh nghiệm
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

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.
O=P?CH
Chưa hiểu về mục tiêu môn học, cũng cho rằng học Tin học là học sử dụng
máy tính, nên không quan tâm đến các nội dung học. Có học sinh còn hiểu môn
học như là một môn học phụ không có tác dụng nhiều trong chương trình giáo
dục phổ thông. Bên cạnh đó học sinh còn yếu về tư duy lôgic, khả năng sáng tạo
và suy luận trong việc học lập trình. Học sinh khi học thuật toán không hình
dung được con đường ra thuật toán bởi nó là tổng quát hóa một cách thức hoạt
động, từ việc đó người ta đưa cho máy tính thực hiện và làm.
GV Bùi Thiện Quý THPT Hưng Yên
7
Sáng kiến kinh nghiệm
&*:). +/012
 34&*+56&3
:&*+56&3
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

Xác định bài toán:
Input: Dãy A gồm N số nguyên khác nhau a
1
, a
2
, ,a
N
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.
:+/01
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 (a
1
<a
2
<…<a
N
). Khi đó ý tưởng thuật toán như sau:
Vì dãy A là dãy tăng, nên ta thu hẹp phạm vi tìm kiếm sau mỗi lần so
sánh khóa k với phần tử đã chọn. Ở đây, ta chọn số hạng ở giữa dãy (gọi là a
Giua
)
để so sánh với khóa k. Nếu bằng thì ta đưa ra kết quả là chỉ số tìm kiếm là Giua,
còn không thì tìm ở dãy các phần tử đứng sau a
Giua
nếu phần tử a
Giua

+
2
CuoiDau
;
Bước 4: Nếu a
Giua
= k thì thông báo chỉ số Giua, rồi kết thúc;
GV Bùi Thiện Quý THPT Hưng Yên
9
a
Giua
a
N
a
1
Sáng kiến kinh nghiệm
Bước 5: Nếu a
Giua
> k thì đặt Cuoi = Giua –1 rồi chuyển đến bước 7;
Bước 6: Dau

Giua +1;
Bước 7: Nếu Dau > Cuoi thì thông báo dãy A không có số hạng nào có giá
trị bằng k, rồi kết thúc;
Bước 8: Quay lại bước 3;
:). +/012
 34&*+56&3
Mục đích:
- Học sinh hiểu về bài toán tìm kiếm.
- Học sinh biết được thuật toán tìm kiếm nhị phân.

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
, a
2
, …., a
N
. 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.
àĐó là ý tưởng của thuật toán tìm kiếm tuần tự mà học sinh đã biết.
Cách này cũng như việc ta muốn tìm kiếm một bạn học sinh có chiều cao
k nào đó trong một lớp học mà các bạn học sinh đang ngồi học, khi đó ta phải
gọi từng bạn trong lớp ra đo (từ bạn ngồi ở đầu tiên bàn đầu đến bạn ở vị trí cuối
cùng lớp học) để xác định vị trí học sinh có chiều cao k cần tìm.
Hướng học sinh đi đến ý tưởng tìm kiếm nhị phân
- Trong một giờ chào cờ lớp học đó ra xếp hàng chào cờ, và việc xếp hàng
này có thứ tự từ thấp lên cao (bạn thấp đứng trước và bạn cao đứng sau, giả sử
GV Bùi Thiện Quý THPT Hưng Yên
11

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à a
1
, bạn thứ hai là a
2
,…, bạn thứ N là a
N
; trong đó:
a
1
<a
2
< … < a
N
).
+ 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

1
<a
2
< … <
a
N
). 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
, a
2
, ,a
N
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.
Chúng ta dựa theo ý tưởng của bài toán thực tế để bắt đầu xây dựng thuật
toán tìm kiếm nhị phân theo phương pháp tinh chế từng bước như sau. Trong
quá trình tinh chế những dòng được đặt dấu (?) thể hiện điều cần phải làm rõ sau
mỗi lần tinh chế.
Tinh chế lần 1:
Chương trình Tim_Kiem;
Khai báo và nhập dãy A gồm các số nguyên tăng dần và số nguyên k.
Xác định dãy ban đầu để tìm kiếm (?)
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

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.
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
GV Bùi Thiện Quý THPT Hưng Yên
15
Dau Giua Cuoi
Sáng kiến kinh nghiệm
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.
Tinh chế lần 4:

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;
While <điều kiện (?)> do
Begin
Giua:= (Dau + Cuoi) div 2;
if k= a[Giua] then Thông báo
else
if k> a[Giua] then
Dau:= Giua+1
else
Cuoi:= Giua-1;
End;
GV Bùi Thiện Quý THPT Hưng Yên
17
Sáng kiến kinh nghiệm
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;
Tim_thay:=False;
While Dau<=Cuoi do
Begin
Giua:= (Dau + Cuoi) div 2;
if k= a[Giua] then Tim_thay:=True
else
if k> a[Giua] then
Dau:= Giua+1
else
Cuoi:= Giua-1;
End;
Thông báo kết quả (?)
End.
Tinh chế lần 8:
Program Tim_Kiem;
Var a: array[1 N] of integer;
i, k, Dau, Cuoi, Giua: integer;
Tim_thay: boolean;
Begin
GV Bùi Thiện Quý THPT Hưng Yên
19
Sáng kiến kinh nghiệm
Write(‘Nhap N =’); readln(N);
for i:=1 to N do
Begin
Write(‘a[’ ,i, ‘] =’); readln(a[i]);
End;

các đối tượng cần được sắp xếp theo một thứ tự nhất định.
GV Bùi Thiện Quý THPT Hưng Yên
22
Sáng kiến kinh nghiệm
&*U)&'
U+2/98%(U
VWXYQCNZH?[\]HTEPDJ
Để đảm bảo học sinh hiểu và xây dựng được thuật toán tìm kiếm nhị phân áp
dụng cho một số bài toán đơn giản. Chúng ta cần cung cấp cho học sinh hiểu rõ
ý tưởng thuật toán này và cách để xây dựng được chương trình. Muốn làm được
điều này ta sẽ cho học sinh thực hiện việc tìm kiếm trên một số ví dụ thực tế gần
gũi với học sinh, làm cho học sinh hình dung rõ nét dần ý tưởng thuật toán.
Đồng thời liên hệ và sử dụng ngôn ngữ lập trình để diễn giải thuật toán để đi đến
chương trình cụ thể. Trên cơ sở đó phát triển tư duy nhận thức của học sinh, làm
cho học sinh có một cách nhìn thấu đáo về thuật toán.
Từ việc dạy học như vậy ta sẽ khảo sát mức độ tiếp thu thuật toán đó như thế
nào của học sinh để tìm hiểu và đánh giá được chất lượng dạy học thuật toán
này. Việc khảo sát đó thông qua trả lời các câu hỏi theo ở các cấp độ tư duy
khác nhau.
Việc xây dựng hệ thống các câu hỏi khảo sát được thực hiện như sau:
Ở mức độ biết: Chúng ta đưa những câu hỏi mang tính tương tự hoặc xem
xét lại các điều kiện hoặc kiểm tra việc gán giá trị các biến, Chúng ta có thể
đưa một số câu hỏi như sau:
Dãy số đưa vào có phải là dãy đã sắp xếp hay chưa?
Việc nhập dữ liệu đầu vào thực hiện ở câu lệnh nào?
Các biến Dau, Cuoi ban đầu gán các giá trị là bao nhiêu?
Việc so sánh trong thuật toán luôn thực hiện ở việc so sánh khóa k với các
phần tử đứng giữa phải không?
Nếu khóa k lớn hơn phần tử đứng giữa thì sẽ tìm kiếm ở dãy nào?
Mục đích chúng ta đưa học sinh trả lời các câu hỏi đó là để xác định xem

1 = Không đồng ý (tương ứng 1 điểm)
2 = Phân vân (tương ứng 2 điểm)
3 = Đồng ý (tương ứng 3 điểm)
4 = Hoàn toàn đồng ý (tương ứng 4 điểm)
GV Bùi Thiện Quý THPT Hưng Yên
24