Giáo án môn Tin học 10 - Bài 4: Bài toán và thuật toán

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. ổn đị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,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 (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 tìm kiếm nhị phân. Để xem ý tưởng đó thế nào, chúng ta sẽ cùng đi tìm hiểu. 
ý tưởng thuật toán tìm kiếm nhị phân được phát biểu như sau:
Sử dụng tính chất của một dãy số tăng. Ta tìm cách thu hẹp phạm vi tìm kiếm sau mỗi lần so sánh khoá k với phần tử tìm kiếm. Phần tử tìm kiếm thường được chọn là phần tử ở giữa.
Với Giua=[(Dau+Cuoi)/2]; Dau và Cuoi là chỉ số tương ứng của phần tử đầu và cuối dãy tìm kiếm. Ban đầu khởi tạo Dau=1, Cuoi=N.
+ Đầu tiên, ta xét phần tử ở giữa, so sánh với k. Nếu đúng bằng k thì dừng.
+ Nếu phần tử giữa lớn hơn k, ta thực hiện lại công việc tìm kiếm với các phần tử từ đầu đến phần tử gần phần tử giữa nhất (tìm ở phần đầu cuốn sách).
 + Nếu phần tử giữa nhỏ hơn k thì thực hiện lại việc tìm kiếm với các phần tử từ phần tử ngay sau phần tử giữa đến phần tử cuối (tìm ở phần sau cuốn sách). 
+ Việc tìm kiếm sẽ dừng nếu tìm thấy phần tử k đó trong dãy hoặc phạm vi tìm kiếm bằng rỗng (không còn trang sách nào để tìm nữa).
- Thuật toán được gọi là “Tìm kiếm nhị phân” bởi ta thực hiện việc tìm kiếm bằng cách chia dãy tìm kiếm thành 2 dãy con (nhị phân), sau đó lại tìm kiếm trên một trong hai dãy con đó nếu vẫn chưa tìm thấy.
- Từ ý tưởng ở trên, ta có cách biểu diễn thuật toán ở dạng liệt kê như sau: 
(nêu lên các bước).
- Trả lời 
- Trả lời: Cách đó không thể làm với quyển vở bình thường vì vở không đánh số trang.
- Ghi bài:
Sử dụng tính chất dãy A tăng.
So sánh aGiua với k. Với Giua ò [(Dau + Cuoi)/2]. Dau ò 1, Cuoi ò N.
+ Nếu aGiua = k thì Giua là chỉ số cần tìm, kết thúc tìm kiếm.
+ Nếu aGiua > k thì tìm kiếm tiếp trên dãy a1, a2,, aGiua-1
+ Nếu aGiua < k thì tìm kiếm tiếp trên dãy aGiua +1 , aGiua+2, , aN
+ Quá trình kết thúc khi tìm thấy chỉ số i sao cho ai = k hoặc phạm vi tìm kiếm bằng rỗng.
Quan sát và ghi bài.
Bước 1: Nhập N, các phần tử a1, a2,, aN và khoá k;
Bước 2: Dauò1, CuoiòN;
Bước 3:
Giuaò[(Dau+Cuoi)/2];
Bước 4: Nếu aGiua=k thì thông báo chỉ số Giua rồi kết thúc;
Bước 5: Nếu aGiua>k thì 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ó phàn tử nào có giá trị bằng k, rồi kết thúc;
Bước 8: Quay lại bước 3;
- VD 1: N=7, k=5. Dãy số: 2, 4, 5, 21, 43, 47, 52.
+ Chọn Dau là phần tử đầu tiên: Dau ò 1, và Cuoi là phần tử cuối cùng: Cuoi ò N (tức Cuoi = 7).
 + Xét phần tử ở giữa: Giua ò [(Dau+Cuoi)/2], tức Giua = 4; Thấy aGiua=21 > k = 5. Thực hiện tìm kiếm trong nửa đầu của dãy: CuoiòGiua-1; tức Cuoi=3;
+ Lại xét phần tử giữa: Giuaò[(Dau+Cuoi)/2]; tức Giua = 2; aGiua=4 < k = 5; Thực hiện tìm kiếm trong nửa sau của dãy: DauòGiua + 1; tức Dau=3.
+ Xét tiếp phần tử ở giữa: Giuaò[(Dau+Cuoi)/2]; tức Giua = 3; aGiua=5 = k ; Thông báo ra chỉ số cần tìm i=Giua=3 rồi kết thúc tìm kiếm.
- Đưa ra sơ đồ khối của thuật toán và giải thích. Đồng thời giải thích sự tương đương giữa sơ đồ khối và các bước liệt kê.
- Nhận xét: trong thuật toán, việc tìm kiếm thực chất là lặp một số lần thao tác:
+ Chọn phần tử ở giữa làm phần tử tìm kiếm.
+ So sánh phần tử tìm kiếm với k.
+ Căn cứ vào kết quả so sánh để thu hẹp phạm vi tìm kiếm hoặc kết luận đã tì thấy (không tìm thấy)
Đ
Nhập N, a1, a2,, aN và k
Dauò1; CuoiòN
aGiua = k
Giua ò [(Dau+Cuoi)/2]
Đưa ra Giua rồi kết thúc
aGiua > k
Cuoiò Giua-1
DauòGiua+1
Dau>Cuoi
Thông báo trong dãy không có số hạng nào có giá trị bằng k rồi kết thúc
Đ
Đ
S
S
S
i
1
2
3
4
5
6
7
A
2
4
5
21
43
47
52
Dau
1
1
3
Cuoi
7
3
3
Giua
4
2
3
aGiua
21
4
5
aGiua và k
>
<
=
Lần duyệt
1
2
3
Thông báo chỉ số cần tìm i=Giua=3.
- Quan sát sơ đồ của giáo viên.
- Hướng dẫn HS tìm hiểu các VD.
- VD 2: N=8, k=23. Dãy số: 3, 5, 9, 12, 16, 17, 19, 24.
Bảng mô phỏng như sau (kết hợp với sơ đồ hoặc các bước liệt kê).
i
1
2
3
4
5
6
7
8
A
3
5
9
12
16
17
19
24
Dau
1
5
7
8
8
Cuoi
8
8
8
8
7
Giua
4
6
7
8
aGiua
12
17
19
24
aGiua và k
<
<
<
>
Lần duyệt
1
2
3
4
Nhận thấy rằng: Dau>Cuoi nên phạm vi tìm kiếm bằng rỗng, thông báo: không tìm thấy phần tử nào bằng 23 trong dãy.
+ VD 3: N=5, k=36. Dãy số: 9, 10, 29, 36, 42.
HS tự làm.
GV nhận xét bài của HS.
- Nghe giảng và ghi bài.
- Làm VD.
Củng cố (1 phút)
- So với thuật toán tìm kiếm tuần tự, ở thuật toán tìm kiém nhị phân cần lưu ý:
+ Dãy số ban đầu là dãy tăng.
+ Số lần duyệt ít hơn.
- BTVN: 
Học các cách biểu diễn bài toán tìm kiếm bằng liệt kê và bằng sơ đồ khối.
Mỗi học sinh lấy 2 ví dụ về dãy tăng dần và khoá k, sau đó mô phỏng thuật toán tìm kiếm nhị phân bằng bảng.
V. nhận xét của giáo viên hướng dẫn:
.................................................................................................................................
..................................................................................................................................................................................................................................................................
................................................................................................................................