BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)

Bài: 4 – tiết: 13
Tuần dạy: ………. Ngày dạy:


Mục tiêu:
Kiến thức:
HS biết:
Biết khái niệm bài toán và thuật toán, các đặc trưng chính của thuật toán.
HS hiểu:
Hiểu 1 số thuật toán thông dụng.
Hiểu cách biểu diễn thuật toán bằng ngôn ngữ liệt kê (dùng ngôn ngữ tự nhiên).
Mô tả được thuật toán giải một số bài toán đơn giản bằng ngôn ngữ liệt kê.
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ê.
Về thái độ: Có ý thức sử dụng các kiến thức trên góp phần phát triển tư duy khi giải quyết các vấn đề trong khoa học cũng như trong đời sống.
Trọng tâm:
Mô tả được thuật toán giải một số bài toán đơn giản bằng ngôn ngữ liệt kê.
Chuẩn bị :
3.1 Giáo viên: bảng
3.2 Học sinh: Xem trước của bài 4 : “ Bài toán và thuật toán”
Tiến trình:
Ổn định tổ chức và kiểm diện:
Kiểm tra miệng:
Câu 1: Xác định bài toán, nêu ý tưởng để giải bài toán kiểm tra tính nguyên tố của một số nguyên dương?
Trả lời:
* Xác định bài toán
- Input: N là một số nguyên dương;
- Output: “ N là số nguyên tố” hoặc “ N không là số nguyên tố”;
* Ý tưởng:
- Nếu N=1 thì N không là số nguyên tố;
- Nếu 1 < N < 4 thì N là nguyên tố;
- Nếu N ≥ 4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc hai của N thì N là số nguyên tố.
Bài mới:

HOẠT ĐỘNG CỦA GV VÀ HS
NỘI DUNG BÀI HỌC

Hoạt động 1:

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 hs 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.




HS: Có 5 phút nghiên cứu SGK, sau đó lên bảng trình bày thuật toán bằng phương pháp liệt kê.
Hướng dẫn HS hoàn thành thuật toán.




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.
1. Bài toán:
2. Thuật toán:
3. Một số ví dụ về thuật toán.
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) Ví dụ 2: Bài toán sắp xếp


Câu hỏi bài tập củng cố:
Câu hỏi: 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.
Trả lời:
Ý tưởng: Với mỗi cặp số hạng đứng