Ngày soạn:25/09/09 Ngày dạy : 29/09/09 Dạy lớp:10A5
Tiết 11 - Bài toán và thuật toán
I. Mục tiêu:
1. Kiến thức:
- Biết được khái niệm về bài toán và thuật toán, các tính chất của thuật toán.
- Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và bằng phương pháp liệt kê các bước.
- Hiểu một số thuật toán đơn giản và thông dụng.
- Xây dựng được thuật toán giải một một số bài toán đơn giản bằng sơ đồ khối hoặc liệt kê các bước.
2. 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ê các bước.
3. Thái độ:
- Tư duy logic và rèn luyện khả năng làm việc khoa học, chuẩn xác.
II. Chuẩn bị của GV và HS:
1. Chuẩn bị của GV: Bài soạn, sgk, sgv Tin học 10, tài liệu tham khảo, sơ đồ khối cho một số bài toán đơn giản.
2. Chuẩn bị của HS: Sách giáo khoa tin học 10, kiến thức toán học, đồ dùng học tập.
III. Tiến trình bài dạy:
1. Kiểm tra bài cũ: (5’)
Câu hỏi:
Viết thuật toán liệt kê cho bài toán sau:
Bài toán: Cho dãy A gồm N số nguyên a1,…, an. Sắp xếp dãy theo chiều tăng dần.
Trả lời:
- Thuật toán liệt kê:
Bước 1: Nhập N và dãy a1, …, an
Bước 2: M ( N
Bước 3: Nếu M < 2 thì đưa ra dãy A đã 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.
* Trong cuộc sống, chúng ta thường gặp những công việc liên quan đến sắp xếp như: Sắp xếp điểm trung bình, sắp xếp họ tên… Để giải quyết vấn đề này ta cùng tìm hiểu thuật toán sắp xếp bằng tráo đổi. (1’)
2. Dạy nội dung bài mới:
Hoạt động của giáo viên
TG
Hoạt động của học sinh

Hoạt động 3: Thuật toán sắp xếp bằng tráo đổi (Exchange)
8’
- Hoạt động cá nhân và tập thể

Cho dãy A là dãy gồm các 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).
Ví dụ: Với A là dãy gồm các số nguyên: 6, 1, 5, 3, 7, 8, 10, 7, 12, 4 sau khi sắp xếp ta có dãy: 1, 3, 4, 5, 6, 7, 7, 8, 10, 12.
GV: Hãy xác định bài toán cho ví dụ trên?
* Xác định bài toán
- Input: Dãy A gồm N số nguyên a1,…, aN.
- Output: Dãy A được sắp xếp là dãy không giảm.
* Xác định thuật toán
GV: Xác định thuật toán