Tuần 7: Tiết 13: Ngày soạn: 10/10/2007
Bài 4: Bài toán và thuật toán
I- Mục tiêu:
1. Về kiến thức:
- Biết cách diễn tả thuật toán bằng một trong hai phương pháp: Liệt kê và sơ đồ khối.
- Nắm dược các tính chất cơ bản của thuật toán.
2. Về kĩ năng:
- Diễn tả được thuật toán theo cách liệt kê hoặc bước đầu thể hiện được thuật toán bằng sơ đồ khối.
- Hiểu và diễn tả được một số bài toán cơ bản.
3. Về thái độ:
Rèn luyện lòng say mê nghiên cứu tìm hiểu và tư duy khoa học.
Tác phong làm việc độc lập sáng tạo, nâng cao lòng say mê học tập bộ môn.
II- Chuẩn bị:
1. Giáo viên:
- Chuẩn bị tranh vẽ, máy tính và một số bài toán áp dụng để rèn luyện kỹ năng biểu diễn thuật toán.
2. Học sinh:
- Sách giáo khoa và các ví dụ trong sách giáo khoa.
III- Hoạt động dạy học:

Hoạt động của giáo viên
Hoạt động của học sinh

định lớp:
Bài cũ:
? Thuật toán là gì? Nêu các tính chất của thuật toán?
? Hãy diễn tả thuật toán liệt kê đối với bài toán kiểm tra N có phải là số nguyên tố hay không?
Bài mới:
Hoạt động 1
Giới thiệu và hướng dẫncho học sinh mô tả thuật toán của một số bài toán điển hình- bài toán sắp xếp.
( Trong cuộc sống ta thường gặp những việ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 theo thứ tự từ cao đến thấp. Nói 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 đó. Sau đây ta chỉ xét bài toán sắp xếp dạng đơn giản.
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).
? Hãy xác định bài toán?

? Từ input và output của bài toán em hãy nêu ý tưởng giải bài toán?


( nghĩa là ta lấy a1 so sánh với a2 nếu a1>a2 thì ta tiến hành đổi chỗ hai vị trí này cho nhau, lần lượt so sánh cho đến khi không còn có sự đổi chỗ xảy ra nữa.
? Từ ý tưởng của bài toán em hãy viết thuật toán dạng liệt kê?

( Sau mỗi lần duyệt giá trị lớn nhất của dãy A sẽ được chuyển về cuối dãy số và sau lượt sắp xếp thứ nhất thì giá trị lớn nhất được xếp đúng vị trí là ở cuối dãy. Tương tự như vậy cho các lượt tiếp theo. Tóm lại, sau mỗi lần duyệt có ít nhất một số hạng được sắp xếp đúng vị trí và không còn tham gia vào quá trình đổi chỗ nữa, giống như các bọt nước từ đáy hồ đã lên mặt nước ( cuối dãy) rồi tan biến. Có thể vì thế mà sắp xếp bằng tráo đổi còn có tên gọi là sắp xếp nổi bọt.

HS bá