13 - BAI TOAN VA THUAT TOAN (Tiet 4)

Ngày soạn : Tiết :
Ngày dạy : Lớp :
§4. BÀI TOÁN VÀ THUẬT TOÁN
(Tiết 4)
MỤC TIÊU
1. Kiến thức
- Biết bài toán sắp xếp trong tin học.
2. Kỹ năng
- Hiểu và trình bày được thuật toán sắp xếp bằng tráo đổi (Exchange Sort) theo 2 cách liệt kê và sơ đồ khối, vận dụng linh hoạt trong lớp những bài toán dạng này.
PHƯƠNG PHÁP, PHƯƠNG TIỆN DẠY HỌC
1. Chuẩn bị của giáo viên
- Đồ dùng: Giáo án, SGK, SGV, tài liệu tham khảo máy chiếu (nếu có)
- Phương pháp: Thuyết trình, vấn đáp.
2. Chuẩn bị của học sinh
- Đồ dùng học tập: SGK, vở ghi, bút,....
III. NỘI DUNG BÀI GIẢNG
1. Ổn định tổ chức lớp
- Ổn định lớp.
- Chỉnh đốn trang phục.
- Sĩ số:.........Vắng:......
2. Kiểm tra bài cũ
Câu 1: Hãy mô tả thuật toán kiểm tra tính nguyên tố của một số nguyên dương theo phương pháp liệt kê?
Câu 2: Hãy mô tả thuật toán kiểm tra tính nguyên tố của một số nguyên dương theo phương pháp sơ đồ khối?
3. Đặt vấn đề
4. Nội dung bài mới
Hoạt động của GV
Hoạt động của HS
Tg


Ví dụ 2: Bài toán sắp xếp.
Hoạt đông 1: Giới thiệu cho học sinh về bài toán sắp xếp.


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


Ví dụ:
Dãy 7 4 9 5 7 sau khi sắp xếp được dãy:
4 5 7 7 9
GV: Để sắp xếp dãy này có nhiều thuật toán sắp xếp. Sau đây chúng ta nghiên cứu thuật toán sắp xếp bằng tráo đổi.
3. Một số ví dụ
Ví dụ 2: Bài toán sắp xếp.
Giới thiệu bài toán sắp xếp là bài toán cơ bản trong tin học: cho một dãy đối tượng, cần sắp xếp lại vị trí các đối tượng theo 1 tiêu chí nào đó.








Bài toán: 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).


Hoạt động 2: Hướng dẫn học sinh tìm ý tưởng của thuật toán sắp xếp bằng tráo đổi (Exchange Sort).
- Yêu cầu học sinh xác định bài toán.





Ví dụ: Cho dãy số nguyên sau:
6 1 5 3 7
Theo em dãy số này nếu xếp tăng dần thì sẽ như thế nào?


GV: Đưa ra phương án sắp xếp:
Giả sử dãy có N phần tử ban đầu ta so sánh số thứ nhất với số thứ hai, nếu số thứ nhất lớn hơn số thứ hai thì ta đổi chỗ hai số này.
Tương tự như vậy ta sẽ so sánh số thứ hai với thứ ba nếu số thứ hai lớn hơn số thứ ba thì ta đổi chỗ hai số này. Tương tự ta lại tiếp tục so sánh số thứ ba với số tiếp theo... cứ tiếp tục làm như vậy tới hết dãy thì dừng lại.
Sau lần duyệt đầu tiên thì phần tử lớn nhất sẽ được đẩy về cuối dãy (Vị trí thứ N) và đó cũng chính là vị trí của nó trong sắp xếp. Ta lại tiếp tục lần duyệt thứ hai với dãy bắt đầu từ phần tử đầu tiên đến vị trí thứ N-1. Cứ tiếp tục làm như vậy cuối cùng ta sẽ được một dãy hoàn chỉnh theo chiều tăng dần. Như vậy để được dãy tăng dần ta cần phải thực hiện N -1 lần duyệt





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


- HS: đưa ra dãy đã sắp xếp tăng dần.
1 3 5 6 7


- HS: quan sát












* ý tưởng bài toán
- Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số đứng trước lớn hơn số sau,