Bài 4: bài toán và thuật toán
(tiết 6)
Người soạn: Nguyễn Thị Huê
SV lớp: SP Tin K40
Ngày soạn: 25/9/2008
Giáo viên hướng dẫn: Nguyễn Văn Trường
I. Mục đích – Yêu cầu
- Hiểu và thực hiện được thuật toán tìm kiếm nhị phân.
- Biết cách xây dựng thuật toán đó.
- Hình thành kĩ năng tư duy logic để giải quyết các bài toán và vấn đề trong thực tế.
II. Công tác chuẩn bị.
Giáo viên chuẩn bị bảng phụ mô tả sơ đồ khối thuật toán tìm kiếm nhị phân.
III. Nội dung
1. định tổ chức lớp (1 phút)
Sĩ số: Vắng: Có phép: Không phép:
2. Kiểm tra bài cũ. (6 phút)
* Câu hỏi: Cho dãy số nguyên sau và khoá k= 27, em hãy thực hiện thuật toán tìm kiếm tuần tự và đưa ra kết quả dưới dạng mảng mô phỏng?
Dãy số: 7, 5, 23, 27, 17, 32, 1
* Đáp án:
Bảng mô phỏng:
A
7
5
23
27
17
32
1

i
1
2
3
4
5
-
-

Ai = k ?
Sai
Sai
Sai
Sai
Đúng
-
-


Kết quả thực hiện thuật toán: Thông báo chỉ số cần tìm: i = 5.
3. Bài mới
Hoạt động của GV
Hoạt động của HS
Thời gian

Đặt vấn đề: Bài toán tìm kiếm rất phổ biến trong thực tế. Ví dụ: tìm thuê bao trong danh bạ điện thoại, tìm học sinh trong danh sách, … Ta cũng có thể tìm kiếm theo nhiều cách khác nhau. ở tiết trước các em đã được tìm hiểu về thuật toán tìm kiếm tuần tự, tiếp theo chúng ta cùng tìm hiểu một thuật toán tìm kiếm nữa: tìm kiếm nhị phân.



- Các em hãy mở SGK trang 42.
Bài toán được phát biểu như sau:
Bài toán : “Dãy A gồm N số nguyên khác nhau: a1,a2aN đượ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 (1<=i<=N) mà ai=k. Nếu có hãy cho biết chỉ số đó”.
Em hãy xác định Input và Output của bài toán?

Bài 4: Bài toán và thuật toán.
(tiết 6)
3. Một số ví dụ về thuật toán.
Ví dụ 3 (tiếp): Thuật tón tìm kiếm nhị phân.


- Xác định:
+ Input: Dãy tăng gồm N số nguyên khác nhau a1, a2,…, aN và số nguyên k;
+ Output: Chỉ số i mà ai=k hoặc thông báo không có số hạng nào của dãy có giá trị bằng k;


- Em nào có thể mô tả ngắn gọn cách mở trang sách của mình?
Ngoài cách như trên, ta cũng có thể làm như sau: Em mở một trang bất kì trong sách. Nếu trang đó đúng là trang 42 thì thôi. Nếu số trang đó nhỏ hơn 42 thì lại mở từ trang trước đó trở về đầu sách, ngược lại thì mở từ trang sau đó trở về cuối sách.
- Với cách làm đó của em thì có thực hiện được trên cuốn vở viết bình thường không?
- Việc tìm trang 42 cũng gần giống với ý tưởng của thuật toán