TT Tim kiem(cuc hay)

Ngày soạn: 26/09/10 Tuần: 07
Ngày dạy: 30/09/10 Tiết PPCT: 14
Bài 4 BÀI TOÁN VÀ THUẬT TOÁN(tt)
(Tiết 4)
I. MỤC TIÊU:
1. Kiến thức:
– Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước.
– Hiểu một số thuật toán thông dụng.
2. Kĩ năng:
– Xây dựng được thuật toán cho một số bài toán đơn giản. Qua đó hình thành một số kĩ năng chẩ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.
3. Thái độ:
– Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó.
II. CHUẨN BỊ:
Giáo viên: – Giáo án điện tử(Slide Powerpoint) + Giáo án in.
Học sinh: SGK, vở ghi. Soạn bài trước.
III. HOẠT ĐỘNG DẠY - HỌC:
1. Ổn định tổ chức: Kiểm tra sĩ số lớp.
2. Kiểm tra bài cũ:
Hỏi: Nêu ý tưởng thuật toán kiểm tra tính nguyên tố của một số nguyên dương?
Đáp: Theo ĐN về số nguyên tố: Một số nguyên dương N là số nguyên tố nếu nó có đúng 2 ước là 1 và chính nó. Nên ta suy ra:
Nếu N = 1 thì N không là số nguyên tố;
Nếu 1 < N < 4 thì N là số nguyên tố;
Nếu N > 4 và không có ước trong phạm vi từ 2 đến phần nguyên căn bậc hai của N thì N là số nguyên tố.
3. Bài mới
Hoạt động 1: Hướng dẫn tìm thuật toán giải bài toán
Nội dung
Hoạt động của Giáo viên
Hoạt động của Học sinh

III. Một số ví dụ: (tt)
3. Ví dụ 3: Bài toán tìm kiếm
Cho dãy A gồm N số nguyên khác nhau: a1, a2, …, aN và một 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ố đó.
a) Thuật toán tìm kiếm tuần tự (Sequential Search)
( 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ự là 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á. Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá.
( Thuật toán:
* Cách liệt kê:
- B1: Nhập N, các số hạng a1, a2, …, aN và khoá k;
- B2: i
1;
- B3: Nếu ai = k thì thông báo chỉ số i, kết thúc;
- B4: i
i + 1;
- B5: Nếu i >N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc.
- B6: Quay lại bước 3.
Đặt vấn đề: Tìm kiếm là một việc thường xảy ra trong cuộc sống.

Cho dãy A gồm: 5, 7, 1, 4, 2, 9, 8, 11, 25, 51. Tìm i với ai = 2 ?







H. Hãy xác định bài toán?







( GV hướng dẫn HS tìm thuật toán giải bài toán.
# Giống việc tìm các đồ vật trong các ngăn tủ.







( GV hướng dẫn HS trình bày thuật toán tìm kiếm bằng cách liệt kê.



( i là biến chỉ số và nhận giá trị nguyên lần lượt từ 1 đến N+1.






( i = 5







Đ. + Input: N, a1, a2, …, aN, k
+ Output: i hoặc thông báo không có i





( HS trình bày ý tưởng.










( HS lên bảng trình bày.


Hoạt động 2: Diễn tả thuật toán tìm kiếm bằng sơ đồ khối
* Sơ đồ khối:












Hoạt động 3: Mô phỏng việc thực hiện thuật toán