Ngày soạn: 01/10/2008
Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 5)
A. MỤC TIÊU
1. Kiến thức:
Hiểu được thuật toán tìm kiếm nhị phân.
2. Kỹ năng:
Vận dụng thuật toán để giải quyết các bài toán khác.
3. Thái độ:
Rèn luyện cho HS tư duy logic, làm việc có khoa học.
B. PHƯƠNG PHÁP:
Nêu và giải quyết vấn đề + thuyết trình.
C. CHUẨN BỊ CỦA GIÁO VIÊN VÀ HỌC SINH:
1. Chuẩn bị của GV: SGK
2. Chuẩn bị của HS: SGK
D. TIẾN TRÌNH LÊN LỚP:
1. Ổn định lớp: Ồn định lớp kiểm tra sĩ số.
2. Kiểm tra bài cũ:
Viết thuật toán dưới dạng sơ đồ khối của bài toán sắp xếp dãy số nguyên theo thứ tự tăng dần.

Kết quả:





















3. Bài mới:
a, Đặt vấn đề:
Trong cuộc sống hàng ngày các em hay gặp sự tìm kiếm nào đó, ví dụ tìm kiếm một bạn học sinh trong lớp, hoặc tìm kiếm một số hạng có trong dãy hay không. Hôm nay chúng ta tìm hiểu thuật toán tìm kiếm nhị phân.
b, Triển khai bài:
HOẠT ĐỘNG CỦA THẦY VÀ TRÒ
NỘI DUNG KIẾN THỨC


Hoạt động 1: Tìm hiểu thuật toán tìm kiếm nhị phân.




HS: Nghiên cứu SGK.
GV: Gọi HS xác định bài toán
HS: Xác định bài toán


GV: Cho ví dụ cụ thể để giải thích cho
Ví dụ: ta có dãy gồm 4 số nguyên như sau:
a1 a2 a3 a4
9 12 17 21
Với k= 12 thì kết quả chúng ta có được kết quả chúng ta sẽ được chỉ số nào?
HS: trả lời câu hỏi.
GV: Gọi HS nêu ý tưởng
HS: Nêu ý tưởng.
GV: Với A là một dãy ta tìm cách thu hẹp khoảng cách nhanh phạm vi tìm kiếm sau mỗi lần so sánh với số hạng k được chọn.
Ta dùng một biến chỉ số giưa để làm vị trí đầu cho quá trình tìm kiếm.


Nếu agiua =k thì giua là chỉ số cần tìm.
Ngược lại tực lúc này agiua <> k thì nếu k có trong dãy thì k nằm ½ bên phải hoặc ½ bên trái của giua nằm trong dãy A
Ta lại tiếp tục thay đổi giá trị của giua tuỳ thuộc phép so sánh giữa agiua với k.
Để chọn giá trị giua tiếp theo ta cần có hai biến chỉ số dau và cuoi.





GV: Gọi 1 HS viết thuật toán bằng cách liệt kê.
HS: Viết thuật toán.
GV: Nhận xét và giải thích thêm.






GV: Gọi 1 HS lên bảng vẽ sơ đồ khối biểu diễn thuật toán.
HS: Vẽ sơ đồ khối.
GV: Nhận xét.











GV: Mô phỏng thuật toán với dãy số và khoá k cụ thể.

Ví dụ: N=6 và k= 13

a1 a2 a3 a4 a5 a6
3 5 9 11 13 18
*Thuật toán tìm kiếm nhị phân
Bài toán: Cho dãy A gồm N số nguyên khác nhau a1,a2..an đã được sắp xếp tăng dần và số nguyên k. Cần biết có hay không chỉ số I mà ai =k. Nếu có hãy cho biết chỉ số đó.
- Xác định bài toán:
+ Input: Số nguyên n, Dãy số nguyên đã sắp xếp tăng dần, số nguyên k.
+ Output: Thông báo chỉ số I nếu ai=k hoặc không có phần tử nào trong dãy:

- Thuật toán:
+ Cách liệt kê:
B1: Nhập n, k và các số hạng a1,a2..an theo thứ tự tăng dần.
B2: dau←1; cuoi←n;
B3:

B4: Nếu agiua=k thì thông báo chỉ số giua rồi kết thúc.
B5: Nếu agiua>k thì
Cuoi ← giua -1; Chuyển sang B7
B6: dau ← giua+1.
B7:Nếu dau>cuoi thì thông báo trong dãy không có số hạng bằng k.
B8:Quay lại B3



+ Sơ đồ khối:










4. Củng cố:
- Thuật toán tìm kiếm nhị phân.
5. Dặn dò, hướng dẫn học sinh học tập ở nhà:
- Về nhà đọc và làm trước các bài tập trong sách bài tập
- Chuẩn bị mang sách bài tập.