§4 bài toán và thuật toán
(tiết 5)

Mục đích_Yêu cầu
- Giúp học sinh làm quen với bài toán tìm kiếm trong tin học.
- Hình thành và phát triển tư duy lôgic, tư duy giải thuật.
- Giúp học sinh có các kiến thức góp phần phát triển khả năng tư duy khi giải quyết các vấn đề trong khoa học cũng như trong cuộc sống.
- Kỹ năng : học sinh biết cách giải các bài toán toán tìm kiếm. Hình thành một số kĩ năng chuẩn bị tiếp thu việc học ngôn ngữ lập trình: cách dùng biến, khởi tạo giá trị các biến.

II. Công việc chuẩn bị của thầy và trò:
GV: Chuẩn bị giáo án, đồ dùng dạy học gồm 4 bảng phụ cho 2 sơ đồ khối và 2 ví dụ.
HS: Ôn tập bài cũ ở hai tiết trước đó là nội dung hai thuật toán: kiểm tra số nguyên tố và thuật toán sắp xếp; chuẩn bị bài mới: Thuật toán tìm kiếm.

Nội dung bài giảng
định lớp: 1p’
Lớp: Sĩ số: Vắng:

Bài mới: 39p’

Hoạt động của giáo viên
Hoạt động của HS
Thời gian


Đặ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.
Trong bài hôm nay chúng ta cùng tìm hiểu một số dạng bài toán tìm kiếm và xem rằng tin học sẽ xử lý các bài toán ấy như thế nào?
GV ghi bảng:
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, a2aN và một số nguyên k.
Kiểm tra trong dãy trên có chỉ số i (1<=i<=N) mà ai=k hay không? nếu có thì hãy đưa ra chỉ số đó.
GV giải thích: Số nguyên k được gọi là khoá tìm kiếm gọi tắt là khoá.
Giả sử ta có dãy sau:
6 2 7 15 11
Và k=15 thì ta phải đưa ra kết luận là tại chỉ số i=5 thì a5=k
Hoặc k=9 thì ta đưa ra kết luận là trong dãy không có số hạng nào của dãy có giá trị bằng k.
GV: Bài toán tìm kiếm được chia thành 2 dạng: tìm kiếm tuần tự và tìm kiếm nhị phân. Sau đây chúng ta đi nghiên cứu từng dạng một.
*Tìm kiếm tuần tự:
Xác định bài toán :
GV : Dựa vào bài toán dã nêu ở trên em hãy xác định Input và Output của bài toán?.









GV : Nhận xét và bổ xung (ghi bảng) :
Input: Dãy A gồm N số nguyên khác nhau a1,a2aN và số nguyên k.
Output: chỉ số i sao cho ai=k hoặc không có giá trị nào của dãy có giá trị bằng k
GV: ý tưởng của thuật toán được nêu như sau:
ý 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ì