Giáo án Tin học lớp 10: Bài toán - Thuật toán (tiết 5)
lượt xem 8
download
Dưới đây là Giáo án Tin học lớp 10: Bài toán - Thuật toán (tiết 5). Thông qua việc tham khảo bài giáo án này sẽ bổ sung thêm tư liệu cho các bạn trong việc biên soạn một bài giáo án điện tử nói chung và giáo án điện tử môn Tin học nói riêng.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Giáo án Tin học lớp 10: Bài toán - Thuật toán (tiết 5)
- Trêng trung häc phæ th«ng A Líi Ngày soạn: 07/10/2015 Ngày dạy: 10/10/2015 Lớp dạy: 10B1 BÀI TOÁN THUẬT TOÁN (T5/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: – 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 thuật toán tìm kiếm. 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 Loại câu Vận dụng Vận dụng Nội dung Nhận biết Thông hiểu hỏi / bài tập thấp cao Câu hỏi / bài tập định tính Tìm Input, Viết được Giải thích Đọc hiểu 3. Một số Output và nêu chính xác chính xác hoạt thuật toán từ ví dụ đơn Bài tập định cách giải của thuật toán giải động của đó phát biểu giản lượng bài toán tìm bài toán tìm thuật toán tìm bài toán tìm kiếm. kiếm. kiếm. kiếm. 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: Tìm kiếm. 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: Hướng dẫn tim thuật toán giải bài toán Đặt vấn đề: Tìm kiếm là một việc thường xảy ra trong cuộc III. Một số ví dụ: (tt) sống. 3. Ví dụ 3: Bài toán tìm kiếm Cho dãy A gồm N số nguyên khác Cho dãy A gồm: 5, 7, 1, 4, 2, 9, i = 5 nhau: a1, a2, …, aN và một số 8, 11, 25, 51. Tìm i với ai = 2 ? nguyên k. Cần biết có hay không GV: Ths.Hoµng TuÊn Hng - Gi¸o ¸n Tin 10 Trang 1
- Trêng trung häc phæ th«ng A Líi chỉ số i ( 1 ≤ i ≤ N) mà ai = k. Nếu có hãy cho biết chỉ số đó. a) Thuật toán tìm kiếm tuần tự (sequential search) Xác định bài toán Tổ chức các nhóm thảo luận Các nhóm thảo luận, đưa Input: Dãy A gồm N số nguyên ra ý kiến khác nhau a1, a2, …, aN và số nguyên k; H. Hãy xác định bài toán? Đ. + Input: N, a1, a2, …, aN, Output: Chỉ số i mà ai = k hoặc k thông báo không có số hạng nào + Output: i hoặc thông của dãy A có giá trị bằng k. báo không có i Ý tưởng: Tìm kiếm tuần tự là lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoặc gặp một số hạng bằng GV hướng dẫn HS tìm thuật khoá hoặc dãy đã được xét hết và toán giải bài toán. Cho các nhóm trình bày ý không có giá trị nào bằng khoá. tưởng. Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá. Thuật toán: * Cách liệt kê: B1: Nhập N, các số hạng a1, a2, …, aN và khoá k; B2: i 1; B3: Nếu ai = k thì thông báo chỉ số i, kết thúc; B4: i i + 1; GV hướng dẫn HS trình bày B5: Nếu i >N thì thông báo dãy thuật toán tìm kiếm bằng cách Các nhóm thảo luận và A không có số hạng nào có giá trị liệt kê. đưa ra thuật toán. bằng k, rồi kết thúc. B6: Quay lại bước 3. i là biến chỉ số và nhận giá trị nguyên lần lượt từ 1 đến N+1. Hoạt động 2: Diễn tả thuật toán tìm kiếm bằng sơ đồ khối GV: Ths.Hoµng TuÊn Hng - Gi¸o ¸n Tin 10 Trang 2
- Trêng trung häc phæ th«ng A Líi Nhập N và a 1, a2, …, a N; k * Sơ đồ khối: i ←1 Đ Đưa ra i ai = k rồi kết thúc S i ←i +1 S i>N Đ Thông báo dãy A không có số hạng nào có giá trị bằng k rồi kết thúc Hoạt động 3: Mô phỏng việc thực hiện thuật toán k = 2 vµ N = 10 Mô phỏng việc thực hiện thuật A 5 7 1 4 2 9 8 11 25 51 i 1 2 3 4 5 toán với: Víi i = 5 th× a5 = 2. + N = 10, k = 2 Hoạt động 4: Hướng dẫn tìm thuật toán giải bài toán b) Thuật toán tìm kiếm nhị Nhấn mạnh dãy A là một phân (Binary Search) dãy tăng. Xác định bài toán H. So sánh 2 bài toán tìm kiếm Đ. Dãy A ở đây là dãy tăng Input: Dãy A là dãy tăng gồm N trong 2 thuật toán? số nguyên khác nhau a1, a2, …, aN và một số nguyên k GV hướng dẫn HS tìm thuật Output: Chỉ số i mà ai = k hoặc toán giải bài toán. thông báo không có số hạng nào của dãy A có giá trị bằng k. Ý tưởng: Sử dụng tính chất dãy Minh hoạ qua việc tra từ Các nhóm trình bày cách A là dãy tăng, ta tìm cách thu hẹp điển làm nhanh phạm vị tìm kiếm sau mỗi Cho các nhóm thảo luận việc lần so sánh khoá với số hạng tra từ điển. Từ đó rút ra thuật được chọn, ta chọn số hạng aGiữa ở toán. " giữa dãy" để so sánh với k, trong N + 1� � đó Giưa = � �. Khi đó: �2 � Nếu aGiưa = k thì Giưa là chỉ số cần tìm. Nếu aGiưa> k thì do dãy A là dãy đã sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2, …, aGiưa 1 . Nếu aGiưa
- Trêng trung häc phæ th«ng A Líi số lần cho đến khi hoặc đã tìm thấy khoá k trong dãy A hoặc phạm vi tìm kiếm bằng rỗng. Thuật toán: * Cách liệt kê: B1: Nhập N, các số hạng a1, a2, …, aN và khoá k B2: Dau 1,Cuoi N; Dau + Cuoi � � B3: Giưa = � �; � 2 � B4: Nếu aGiưa = k thì thông báo chỉ số Giưa, rồi kết thúc; B5: Nếu aGiưa > k thì đặt Cuoi = Giưa 1, rồi chuyển đến bước 7; B6: Dau Giưa +1; B7: Nếu Dau > cuoi thì thông báo dãy A không có số hạng nào có giá trị bằng k, kết thúc; B8: Quay lại bước 3. Hoạt động 5: Mô tả thuật toán bằng sơ đồ khối Nhập N và a 1, a2, …, a N; k * Sơ đồ khối Dau ← 1; Cuoi ← N Giua ← (Dau + Cuoi)/2 S Đ aGiua = k aGiua > k Cuoi ← Giua - 1 Đ S S Đưa ra Giua rồi Dau ← Giua + 1 Dau > Cuoi kết thúc Đ Thông báo dãy A không có số hạng có giá trị bằng k rồi kết thúc Hoạt động 6: Mô phỏng việc thực hiện thuật toán k = 21, N =10 i 1 2 3 4 5 6 7 8 9 10 Mô phỏng việc thực hiện thuật A 2 4 5 6 9 21 22 30 31 33 Dau 1 6 6 toán với N = 10,k= 21 Cuoi 10 10 7 Giua 5 8 6 aGiua 9 30 21 Lỵt 1 2 3 Lần duyệt thứ ba thì aGiua = k. Vậy chỉ số cần tìm i = Giua = 6. Hoạt động 7: Củng cố các kiến thức đã học GV cho HS nhận xét điểm Các nhóm thảo luận và khác biệt cơ bản của 2 thuật trình bày toán GV: Ths.Hoµng TuÊn Hng - Gi¸o ¸n Tin 10 Trang 4
- Trêng trung häc phæ th«ng A Líi III. BÀI TẬP VỀ NHÀ – Mô phỏng việc thực hiện thuật toán với dãy số khác. – Bài 3, 7 SGK, chuẩn bị tiết sau làm bài tập . IV. RÚT KINH NGHIỆM, BỔ SUNG GV: Ths.Hoµng TuÊn Hng - Gi¸o ¸n Tin 10 Trang 5
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo án Tin học lớp 10 Bài 3: Giới thiệu về máy tính (tiết 2)
4 p | 521 | 35
-
Giáo án Tin học lớp 10 Bài 7 & 8: Phần mềm máy tính - Những ứng dụng của Tin học
7 p | 515 | 33
-
Giáo án Tin học lớp 10 Chương 1 Bài 1: Tin học là một ngành khoa học
5 p | 366 | 30
-
Giáo án Tin học Lớp 10 Bài 11: Tệp và quản lý tệp - Ths. Hoàng Tuấn Hưng
4 p | 316 | 28
-
Giáo án Tin học Lớp 10 Bài 12: Giao tiếp với hệ điều hành - Ths. Hoàng Tuấn Hưng
6 p | 240 | 27
-
Giáo án Tin học Lớp 10 Bài 9: Tin học và xã hội - Ths. Hoàng Tuấn Hưng
4 p | 380 | 27
-
Giáo án Tin học lớp 10 Bài 2: Thông tin và dữ liệu (tiết 1)
5 p | 200 | 16
-
Giáo án Tin học lớp 10: Bài toán - Thuật toán (tiết 4)
3 p | 205 | 14
-
Giáo án Tin học lớp 10 Tiết 14: Bài tập
3 p | 171 | 13
-
Giáo án Tin học lớp 10: Bài tập và thực hành (học tại lớp) - Làm quen với thông tin và mã hóa thông tin
3 p | 229 | 13
-
Giáo án Tin học lớp 10: BTTH 2 - Làm quen với máy tính (tiết 1)
3 p | 188 | 11
-
Giáo án Tin học Lớp 10 Tiết 20: Bài tập
3 p | 148 | 10
-
Giáo án Tin học lớp 10 Bài 9: Bài toán - Thuật toán (tiết 1)
3 p | 132 | 9
-
Giáo án Tin học lớp 10: BTTH 2 - Làm quen với máy tính (tiết 2)
2 p | 106 | 8
-
Giáo án Tin học lớp 10 bài 9: An toàn trên không gian mạng
3 p | 30 | 6
-
Giáo án Tin học lớp 10 (Trọn bộ cả năm)
152 p | 22 | 5
-
Giáo án Tin học lớp 10 bài 10: Thực hành khai thác tài nguyên trên Internet
3 p | 23 | 4
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn