Ngày soạn: 4 /10/2008
Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 3)
A. MỤC TIÊU
1. Kiến thức:
Hiểu được thuật toán sắp xếp bằng tráo đổi.
2. Kỹ năng:
Xây dựng được thuật toán cho một bài toán.
B. PHƯƠNG PHÁP:
Nêu và giải quyết vấn đề + thuyết trình.
C. CHUẨN BỊ CỦA GIÁO VIÊN VÀ HỌC SINH:
1. Chuẩn bị của GV: SGK
2. Chuẩn bị của HS: SGK
D. TIẾN TRÌNH LÊN LỚP:
1. Ổn định lớp: Kiểm tra sĩ số.
2. Kiểm tra bài cũ:
Câu 1: Nêu các tính chất của thuật toán? Các ký hiệu dùng để biểu diễn thuật toán bằng sơ đồ khối?
Câu 2: Hãy mô tả thuật toán giải phương trình ax + b = 0 bằng sơ đồ khối.
Đáp án:
Câu 1: (SGK)
Câu 2:














3. Bài mới:
a, Đặt vấn đề:
Trong cuộc sống, ta thường gặp những việc liên quan đến sắp xếp như sắp xếp các học sinh theo thứ tự tăng dần theo tên, sắp xếp điểm trung bình của học sinh theo thứ tự từ cao đến thấp… Hôm nay chúng ta sẽ tìm hiểu về thuật toán sắp xếp.
b, Triển khai bài:



HOẠT ĐỘNG CỦA THẦY VÀ TRÒ
NỘI DUNG KIẾN THỨC


Hoạt động 1: Xây dựng thuật toán cho một bài toán thông thường.

GV: Gọi HS xác định bài toán
HS: Xác định bài toán

GV: Gọi HS nêu ý tưởng
HS: Nêu ý tưởng


GV: Gọi 1 HS viết thuật toán bằng cách liệt kê
GV: Nhận xét và giải thích thêm

GV: Gọi 1 HS lên bảng vẽ sơ đồ khối biểu diễn thuật toán.
HS: Vẽ sơ đồ khối.
GV: Nhận xét.










GV: Mô phỏng thuật toán với dãy số: 5 1 4 7 6 15 3


Hoạt động 2: Tìm hiểu thuật toán sắp xếp bằng cách tráo đổi.
HS: Nghiên cứu SGK.
GV: Gọi HS xác định bài toán.
HS: Xác định bài toán.

GV: Gọi HS nêu ý tưởng.
HS: Nêu ý tưởng.
GV: Giải thích cụ thể về ý tưởng.


GV: Hướng dẫn học sinh hình thành thuật toán. Gọi 1 HS trình bày thuật toán bằng cách liệt kê.
HS: Trình bày thuật toán bằng cách liệt kê.
GV: Nhận xét.







GV: Gọi 1 HS trình bày thuật toán bằng sơ đồ khối.
HS: Lên bảng vẽ sơ đồ khối.
GV: Nhận xét.


















GV: Mô phỏng thuật toán bằng một dãy số cụ thể.
3. Một số ví dụ về thuật toán:
Ví dụ 2: Tìm giá trị lớn nhất của một dãy số nguyên.
- Xác định bài toán:
+ Input: Số nguyên n và dãy số a1, a2, ..an
+ Output: Số có giá trị max trong dãy số
- Ý tưởng:
+ Khởi tạo giá trị max ← a1, i ← 2
+ Với i từ 2 đến n: so sánh max với ai nếu ai>max thì max ← ai
- Thuật toán:
+ Cách liệt kê: (SGK)


+ Sơ đồ khối:






















Ví dụ 3: Bài toán sắp xếp
Bài toán: (SGK)
* Thuật toán sắp xếp bằng tráo đổi:
- Xác định bài toán:
+ Input: Dãy số nguyên, số nguyên n
+ Output: Dãy đã được săp xếp theo thứ tự tăng dần.
- Ý tưởng: Với mỗi cặp số hạ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ó đổi chỗ nào xảy ra nữa.
- Thuật toán:
a, Cách liệt kê:
B1: Nhập n, các số hạng a1, a2..an
B2: j ← n
B3: Nếu j <2 thì đưa ra dãy đã được sắp xếp và kết thúc.
B4: j ← j – 1, i ← 0
B5: i ← i +1
B6: Nếu i>j thì quay lại bước 3.
B7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau.
B8: Quay lại bước 5.
b, Sơ