intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Giáo án Tin học lớp 10: Bài toán - Thuật toán (tiết 5)

Chia sẻ: Hoàng Hưng | Ngày: | Loại File: DOC | Số trang:5

Thêm vào BST
Báo xấu
110
lượt xem 8
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo án Tin học lớp 10: Bài toán - Thuật toán (tiết 5)

  1. 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
  2. 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
  3. 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 
  4. 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
  5. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

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

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2