Giáo án Tin học 10 bài 4 tiết 11: Bài toán - Thuật toán (t3/5)

Ngày soạn: 01/10/2015 Ngày dạy: Lớp dạy: 10B1 Tiết 11 BÀI TOÁN - THUẬT TOÁN (T3/5) I. XÁC ĐỊNH MỤC TIÊU: 1. Lựa chọn chủ đề, nội dung dạy học: Bài toán - Thuật toán. 2. Xác định yêu cầu kiến thức, kỹ năng, thái độ Kiến thức: + Môn Tin: – Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước. – Hiểu một số thuật toán thông dụng kiểm tra tính nguyên tố của 1 số nguyên dương. + Môn Toán: (Địa chỉ tích hợp) - Biết được khái niệm số nguyên tố. - Hiểu và cho 1 số ví dụ về số nguyên tố. Kĩ năng: – Biết xây dựng thuật toán của một số bài toán thông dụng. Thái độ: – Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó. 3. Lập bảng mô tả yêu cầu cần đạt Nội dung Loại câu hỏi / bài tập Nhận biết Thông hiểu Vận dụng thấp Vận dụng cao 3. Một số ví dụ đơn giản Câu hỏi / bài tập định tính Bài tập định lượng Tìm Input, Output và nêu cách giải của bài toán kiểm tra tính nguyên tố của 1 số nguyên dương. Viết được chính xác thuật toán giải bài toán kiểm tra tính nguyên tố của 1 số nguyên dương. Giải thích chính xác hoạt động của thuật toán kiểm tra tính nguyên tố của 1 số nguyên dương. Đọc hiểu thuật toán từ đó phát biểu bài toán. kiểm tra tính nguyên tố của 1 số nguyên dương. Bài tập thực hành 4. Đề xuất năng lực có thể hướng tới: Hiểu các bài toán: Kiểm tra tính nguyên tố của một số nguyên dương. HS phải hiểu được các bài toán này (mô tả được thuật toán bằng ngôn ngữ liệt kê, mô phỏng thực hiện thuật toán với bộ dữ liệu đơn giản). II. CÁC HOẠT ĐỘNG DẠY HỌC Nội dung Hoạt động của Giáo viên Hoạt động của Học sinh Hoạt động 1: Tìm thuật toán giải bài toán Kiểm tra tính nguyên tố của một số nguyên dương III. Một số ví dụ về thuật toán. 1. Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương. · Ý 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ố. · Thuật toán: a) Cách liệt kê: B1: Nhập số ng.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: ii + 1 rồi quay lại B5 · Tổ chức các nhóm thảo luận H. Nhắc lại định nghĩa số nguyên tố? Câu hỏi: Số 1 có phải là số nguyên tố không? Câu hỏi: Số 2 và 3 có phải là số nguyên tố không? Câu hỏi: Số 2 và 3 thuộc phạm vi nào? Câu hỏi: Các số còn lại phải thoả mãn điều kiện nào thì nó mới là một số nguyên tố? H. Hãy xác định Input và Output của bài toán này? Câu hỏi: Trên cơ sử ý tưởng đó. Em hãy xây dựng thuật toán của bài toán trên? · Cho các nhóm tiến hành xây dựng thuật toán bằng phương pháp liệt kê. · Biến i nhận giá trị nguyên thay đổi trong phạm vi từ 2 đến + 1 và dùng để kiểm tra N có chia hết cho i hay không. GV: Gọi HS lên bảng viết và gọi một số HS nhận xét, sữa lỗi và cho HS chép vào vở Câu hỏi: Tại sao phải khởi tạo biến I ban dầu là 2? · Các nhóm thảo luận, trình bày ý kiến. Đ. N là số nguyên tố, nếu: + N ≥ 2 + N không chia hết cho các số từ 2 ® N – 1 hoặc + N không chia hết cho các số từ 2 ® Trả lời: số 1 không phải là số nguyên tố Trả lời: Số 2 và 3 là số nguyên tố Trả lời: Thuộc đoạn từ 1è 4. Trả lời: Thoả mãn điều kiện chỉ chia hết cho 1 và chia hết cho chính nó + Input: N Î Z+ + Output: " N là số nguyên tố " hoặc "N không là số nguyên tố" · Từng nhóm trình bày thuật toán *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ố và kết thúc Bước 4: I=2 Bước 5: Nếu I> [] thì thông báo N là 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 phải là số nguyên tố rồi kết thúc Bước 7: I = I+ 1 Quay lại bước 5 Trả lời: Bởi vì ta đã nhận xét ở bước 2: Số 1 không phải là số nguyên tố Hoạt động 2: Hướng dẫn mô tả thuật toán bằng sơ đồ khối 10 b) Sơ đồ khối: đúng Nhập N N = 1 Thông báo N là số nguyên tố rồi kết thúc i ¬ 2 i> i ¬ i + 1 N chia ht cho i N < 4 Thông báo N không là số nguyên tố rồi kết thúc đúng Sai Sai đúng Sai đúng Sai Hoạt động 3: Mô phỏng việc thực hiện thuật toán Mô phỏng các bước thực hiện thuật toán trên với: N = 31 · Xét với N = 29 có phải là số nguyên tố không? [] = 5 i 2 3 4 5 6 N/i 29/2 29/3 29/4 29/5 Chia hết? Không Không Không Không · Tương tự như trên xét với N = 45 có phải là số nguyên tố không? · Các nhóm thảo luận rồi đưa ra câu trả lời. 29 là số nguyên tố. 45 không phải là số nguyên tố III. BÀI TẬP VỀ NHÀ – Mô phỏng việc thực hiện thuật toán xét tính nguyên tố của các số sau: 41; 55 Bài tập: 1. Có bao nhiêu cách trình bày một thuật toán? a. 2 cách b. 3 cách c. 4 cách d. 1 cách 2. Trong cách diễn tả bằng sơ đồ khối hình thoi - hình chữ nhật dùng để thể hiện lần lượt thao tác: a. so sánh và tính toán b. xuất/nhập dữ liệu và so sánh c. tính toán và xuất nhập dữ liệu d. a, b, c đều sai 3. Trong cách diễn tả bằng sơ đồ khối hình ovan - hình chữ nhật dùng để thể hiện lần lượt thao tác: a. so sánh và tính toán b. xuất/nhập dữ liệu và so sánh c. xuất nhập dữ liệu và tính toán d. a, b, c đều sai 4. Trong cách diễn tả bằng sơ đồ khối hình ovan - hình thoi dùng để thể hiện lần lượt thao tác: a. so sánh và tính toán b. xuất/nhập dữ liệu và so sánh c. xuất nhập dữ liệu và tính toán d. a, b, c đều sai 5. Thuật toán có mấy tính chất? a. 1 b. 2 c. 3 d. 4 6. Xác định lần lượt Input – Output của bài toán: Cho ba số nguyên a, b, c. Kiểm tra xem a, b, c có phải là số đo 3 cạnh của một tam giác hay không? Nếu đúng thì tính chu vi C của tam giác đó.? a. a, b, c nguyên – a, b, c là số đo 3 cạnh của một tam giác? C = ? b. a, b, c nguyên – a, b, c là số đo 3 cạnh của một tam giác? c. a, b, c nguyên – C = ? d. a, b, c đều đúng Chuẩn bị bài mới: Làm thế nào để sắp xếp một dãy số theo chiều tăng hoặc giảm dần – Đọc tiếp bài "Bài toán và thuật toán" IV. RÚT KINH NGHIỆM, BỔ SUNG