Bai toan va thuat toan tiet 4

Tiết 13 §4: BÀI TOÁN VÀ THUẬT TOÁN (tt)

I. MỤC TIÊU:
Kiến thức:
– Biết vận dụng kiến thức về bài toán và thuật toán trong tin học và hai phương pháp liệt kê các bước và sơ đồ khối để diễn tả thuật toán của hai bài toán Tìm kiếm tuần tự và Tìm kiếm nhị phân.
– Hiểu một số thuật toán thông dụng.
Kĩ năng:
– Biết xây dựng thuật toán của một số bài toán thông dụng.
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.
– Tổ chức hoạt động nhóm, bài tập trắc nghiệm, các dụng cụ trực quan như hình vẽ,…
Học sinh: - Sách giáo khoa, vở ghi lý thuyết, đọc bài trước.
Kiến thức về bài toán và thuật toán trong Tin học và hai phương pháp liệt kê và sơ đồ khối.
Các cách tìm kiếm một phần tử thỏa mãn một điều kiện nào đó.

III. HOẠT ĐỘNG DẠY HỌC:
1. Ổn định tổ chức (2p): Kiểm tra sĩ số lớp.
2. Kiểm tra bài cũ: (5p)
Hỏi: Nêu ý tưởng và viết thuật toán sắp xếp bằng tráo đổi?
Đáp: -Ý tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau thì ta đổi chỗ chúng cho nhau. Việc đó được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa.
- Thuật toán:….
3. Giảng bài mới:

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

HĐ1: Hướng dẫn giải bài toán tìm kiếm bắng thuật toán tìm kiếm tuần tự (Sequential Search).






































10
3. Một số ví dụ: (tt)











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ự được thực hiện một 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á. 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.










( Mô phỏng việc thực hiện thuật toán với:
- k = 2 và N = 10
A
5
7
1
4
2
9
8
11
25
51

i
1
2
3
4
5
-
-
-
-
-

(Với i = 5 thì a5 = 2
- k = 6 và N = 10
A
5
7
1
4
2
9
8
11
25
51


i
1
2
3
4
5
6
7
8
9
10
11

( Với mọi i từ 1 đến 10 không có ai có giá trị bằng 6.

( GV: Tìm kiếm là một việc thường xảy ra trong cuộc sống hằng ngày. Em hãy nêu một ví dụ về tìm kiếm?
( HS: Suy nghĩ trả lời.
( GV: Nhận xét: Tìm kiếm là cần