Giáo án Tin học 10 - Tiết 12 - Bài 4: Bài toán và thuật toán

bài 4: Bài toán và thuật toán (Tiết 12) Ngày soạn: 10/10/07 I- Mục đích và yêu cầu. - Khái niệm thuât toán, một số vi dụ của bài toán. VD thuật toán - Cách diễn giải bài toán theo 2 cách - Phương pháp : Diễn giảng, giải thích - Đồ dùng: Sơ đồ, GAĐT II- Nội dung. 1. ổn định tổ chức lớp. Lớp Sĩ số Vắng Ghi chú 10A5 42 10A6 48 10A7 2. Kiểm tra bài cũ. 3. Bài mới. Nội dung Hoạt động của GV và HS 3. Một số ví dụ về thuật toán Ví dụ 1. 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: Ta nhớ lại định nghĩa: 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ó. Từ định nghĩa đó, ta suy ra: 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ố. GV: Nhắc lại số nguyên tố là số như thế nào HS: Trả lời câu hỏi  ã Thuật toán a) Thuật toán diễn tả bằng cách liệt kê Nhập số nguyên dương N; Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc; Nếu N < 4 thì thông báo N là nguyên tố rồi kết thúc; i <— 2; Nếu i > [] thì thông báo N là nguyên tố rồi kết thúc; 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; i <— i + 1 rồi quay lại bước 5. GV: Treo bảng phụ, hoặc chiếu bằng máy chiếu GV: Nhìn sơ đồ khối và diễn giải GV: Dựa vào sơ đồ khối, hs liệt kê các bước theo sơ đồ. GV cùng HS thực hiện mô phỏng với thuật toán VD: N = 29 ( = 5) N = 45 ( = 6) Với N = 29 () Với N = 45 () i 2 3 4 5 6 i 2 3 N/i 29/2 29/3 29/4 29/5 N/i 45/2 45/3 Chia hết không? Không Không Không Không Chia hết không? Không Chia hết a) 29 là số nguyên tố b) 45 không là số nguyên tố Ví dụ 2. Bài toán sắp xếp VD: 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: 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ê Nhập N, các số hạng a1, a2,..., aN; M <— N; Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc; M <— M – 1, i <— 0; i <— i + 1; Nếu i > M thì quay lại bước 3; Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau; Quay lại bước 5. VD: Mô phỏng thuật toán GV: Trong cuộc sống, ta thường gặp những việc liên quan đến sắp xếp như học sinh xếp hàng theo thứ tự từ thấp đến cao, giáo viên xếp loại học lực học sinh trong lớp. GV: 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 vị trí các đối tượng theo một tiêu chí nào đó. VD: Chẳng hạn, cho 10 chiếc cọc có chiều cao khác nhau cần xếp lại sao cho cọc thấp ở trước, cọc cao ở sau VD: Ví dụ, với A là dãy gồm các số nguyên: 6, 1, 5, 3, 7, 8, 10, 7, 12, 4, sau khi sắp xếp ta có dãy: 1, 3, 4, 5, 6, 7, 7, 8, 10, 12. GV: Treo bảng phụ, hoặc chiếu bằng máy chiếu GV: Nhìn sơ đồ khối và diễn giải GV: Dựa vào sơ đồ khối, hs liệt kê các bước theo sơ đồ. GV cùng HS thực hiện mô phỏng với thuật toán Ta thấy rằng, sau mỗi lần đổi chỗ, giá trị lớn nhất của dãy A sẽ được chuyển dần về cuối dãy 4. củng cố: - Nắm được hai cách diễn giải theo cách liệt kê và sơ đồ khối của VD kiểm tra tính nguyên tố của một số nguyên dương và Thuật toán Sắp xếp bằng tráo đổi (Exchange Sort) 5. Bài tập về nhà: Bài tập: 1, 2, 3, 4, 5, 6 SGK (27) III. Rút kinh nhgiệm giờ dạy.