BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)

Bài: 4 – tiết: 14
Tuần dạy: Ngày dạy:



Mục tiêu:
Kiến thức:
HS biết:
Biết khái niệm bài toán và thuật toán, các đặc trưng chính của thuật toán.
HS hiểu:
Hiểu 1 số thuật toán thông dụng.
Hiểu cách biểu diễn thuật toán bằng ngôn ngữ liệt kê (dùng ngôn ngữ tự nhiên).
Mô tả được thuật toán giải một số bài toán đơn giản bằng ngôn ngữ liệt kê.
Kỹ năng:
Xây dựng được thuật toán giải một số bài toán đơn giản bằng sơ đồ khối hoặc liệt kê.
Về thái độ: Có ý thức sử dụng các kiến thức trên góp phần phát triển tư duy khi giải quyết các vấn đề trong khoa học cũng như trong đời sống.
Trọng tâm:
Mô tả được thuật toán giải một số bài toán đơn giản bằng ngôn ngữ liệt kê.
Chuẩn bị :
3.1 Giáo viên: bảng
3.2 Học sinh: Xem trước của bài 4 : “ Bài toán và thuật toán”
Tiến trình:
Ổn định tổ chức và kiểm diện:
Kiểm tra miệng:
Câu 1: Cho dãy A gồm N số nguyên a1, a2,...,aN. Cần sắp xếp các số hạng để dãy A trở thành dãy không giảm.?
Trả lời:
B1. Nhập N, các số hạng a1, a2,...,aN;
B2. M
N;
B3. Nếu M < 2 thì đưa ra dãy A được sắp xếp rồi kết thúc;
B4. M
M – 1, i
0;
B5. i
i + 1;
B6. Nếu i > M thì quay lại bước 3;
B7. Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
B8. Quay lại bước 5.
Bài mới:

HOẠT ĐỘNG CỦA GV VÀ HS
NỘI DUNG BÀI HỌC

Hoạt động 1:
Tìm kiếm là việc thường xảy ra trong cuộc sống,... 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 các đối tượng cho trước.





Số nguyên k gọi là khóa tìm kiếm.




Hãy xác định I/O của bài toán?
HS: Lên bảng viết.










HS: Có 5 phút nghiên cứu SGK, sau đó lên bảng trình bày thuật toán bằng phương pháp liệt kê.
Hướng dẫn HS hoàn thành thuật toán.







HS: Một HS khác lên bảng dựa vào thuật toán bằng phương pháp liệt kê vẽ sơ đồ khối và trình bày trước lớp.




















HS tự nghiên cứu thuật toán này trong SGK

1. Bài toán:
2. Thuật toán:
3. Một số ví dụ về thuật toán.
Ví dụ 3: Bài toán tìm kiếm



Ta chỉ xét bài toán tìm kiếm dạng đơn giản:
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ố đó.
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: Ta so sánh giá trị k với lần lượt các số hạng của dãy bắt đầu từ a1. Nếu có giá trị nào bằng k thì dừng, ngược lại thì dãy A không có số hạng nào bằng k.
* Thuật toán
a) 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 rồ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.
b) Sơ đồ khối




















Thuật toán tìm kiếm nhi phân (Binari Search).



Câu hỏi bài tập củng cố:
Câu hỏi: Nêu ý tưởng 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 =