Bai toan va thuat toan tiet 3

Tiết 12 § 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 Bài toán sắp xếp bằng tráo đổi.
– 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à các phương pháp liệt kê và sơ đồ khối.
Nguyên tắc của việc đổi chỗ giữa hai phần tử.
III. HOẠT ĐỘNG DẠY HỌC:
1. Ổn định tổ chức (2p).
- Ổn định lớp.
- Kiểm tra sĩ số lớp.
2. Kiểm tra bài cũ (8p):
Hỏi: Em hãy viết thuật toán kiểm tra tính nguyên tố của một số nguyên dương bằng phương pháp liệt kê các bước?
Đáp: Cách liệt kê:
B1: Nhập số ng.dương N;
B2: Nếu N=1 thì thông báo N không nguyên tố rồi kết thúc;
B3: Nếu N< 4 thì thông báo N là nguyên tố rồi kết thúc;
B4: i
2 ;
B5: Nếu i>
thì thông báo N là nguyên tố rồi kết thúc.
B6: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc;
B7: i
i + 1 rồi quay lại B5;
3. Giảng bài mới:
TG
Nội dung
Hoạt động của GV và HS

Hoạt động 1: Hướng dẫn giải bài toán sắp xếp bằng thuật toán sắp xếp bằng tráo đổi (Exchange Sort)
















25

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














Ví dụ 2: Bài toán sắp xếp
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.















( GV: Trong cuộc sống hằng ngày chúng ta thường gặp những công việc có liên quan đến sắp xếp như: xếp các học sinh theo thứ tự từ thấp đến cao, xếp điểm trung bình của học sinh trong lớp theo thứ tự từ cao đến thấp. một cách tổng quát, cho một dãy đối tượng, cần sắp xếp lại vị trí các đối tượng theo một tiêu chí nào đó. Chẳng hạn cho 10 chiếc cọc có chiều cao khác nhau (h.22a), cần sắp xếp lại các cọc từ thấp đến cao (h.22b). dưới đây ta chi xét bài toán sắp xếp dạng đơn giản như sau:







( GV: Ví dụ cho dãy A gồm các số nguyên 7, 4, 9, 5, 7. Em hãy nêu cách sắp xếp các số hạng để dãy A trở thành dãy không giảm?
( HS: ban đầu ta so sánh số hạng thứ nhất với số hạng thứ 2, nếu số thứ nhất lớn hơn số thứ 2 thì ta đổi chỗ hai số này. Tương tự ta lại đi so sánh số hạng thứ 2 với số thứ 3, nếu số thứ 2 lớn hơn số thứ 3 ta lại đổi chỗ chúng. Tương tự ta lại so sánh số thứ 3 với số tiếp theo…cứ so sánh như vậy tới hết dãy thì dừng lại.
( Dãy số sau khi sắp xếp là: 4, 5, 7, 7, 9.
( GV: Để giải bài toán sắp xếp dạng tổng quát trên có nhiều thuật toán khác nhau, sau đây chúng ta sẽ cùng nghiên cứu cách giải bài toán này bằng thuật toán sắp xếp bằng tráo đổi.









































































* Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)




( 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.