Kí kiểm tra Ngày soạn: 5/10/2008
Ngày dạy : 10/10/2008
Tiết theo PPCT: 14

§4.Bài toán và thuật toán
I. MỤC TIÊU
1. Kiến thức:
- Hiểu được khái niệm thuật toán là cách giải bài toán mà về nguyên tắc có thể giao cho máy tính thực hiện.
- Biết biểu diễn thuật toán bằng cách liệt kê, sơ đồ khối.
- Hiểu và thực hiện được thuật toán tìm kiếm nhị phân.
2. Kỹ năng:
- Chỉ ra được Input và Output của một số bài toán đưa ra.
- Xây dựng được thuật toán cho một số bài toán đơn giản trong SGK.
3. Thái độ:
- Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó.
II.Đồ dùng dạy-học
-Sách giáo khoa, sách giáo viên.
III. HOẠT ĐỘNG DẠY- HỌC
1. Ổn định tổ chức(1’):
Kiểm tra sỹ số.
2. tra bài cũ(4’):
- Câu hỏi: Trình bày ý tưởng và viết thuật toán tìm kiếm tuần tự?
3.Nội dung mới(38’):

Nội dung
Tg
Hoạt động của GV và HS

3. Một ví dụ:
* Thuật toán tìm kiếm nhị phân

- Xác định bài toán
+ Input: Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2, …, aN và một 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: SGK



- Thuật toán:
* Cách liệt kê:
SGK trang 42, 43





* Sơ đồ khối:
SGK trang 43





7’










4’





12’






15’


- Đặt vấn đề: giả sử muốn tìm tới trang 40 của SGK Tin 10 các em tìm như thế nào?
- HS: Ước chừng trang 40 nằm ở đoạn đầu, mở ra, nếu trang sách vừa mở >40 thì tiếp tục giở về trước, không thì tiếp tục tìm về phía sau
hoặc GV minh hoạ qua việc tra từ điển
-GV nhấn mạnh dãy A là một dãy tăng.
+Hỏi:So sánh 2 bài toán tìm kiếm trong 2 thuật toán?
+HS trả lời: Dãy A ở đây là dãy tăng
-GV: Tại mỗi bước phạm vi tìm kiếm được thu hẹp chỉ còn “một nửa”(chia đôi dãy thành 2 dãy con, hơn kém nhau ko quá 1 phần tử) do đó sẽ tăng nhanh tốc độ tìm kiếm
- Thay vì dùng biến i(như các thuật toán khác), ta dùng biến Giua, xác định số hạng cần so sánh với giá trị khóa, để nhấn mạnh ý tưởng thuật toán.
( GV hướng dẫn HS tìm thuật toán giải bài toán.

- Giải thích thuật toán theo sơ đồ khối

- Lấy ví dụ minh họa




4.cố(1’):
- Nhắc lại khái niệm bài toán.
- Muốn giải bài toán, trước tiên phải xác định được Input và Output
5.xét cuối giờ(1’):
- Đánh giá giờ học.
- Học bài cũ, làm bài tập 4, 5, 6, 7 trang 44 SGK.
RÚT KINH NGHIỆM, BỔ SUNG:
........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................