Tin học 8 - Tiết 13, 14 - Bài 4 Bài toán và thuật toán (tiếp)

Tuần 7 Ngày soạn: 10/09 Tiết 13,14 Ngày dạy:

§4. BÀI TOÁN VÀ THUẬT TOÁN (TT)

I. Mục tiêu 1. Kiến thức

- Học sinh biết 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 - Học sinh chỉ ra được Input và Output của mỗi bài toán đưa ra. 2. Kỹ năng - Hiểu và nhận biết được Input và Output trong mỗi bài toán. 3. Thái độ - Chú ý nghe giảng, hăng hái phát biểu ý kiến. - Có thái độ học tập nghiêm túc. II. Chuẩn bị của giáo viên và học sinh 1. Chuẩn bị của giáo viên: SGK, Giáo án, Tài liệu tham khảo. 2. Chuẩn bị của học sinh: SGK, vở ghi III. Phương pháp: Hướng dẫn giảng giải, minh họa trực quan, nêu câu hỏi để học sinh thảo luận trả lời. Hoạt động nhóm, hoạt động cá nhân IV. Hoạt động dạy - học 1. Ổn định tổ chức 2. Kiểm tra bài cũ:

-Viết thuật toán tìm Max của dãy số nguyên bằng liệt kê

GV: Nhận xét và ghi điểm. 3. Nội dung bài mới

Hoạt động của thầy và trò Nội dung

GV: Số nguyên tố là gì? HS: Trả lời. GV: Chốt lại: Một số nguyên dương N là số nguyên tố nếu nó có đúng hai ước số khác nhau là 1 và chính nó. HS: Lắng nghe và ghi nhớ. GV: Yêu cầu HS xác định bài toán. HS: Xác định bài toán. GV: Từ định nghĩa trên các em hãy thử nêu ý tưởng để giải bài toán? HS: Trả lời. GV: Mời HS lên viết và thử giải thích thuật toán (dưới dạng liệt kê). HS: Thực hiện. GV: Yêu cầu HS còn lại nhận xét và hoàn thiện. HS: Trả lời. GV: Gọi HS tự ra ví dụ và tự kiểm tra thuật toán. HS: Thực hiện. GV: Yêu cầu HS về nhà hoàn thiện thuật toán dưới dạng sơ đồ khối.

3. Một số ví dụ về thuật toán a. Thuật toán kiểm tra tính nguyên tố của một số nguyên dương * 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à số 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ố. ta có thuật toán như sau: * Thuật toán a. Cách liệt kê

Bước 1: Nhập số nguyên dương N Bước 2: Nếu N=1 thì thông báo N không là số nguyên tố

Bước 3: Nếu N<4 thì thông báo N là số nguyên tố.

Bước 4: i <- 2

ThuVienDeThi.com

HS: Lắng nghe và ghi nhớ.

GV: Trong cuộc sống ta thường gặp những bài toán sắp xếp ví dụ sắp điểm từ thấp đến cao hay sắp xếp học sinh theo ABC.v.v... Hôm nay chúng ta đi tìm hiểu một số thuật toán sắp xếp cơ bản. GV: Đưa ra ví dụ về thuật toán sắp xếp rồi cho học sinh xác định Input, Output và ý tượng thuật toán. HS: Đứng tại chỗ trả lời. GV: Ghi lên bảng và phân tích ý tưởng thuật toán rồi gọi học sinh lên bảng viết thuật toán. HS: Lên bảng viết thuật toán GV: Gọi học sinh khác nhận xét về thuật toán trên. HS: Đứng tại chỗ nhận xét. GV: Tổng hợp lại, chính sửa thuật toán cho phù hợp và phân tích các bước hoạt động của thuật toán. GV: Yêu cầu HS về nhà hoàn thiện thuật toán dưới dạng sơ đồ khối. HS: Lắng nghe và ghi nhớ.

GV: Trong cuộc sống tìm kiếm là việc thường xuyên xảy ra vi dụ tìm một quốn sách trên giá sách hay tìm một học sinh trong lớp .v.v... Hôm nay chúng đi tìm hiểu một số thuật tìm kiếm cơ bản. GV: Đưa ra ví dụ bài toán Giải thích, gợi ý để học sinh đưa ra ý tưởng thuật toán. HS: Xác định bài toán.

Bước 5: Nếu i> [ ] thì thông báo N là N số nguyên tố rồi kết thúc.

Bước 6: 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.

Bước 7: i <-i+1 rồi quay lại bước 5 b. Sơ đồ khối

b. 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 (tức là số hạng trước không lớn hơn số hạng sau). Thuật toán Sắp xếp bằng tráo đổi (Exchange Sort) * Xác định bài toán - Input: Số nguyễn dương N, dãy a1, a2,., aN. - Output: Dãy a1, a2,., aN được sắp xếp thành dãy không giảm. * Ý tưởng: Ta so sánh lần lượt các 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 đổi chỗ đượ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ê

Bước 1: Nhập N, và dãy a1, a2,..., aN; Bước 2: M  N; Bước 3: Nếu M < 2 thì đưa ra dãy A đã …