14 - BAI TOAN VA THUAT TOAN (Tiet 5)

Ngày soạn : Tiết :
Ngày dạy : Lớp :
§4. BÀI TOÁN VÀ THUẬT TOÁN
(Tiết 5)
MỤC TIÊU
1. Kiến thức:
- Biết cách xây dựng thuật toán tìm kiếm tuần tự và tìm kiếm nhị phân cho bài toán tìm kiếm. Góp phần hiểu đúng khái niệm bài toán trong tin học, đồng thời qua một số ví dụ của tiết trước và tiết này nhận dạng được các cách trình bày thuật toán bằng liệt kê và bằng sơ đồ khối.
2. Kỹ năng:
- Hiểu và trình bày được 2 thuật toán tìm kiếm (tuần tự và nhị phân) theo 2 cách liệt kê và sơ đồ khối, vận dụng linh hoạt trong lớp những bài toán dạng này.
PHƯƠNG PHÁP, PHƯƠNG TIỆN DẠY HỌC
1. Chuẩn bị của giáo viên
- Đồ dùng: Giáo án, SGK, SGV, tài liệu tham khảo máy chiếu (nếu có)
- Phương pháp: Thuyết trình, vấn đáp.
2. Chuẩn bị của học sinh
- Đồ dùng học tập: SGK, vở ghi, bút,....
III. NỘI DUNG BÀI GIẢNG
1. Ổn định tổ chức lớp
- Ổn định lớp.
- Chỉnh đốn trang phục.
- Sĩ số:.........Vắng:......
2. Kiểm tra bài cũ
Câu 1: Hãy mô tả thuật toán sắp xếp bằng tráo đổi (Exchange Sort) theo phương pháp liệt kê?
Câu 2: Hãy mô tả thuật toán sắp xếp bằng tráo đổi (Exchange Sort) theo phương pháp sơ đồ khối?
3. Đặt vấn đề
4. Nội dung bài mới
Hoạt động của GV
Hoạt động của HS
Tg

Ví dụ 3: Bài toán tìm kiếm.
Hoạt đông 1: Giới thiệu cho học sinh về bài toán tìm kiếm.
Tìm kiếm là một việc thường xảy ra trong cuộc sống, chẳng hạn cần tìm cuốn sách giáo khoa Tin học 10 trên giá sách, cần tìm một học sinh trong danh sách một lớp học,… Nói một cách tổng quát là cần tìm một đối tượng cụ thể nào trong tập đối tượng cho trước.
Dưới đây ta chỉ xét bài toán tìm kiếm dạng đơn giản sau:



Ví dụ:
Với dãy A gồm các số:
5 7 1 4 2 9 8 11 25 51
- Với k = 8 trong dãy trên có số hang a7 có giá trị bằng k. Vậy chỉ số cần tìm là i = 5.
- Với k = 6 thì không có số hạng nào của dãy A có giá trị bằng k.
GV: Để tìm kiếm một số xem nó có mặt trong dãy hay không ta sử dụng thuật toán tìm kiếm tuần tự và thuật toán tìm kiếm nhị phân.
3. Một số ví dụ
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: a1, a2,..., aN và một số nguyên k (sẽ gọi là khoá tìm kiếm).Cho biết có hay không chỉ số i (1


Hoạt động 2: Hướng dẫn học sinh tìm ý tưởng của thuật toán tìm kiếm tuần tự.
- Yêu cầu học sinh xác định bài toán:









VD: Cho dãy số và số k = 7. Kiểm tra xem trong dãy có giá trị nào bằng k hay không, nếu có ở vị trí thứ mấy trong dãy?
N
a1
a2
a3
a4
a5

5
4
3
7
5
8

k

7




GV: So sánh lần lượt ai và k, nếu bằng thì i chính là vị trí cần tìm; nếu i > 5 màvẫn không có giá trị nào trong dãy bằng k thì kết luận không tìm thấy i thoả mãn
* Xác định bài toán.
Input: Dãy A 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 A có giá trị bằng k

* Ý tưởng:
- Tìm kiếm tuần tự được thực hiện 1 cách tự nhiên. Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoặc gặp một số hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá.


Hoạt động 3: Biểu diễn thuật toán tìm kiếm tuần tự bằng phương pháp liệt kê từng bước.
- GV giải thích cho học sinh từng bước của thuật toán.



Cách 1: Liệt kê các bước
B1: Nhập N, các số hạng a1, a2,..., aN và khoá