Bài 4 bài toán và thuật toán (tiết 1)

Ngày soạn: Ngày dạy:
Tuần:……………Tiết thứ:………….......Người soạn: Phan Ngọc Duyên
§ 4. BÀI TOÁN VÀ THUẬT TOÁN (tiết 3)
(((
I. Mục Tiêu:
1. Kiến thức:
Biết khái niệm bài toán và thuật toán, các tính chất của thuật toán.
Biết cách biểu diễn thuật toán bằng liệt kê các bước và bằng sơ đồ khối.
Biết một số thuật toán thông dụng
2. Kỹ năng:
- Xây dựng thuật toán giải một số bài toán đơn giản bằng liệt kê các bước và bằng sơ đồ khối.
3. Thái độ: chăm chỉ, chú ý lắng nghe
II. Phương pháp và phương tiện dạy học:
1. Phương pháp
- Lấy học viên làm trung tâm.
- Nêu câu hỏi gợi mở, diễn giảng, một số phương pháp khác.
2. Phương tiện
GV: SGK, SGV, giáo án, máy tính, bảng phụ.
HV: SGK, vở ghi, đọc bài trước ở nhà
III. Tiến trình lên lớp và nội dung bài giảng:
1. Ổn định lớp: Kiểm tra sĩ số (1’)
2. Kiểm tra bài cũ: (5’)
Câu hỏi: : Xác định Input và Output của bài toán sau: Kiểm tra số nguyên tố của một số nguyên dương?
3.Bài mới: (thời gian 34’)
Hoạt động GV
Hoạt động HS
Nội dung

Giáo viên gọi HS đọc các tính chất của thuật toán (SGK).
VD: ba tính chất trong thuật toán tìm Max (SGK)
Trả lời câu hỏi
Một số tính chất của thuật toán:
Tính dừng:Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác;
Tính xác định:Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để thực hiện bước tiếp theo;
Tính đúng đắn: Sau khi thuật toán kết thúc ta phải nhận được Output cần tìm.

Trong cuộc sống hàng ngày ta thường gặp những bài toán liên quan đến vấn đề sắp xếp như: sắp xếp danh sách học sinh theo tên, sắp xếp điểm trung bình HS từ lớn đến nhỏ….
Ta sẽ tìm hiểu thuật toán sắp xếp qua ví dụ 2 (SGK)
CH: Xác định input, output của bài toán ?






CH: Các em hiểu dãy không giảm là dãy như thế nào? Cho VD cụ thể?

Giáo viên cho ví dụ để hình thành ý tưởng thuật toán sắp xếp cho học sinh.

Yêu cầu học sinh nghiên cứu SGK sau 2 phút và trình bày lại thuật toán trên theo cách liệt kê.
Giải thích kỹ cho cả lớp nghe từng bước trong thuật toán bằng cách liệt kê.
Cho ví dụ:
N= 3. Dãy: 6 3 4













Input: Dãy A gồm N số nguyên a1, a2,..., aN.
Output: Dãy A được sắp xếp lại thành dãy không giảm.

HS trả lời









Từng em lên trình bày




Chú ý lắng nghe và ghi chép

Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)
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 (tức là số hạng trước không lớn hơn số hạng sau).
Xác định bài toán
Input: Dãy A gồm N số nguyên a1, a2,..., aN.
Output: Dãy A được sắp xếp lại thành dãy không giảm .
Ý 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 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
a) Cách liệt kê
Bước 1: Nhập N, các số hạng a1, a2,..., aN;
Bước 2: M ( N;
Bước 3: Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
Bước 4: M ( M – 1, i ( 0;
Bước 5: i ( i + 1;
Bước 6: Nếu i > M thì quay lại bước 3;
Bước 7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
Bước 8: Quay lại bước 5.

Ví Dụ: N= 3. Dãy: 6 3 4



CH: Em nào có thể cho biết ngoài cách liệt kê thì còn cách nào khác đểbiểu diễn thuật toán nữa không ?

CH: Ứng với mỗi bước trong cách liệt kê ta sẽ sử dụng hình gì trong sơ đồ khối?
Giải thích kỹ cho cả lớp nghe từng bước