Đ 4: BI TON V THUT TON
(Tiếtt 5)
I. -Mục đích - yêu cầu:
Kiến thức : -Hiểu và thực hiện đợc thuật toán trong SGK bài toán tìm kiếm tuần
tự
Kỹ năng: - áp dụng thuật toán tìm kiếm tuần tự để giải một số bài toán đơn
giản.
Tháí độ : - Yêu thích môn học, ham học hỏi.
II. Phơng pháp dạy học: - phơng pháp tích cực, gợi mở, đối thoại.
III. Phơng tiện dạy học: - Giáo án, SGK, SGV, phấn, thớc, máy tính, máy chiếu
IV. Nội dung các bớc lên lớp:
1) ổn định tổ chức lớp: (1)
2) kiểm tra bài cũ: (10) GV đặt câu hỏi và gọi HS lên bảng trả lời
Câu hỏi: Em hãy nêu ý tởng của thuật toán sắp xếp tráo đổi?
áp dung thuật toán để sắp xếp dãy số sau theo chiều tăng dần:
3 5 9 8 1 7 ( Chiếu Slide 1 - câu hỏi kiểm tra bài cũ ).
HS: Trả lời câu hỏi. HS dới lớp theo dõi bạn trả lời và nhận xét.
GV: chiếu Slide 2 + 3 - Đáp án và nhận xét cho điểm.
3) Dạy bài mới: (30)
* Đặt vấn đề: Trong thực tế nhiều khi ta hay phải tìm kiếm một thứ gì đó nh tra từ
điển, tìm sách ở trên giá sách, tìm tên HS trong sổ điểm. Bài hôm nay chúng ta cùng
tim hiểu một số dạng bài toán tìm kiếm và xem trong tin học sẽ xử lý các bài toán đó
nh thế nào?
Hoạt động 1: Tìm hiểu về bài toán tìm kiếm (10)
Hoạt động của giáo viên Hoạt động của học sinh
GV (Chiếu slide số 5): Ví dụ 3. Bài toán tìm
kiếm
Bài toán:
Cho dãy A gồm N số nguyên khác nhau a
1
,

định Input và Output của bài toán?.

GV : Nhận xét và bổ xung (chiếu Slide số 7) :
GV ( Chiếu Slide số 8). Từ ví dụ yêu cầu HS nêu
ý tởng về việc giải bài toán trên.
GV: Phân tích và nhận xét (Chiếu Slide số 9)
GV: dựa vào ý tởng ta có thể xây dựng thuật toán
theo cách liệt kê, trớc tiên ta phải nhập Input của
bài toán vậy một em cho cô biết bớc 1 ta phải làm
HS: trả lời
+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 sao cho a
i
=k
hoặc không có giá trị nào của dãy
có giá trị bằng k
HS: quan sát và ghi bài
HS: Trả lời câu hỏi
ý t ởng :
so sánh lần lợt từng phần tử của
dãy với khoá k
+ Nếu gặp phần tử nào bằng k thì

GV: Lấy kết quả và nhận xét. ( Chiếu Slide 12 ).
HS: Trả lời ta nhập vào dãy A gồm
N số nguyên khác nhau và số
nguyên k.
HS: Nghe giảng, ghi vở
Thuật toán:
Cách liệt kê:
B1: nhập N, các số hạng a
1
, a
2
,
,a
N
và khoá k;
B2: i

1;
B3: nếu a
i
=k thì thông báo chỉ số
i, rồi kết thúc;
B4: i

i+1;
B5: nếu i>N 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.
B6: quay lại B3.
HS: Nghe giảng