&4. BÀI TOÁN VÀ THUẬT TOÁN
Ngày soạn : 4/10/2007
Tiết : 12
Lớp : 10
I. MỤC ĐÍCH YÊU CẦU (Như tiểt 10)
II. CHUẨN BỊ
Thầy:
- Soạn giáo án, nghiên cứu sách giáo khoa, sách bài tập, tài liệu tham khảo.
- Máy tính cá nhân và máy chiếu ( nếu có).
Trò: Đọc trước ở nhà Sách giáo khoa.
III.TIẾN TRÌNH LÊN LỚP.
1. Ổn định tổ chức, kiểm tra sĩ số (1’).
2. Kiểm tra bài cũ (5’).
- Câu hỏi:
Liệt kê các bước kiểm tra tính nguyên tố của một số nguyên dương?
- Đáp án:
+ B1: Nhập số nguyên dương N.
+ B2: Nếu N=1 thì thông báo N không nguyên tố rồi kết thúc.
+ B3: Nếu N<4 thì thông báo N là nguyên tố rồi kết thúc.
+ B4: i ←2;
+ B5: Nếu i>[
] thì thông báo N là nguyên tố rồi kết thúc.
+ B6: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc.
+ B7: i← i+1 rồi quay lại bước 5.
- Đối tượng HS: HS trung bình.
3. Nội dung bài học mới.
Nội dung
Hoạt động của GV
Hoạt động của HS


3. Một số ví dụ về thuật toán.




Ví dụ 2: Bài toán sắp xếp.



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 lại thành 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. Việc đó được lặp lại cho đến khi không có sự đổ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: 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 B3;
B7: Nếu ai >ai+1 thì tráo đổi ai và ai+1 cho nhau;
B8: Quay lại B5.

















b) Sơ đồ khối.





















Ví dụ minh hoạ thuật toán:
Sắp xếp dãy số nguyên sau theo thứ tự không giảm.
6 1 5 3 7 8 10 7 12 4
GV: 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 HS từ cao đến thấp trong giờ chào cờ. Yêu cầu HS nêu một số ví dụ về sắp xếp.
GV: Nói tổng quát, cho một dãy đối tượng hãy sắp xếp theo một tiêu chí nào đó. Vậy sắp xếp các đối tượng đó như thế nào, ta sẽ tìm hiểu thuật toán sắp xếp cơ bản.
GV: Gọi HS xác định bài toán.
GV: Nhận xét và ghi bảng.
GV: Ví dụ với dãy số nguyên: 6, 1, 5, 3, 7, 8, 10, 7, 12, 4. thì sau khi sắp xếp kết quả là?
GV: Gọi HS nêu ý tưởng thuật toán.

GV: Chốt lại và ghi bảng




GV: Nêu các bước của thuật toán theo cách liệt kê.
GV: Sau mỗi lần tráo đổi, vị trí lớn nhất của dãy A sẽ được chuyển dần về cuối dãy và sau lượt thứ nhất thì giá trị lớn nhất xếp đúng vị trí là ở cuối dãy.Tương tự, sau lượt thứ hai, giá trị lớn thứ hai được xếp đúng ở vị trí sát cuối…Sau mỗi lượt có ít nhất một số hạng đã xếp đúng vị trí và không còn tham gia vào quá trình đổi chỗ nữa.
GV: Như vậy 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 1 đơn vị cho đến khi M < 2 thì thuật toán kết thúc. i là biến