Sáng kiến kinh nghiệm

MỤC LỤC
PHẦN I: MỞ ĐẦU.............................................................................1
LÝ DO CHỌN ĐỀ TÀI .................................................................................. 1
MỤC ĐÍCH NGHIÊN CỨU .......................................................................... 2
ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU ................................................ 2
PHƯƠNG PHÁP NGHIÊN CỨU .................................................................. 2
THỜI GIAN NGHIÊN CỨU .......................................................................... 2

PHẦN II: NỘI DUNG .......................................................................3
CHƯƠNG 1: CƠ SỞ LỰA CHỌN ĐỀ TÀI ................................................... 3
1.1 CƠ SỞ LÝ LUẬN .................................................................................... 3
1.2 CƠ SỞ THỰC TIỄN ................................................................................ 5
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 ........ 7
2.1 PHƯƠNG PHÁP TINH CHẾ TỪNG BƯỚC ........................................... 7
2.2 BÀI TOÁN TÌM KIẾM ............................................................................ 8
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 ............................ 9
CHƯƠNG 3: KẾT QUẢ ĐẠT ĐƯỢC ......................................................... 22
3.1 QUÁ TRÌNH THỰC HIỆN THU THẬP SỐ LIỆU VÀ KẾT QUẢ........ 22
3.2 HẠN CHẾ .............................................................................................. 30
3.3 BÀI HỌC KINH NGHIỆM .................................................................... 30
3.4 ĐIỀU KIỆN ÁP DỤNG.......................................................................... 31
3.5 HƯỚNG PHÁT TRIỂN ĐỀ TÀI ............................................................ 31
3.6 KIẾN NGHỊ ........................................................................................... 31

PHẦN III: KẾT LUẬN ..................................................................33
TÀI LIỆU THAM KHẢO ...............................................................34


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

GV Bùi Thiện Quý

1

THPT Hưng Yên


Sáng kiến kinh nghiệm

nhưng tôi muốn đưa ra đây để thấy được hiệu quả của phương pháp và đồng thời
bồi dưỡng và phát hiện những học sinh có năng khiếu tin học.
MỤC ĐÍCH NGHIÊN CỨU
Nâng cao chất lượng dạy và học môn Tin học trong trường phổ thông, đặc
biệt là dạy học lập trình ở Tin học lớp 11.
Góp phần đổi mới phương pháp dạy học trong trường phổ thông nói chung
và môn Tin học nói riêng.
Góp phần khơi dậy lòng đam mê, yêu thích và hứng thú khi học môn Tin
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.
ĐỐ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

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
GV Bùi Thiện Quý

3

THPT Hưng Yên


Sáng kiến kinh nghiệm

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

đế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 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

GV Bùi Thiện Quý


GV Bùi Thiện Quý

6

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

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à aGiua)
để 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 aGiua nếu phần tử aGiuak . Quá trình tiếp tục
lặp đi lặp lại như trên với dãy các phần tử đứng trước hoặc sau cho đến khi tìm
thấy khóa k trong dãy A hoặc phạm vi tìm kiếm (hay dãy phần tử) bằng rỗng
(không còn phần tử nào) thì kết thúc.
a1

aGiua

aN

Thuật toán tìm kiếm nhị phân viết bằng cách liệt kê:
Bước 1: Nhập N, các số hạng a1, a2, ...,aN và khóa k;
Bước 2: Dau1; Cuoi N;

 Dau  Cuoi 
Bước 3: Giua  
 ;
2

GV Bùi Thiện Quý

8

THPT Hưng Yên


Sáng kiến kinh nghiệm


9

THPT Hưng Yên


Sáng kiến kinh nghiệm

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ử 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?
- 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.

Nếu k = a thì “Thông báo” còn lại Xét trường hợp với 1 bạn học sinh b
- Có 3 bạn học sinh xếp hàng theo thứ tự tăng dần (chiều cao tương ứng là:
a
như sau:
- Cho một dãy số tăng gồm các phần tử a 1, a2, …., aN (trong đó: a1
đế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;

GV Bùi Thiện Quý

14

THPT Hưng Yên


Sáng kiến kinh nghiệm

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;

Write(‘a[’ ,i, ‘] =’); readln(a[i]);
GV Bùi Thiện Quý

15

THPT Hưng Yên


Sáng kiến kinh nghiệm

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
else
if k> a[Giua] then
Dau:= Giua+1
else
Cuoi:= Giua-1;
End;
End.
Tinh chế lần 5:
Program Tim_Kiem;
Var

a: array[1..N] of integer;
i, k, Dau, Cuoi, Giua: integer;

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
Cuoi:= Giua-1;
GV Bùi Thiện Quý

18

THPT Hưng Yên


Sáng kiến kinh nghiệm

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
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
2

3

4

5

6

7

8

9

10

2

4

5

6

9

21


Tim_thay

10

www.themegallery.com

Mô phỏng
 Tìm k trong dãy sau:
6

7

8

9

10

21

22

30

31

33

aGiua


THPT Hưng Yên


Sáng kiến kinh nghiệm

Mô phỏng
 Tiếp tục tìm k trong dãy sau:
6

7

21

22
aGiua

Dau

6

So sánh
Giua

Cuoi

7

21

k

3.1 QUÁ TRÌNH THỰC HIỆN THU THẬP SỐ LIỆU VÀ KẾT QUẢ
Xây dựng phiếu khảo sát
Để đả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
học sinh có biết về thuật toán, biết về các lệnh các cấu trúc lệnh đã dùng trong
chương trình cài đặt.
GV Bùi Thiện Quý

22

Có bốn mức đánh giá về việc trả lời câu hỏi:
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)
GV Bùi Thiện Quý

23

THPT Hưng Yên


Sáng kiến kinh nghiệm

4 = Hoàn toàn đồng ý (tương ứng 4 điểm)
Có 21 một câu học sinh phải trả lời.
Tổng điểm tối đa là 4x21 = 84 điểm.
Mỗi câu hỏi được gán 1 mã tương ứng với mức độ nhận thức của học sinh.
Đó là: B1: câu hỏi thứ nhất trong mức độ biết, H2: câu hỏi thứ 2 trong mức độ
hiểu, ....(học sinh không cần quan tâm đến mã này).
Xây dựng phiếu hỏi gồm các cột dòng để học sinh dễ đọc, nội dung trong
các câu hỏi đảm bảo từ ngữ chính xác, logic về mặt ý nghĩa.
Mẫu hỏi được xây dựng như sau:

GV Bùi Thiện Quý

24

THPT Hưng Yên