Giáo án môn Tin học 10 - Bài 4: Bài toán và thuật toán (tiết 3)

Người soạn: Hà Trung Hòa. Lớp: SP Tin 40
Giáo viên hướng dẫn: Lê Thị Bích Liên
Ngày soạn : 30/09/2008	
Ngày giảng : / /2008	
Bài 4: Bài toán và thuật toán (tiết 3)
I. Mục đích yêu cầu
Học sinh hiểu và thực hiện được thuật toán sắp xếp dãy số.
II. Phương pháp, phương tiện giảng bài
Phương pháp: Thuyết trình, giảng giải
Phương tiện: SGK, SGV, bảng phụ (SGK trang 39)
III. Tiến trình bài giảng
Nội dung
Hoạt động của GV và HS
Ví dụ 2: Bài toán sắp xếp
Ta chỉ xét bài toán dạng đơn giả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.
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 thành một dãy không giảm.
* ý tưởng: Với mỗi cặp số hạng đứ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. Lặp lại quá trình này cho đến khi không có sự đổi chỗ nào xảy ra nữa.
* Thuật toán
a) Liệt kê
 B1. Nhập N, các số hạng a1, a2,...,aN;
 B2. M N;
 B3. Nếu M < 2 thì đưa ra dãy A được sắp xếp rồi kết thúc;
 B4. M M – 1, i 0;
 B5. i i + 1;
 B6. Nếu i > M 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ơ đồ khối
(SGK trang 39)
 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 trong lớp 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 các vị trí theo một tiêu chí nào đó.
Hãy xác định I/O của bài toán?
HS: Lên bảng viết.
 Quá trình so sánh và đổi chỗ sau mỗi lượt chỉ thực hiện với dãy đã bỏ bớt số hạng cuối dãy. Để thực hiện điều đó trong thuật toán sử dụng biến nguyên M có giá trị khởi tạo là N, sau mỗi lượt M giảm đi 1 cho đến khi M < 2.
Mời 1 em lên bảng vẽ sơ đồ khối
HS: Một HS khác lên bảng dựa vào thuật toán bằng phương pháp liệt kê vẽ sơ đồ khối và trình bày trước lớp.
III. Củng cố.
 Mô phỏng việc thực hiện thuật toán trên với dãy A như sau:
6 1 5 3 7 8 10 7 12 4
IV. Dặn dò.
 Học bài cũ và đọc trước ví dụ 3: Bài toán tìm kiếm. 
V. Rút kinh nghiệm.
Nhận xét của giáo viên hướng dẫn
Ngày tháng năm 2008
 Giáo viên hướng dẫn