Soạn mới giáo án Tin học 7 KNTT bài 15: Thuật toán tìm kiếm nhị phân

Soạn mới Giáo án tin học 7 kết nối tri thức bài Thuật toán tìm kiếm nhị phân. Đây là bài soạn mới nhất theo mẫu công văn 5512. Giáo án soạn chi tiết, đầy đủ, trình bày khoa học. Tài liệu có bản word tải về. Hi vọng đây sẽ là tài liệu hữu ích để thầy cô tham khảo và nâng cao chất lượng giảng dạy. Mời thầy cô và các bạn kéo xuống tham khảo

Cùng hệ thống với: Kenhgiaovien.com - tech12h.com - Zalo hỗ trợ: Fidutech - nhấn vào đây

Rõ nét về file powerpoint trình chiếu. => Xem thêm

BÀI 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

(2 tiết)

 

I. MỤC TIÊU

1. Mục tiêu

Sau bài học này, HS sẽ:

-       Giải thích được thuật toán tìm kiếm nhị phân.

-       Biểu diễn và mô phỏng được hoạt động của thuật toán tìm kiếm nhị phân trên bộ dữ liệu vào có kích thước nhỏ.

-       Giải thích được mối liên quan giữa sắp xếp và tìm kiếm, nêu được ví dụ minh họa.

2. Năng lực

-       Năng lực chung:

·      Tự chủ và tự học: biết lắng nghe và chia sẻ ý kiến cá nhân với bạn, nhóm và GV. Tích cực tham gia các hoạt động trong lớp.

·      Giao tiếp và hợp tác: có thói quen trao đổi, giúp đỡ nhau trong học tập; biết cùng nhau hoàn thành nhiệm vụ học tập theo sự hướng dẫn của thầy cô.

·      Giải quyết vấn đề và sáng tạo: biết phối hợp với bạn bè khi làm việc nhóm, có sáng tạo khi tham gia các hoạt động tin học.

-       Năng lực riêng:

·      Giải thích được thuật toán tìm kiếm nhị phân.

·      Biểu diễn và mô phỏng được hoạt động của thuật toán tìm kiếm nhị phân trên bộ dữ liệu vào có kích thước nhỏ.

·      Giải thích được mối liên quan giữa sắp xếp và tìm kiếm, nêu được ví dụ minh họa.

3. Phẩm chất

-       Các hoạt động khuyến khích các em hợp tác làm việc có trách nhiệm, có sự trao đổi, tôn trọng ý kiến người khác. Giúp các em có điều kiện học tập lẫn nhau.

-       Chia sẻ niềm vui khi cùng nhau hoàn thành một sản phẩm.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU

1. Đối với giáo viên

-       SGK, SGV, SBT Tin học 7.

-       Máy tính, máy chiếu.

2. Đối với học sinh

-       SGK, SBT Tin học 7.

III. TIẾN TRÌNH DẠY HỌC

A. HOẠT ĐỘNG KHỞI ĐỘNG

a. Mục tiêu: Thông qua hoạt động, đặt HS vào tình huống thực tiễn chứa đựng vấn đề cần giải quyết.

b. Nội dung:

- GV cho HS đọc tình huống trong SGK và yêu cầu HS đưa ra cách giải quyết tình huống.

 - GV nhấn mạnh nhu cầu thuật toán tìm kiếm khác.

c. Sản phẩm học tập: HS nêu được bài toán tìm kiếm trong thực tiễn và nhu cầu tìm hiểu thuật toán tìm kiếm khác.

d. Tổ chức thực hiện:

Bước 1: GV chuyển giao nhiệm vụ học tập

GV cho HS đọc tình huống trong SGK và xử lí tình huống: Việc kinh doanh mở rộng, số lượng khách hàng của cửa hàng bán giống cây trồng nhà An lên đến hàng trăm người. Việc tìm kiếm tên khách hàng trong danh sách thật khó khăn. Em có gợi ý gì cho bạn An để việc tìm kiếm được dễ dàng hơn không?

Bước 2: HS thực hiện nhiệm vụ học tập

HS đọc tình huống trong SGK và xử lí tình huống: Để việc tìm kiếm của An được dễ dàng hơn, bạn có thể:

+ Sắp xếp danh sách để tìm dễ hơn.

+ Đưa danh sách vào phần mềm soạn thảo văn bản hoặc bảng tính và sử dụng chức năng tìm kiếm của phần mềm để tìm kiếm.

HS hoạt động nhóm và thực hiện nhiệm vụ.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS lắng nghe cách xử lí tình huống của bạn và nhận xét.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV đánh giá, nhận xét.

- GV nhấn mạnh nhu cầu cần có thuật toán tìm kiếm khác để giải quyết bài toán tìm kiếm nhanh hơn và cách tìm kiếm nhanh hơn là tìm kiếm một danh sách đã được sắp xếp.

- GV dẫn dắt HS vào bài học: Bài 15: Thuật toán tìm kiếm nhị phân.

B. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1: Thuật toán tìm kiếm nhị phân

a. Mục tiêu: Thông qua hoạt động, HS hiểu hoạt động của thuật toán tìm kiếm nhị phân, đánh giá và so sánh với thuật toán tìm kiếm tuần tự. HS thấy được ý nghĩa của bài toán sắp xếp đối với bài toán tìm kiếm.

b. Nội dung:

GV tổ chia cho HS hoạt động nhóm, quan sát hình 15.1, đọc hiểu mục 1. Thuật toán tìm kiếm nhị phân SGK tr.74 và trả lời câu hỏi HD1.

- GV trình bày sơ đồ khối của thuật toán và hoàn thiện HD1.

- GV tổ chức cho HS đọc nội dung Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên SGK tr.76 và nêu các bước cụ thể.

- GV tổ chức cho HS làm việc cá nhân và thực hiện hoạt động câu hỏi SGK tr.76.

c. Sản phẩm học tập: Thuật toán tìm kiếm nhị phân và các bước mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên.

d. Tổ chức hoạt động:

HOẠT ĐỘNG CỦA GV – HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

Hoạt động 1. Sắp xếp và tìm kiếm

GV tổ chức HS hoạt động nhóm, quan sát hình 15.1, đọc hiểu mục 1.Thuật toán tìm kiếm nhị phân và thực hiện Hoạt động 1. Sắp xếp và tìm kiếm:

+ Em hãy cho biết thuật toán tìm kiếm tuần tự phải thực hiện bao nhiêu bước lặp để tìm được khách hàng tên “Trúc” trong danh sách ở Hình 15.1? Em hãy so sánh số bước lặp thực hiện của thuật toán tìm kiếm tuần tự với số bước lặp thực hiện của thuật toán tìm kiếm nhị phân.

+ Theo em trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần thỏa mãn điều kiện gì? Nếu không thỏa mãn điều kiện đó, thuật toán tìm kiếm nhị phân có thực hiện được không?

Table

Description automatically generated

* Thuật toán tìm kiếm tuần tự

- GV đặt câu hỏi cho HS: Từ tình huống khởi động, em hãy nêu cách làm của An? Nêu rõ các bước làm.

Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên

- GV tổ chức cho HS đọc nội dung Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên SGK tr.73 và thực hiện nhiệm vụ: Em hãy trình bày các bước mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên.

- GV chốt kiến thức:

Text

Description automatically generated 

* Câu hỏi/SGK tr.76

- GV tổ chức cho HS hoạt động cặp đôi và trả lời mục câu hỏi SGK tr.76:

Bước 2: HS thực hiện nhiệm vụ học tập

HS đọc hiểu mục Thuật toán tìm kiếm nhị phân và thực hiện Hoạt động 1.

- HS đọc nội dung Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên SGK tr.76 và thực hiện nhiệm vụ.

HS hoạt động cặp đôi và trả lời mục câu hỏi SGK tr.76.

- GV hướng dẫn, theo dõi, hỗ trợ HS nếu cần thiết.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện HS trả lời câu hỏi và hoàn thành bài tập.

- GV mời đại diện HS khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV đánh giá, nhận xét, chuẩn kiến thức.

- GV chuyển sang nội dung mới.

 

 

 

 

 

 

1. Thuật toán tìm kiếm tuần tự

* Hoạt động 1. Sắp xếp và tìm kiếm

- Thuật toán tìm kiếm tuần tự phải thực hiện 8 bước để tìm khách hàng tên “Trúc” trong danh sách ở hình 15.1, trong khi thuật toán tìm kiếm nhị phân chỉ thực hiện 4 bước. Như vật thuật toán tìm kiếm nhị phân nhanh hơn.

- Trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách tên khách hàng cần được sắp xếp. Nếu không được sắp xếp, thuật toán tìm kiếm nhị phân không thể thu hẹp phạm vi tìm kiếm vì giá trị cần tìm có thể ở vị trí bất kì trong danh sách.

* Thuật toán tìm kiếm tuần tự

- Danh sách khách hàng nhiều → sắp xếp theo thứ tự chữ cái tên khách hàng trên máy tính.

- An so sánh giá trị cần tìm với giá trị ở giữa danh sách

+ Giá trị cần tìm ở giữa danh sách → dừng lại.

+ Lớn (nhỏ) hơn thì tìm ở nửa sau (đầu) của danh sách

- Lặp lại quá trình đến khi tìm thấy hoặc hết danh sách.

à Thuật toán tìm kiếm thu hẹp danh sách tìm kiếm chỉ còn một nửa, gọi là tìm kiếm nhị phân.

- Các bước để An tìm khách hàng tên “Trúc” theo thuật toán tìm kiếm nhị phân:

+ Bước 1. Xét vị trí ở giữa của dãy, đó là vị trí số 5.

Chart

Description automatically generated

Bước 2. Xét vị trí ở giữa của nửa sau của đây là vị trí số 7

Diagram, timeline

Description automatically generated

Bước 3. Xét vị trí ở giữa của nửa sau còn lại của dãy, đó là vị trí số 8.

A picture containing text

Description automatically generated

Vì sau bước 3 đã tìm thấy tên khách hàng nên thuật toán kết thúc.

Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên

- Bước 1. Nếu vùng tìm kiếm không có phần tử nào thì kết luận không tìm thấy và thuật toán kết thúc.

- Bước 2. Xác định vị trí giữa của vùng tìm kiếm. Vị trí này chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa.

- Bước 3. Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận “giá trị cần tìm xuất hiện tại vị trí giữa” và kết thúc.

- Bước 4. Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn nửa trước của dãy. Ngược lại (nếu giá trị cần tìm lớn hơn giá trị của vị trí giữa) vùng tìm kiếm mới thu hẹp lại, chỉ còn nửa sau của dãy.

- Bước 5. Lặp lại từ Bước 1 đến Bước 4 cho đến khi tìm thấy giá trị cần tìm (Bước 3) hoặc tìm kiếm không còn phần tử nào (Bước 1).

Text

Description automatically generated

Lưu ý: “nửa trước” và “nửa sau” không gồm phần tử giữa.

* Câu hỏi/SGK tr.76

- Bước 1. Vị trí giữa vùng tìm kiếm là 5. So sánh “Hòa” và “Mai”. Vì H đừng trước M trong bảng chữ cái nên vùng tìm kiếm là nửa trước của dãy (từ vị trí 1 đến vị trí 4).

- Bước 2. Vị trí giữa vùng tìm kiếm là 2. So sánh “Hòa” và “Bình”. Vì H đứng sau B trong bảng chữ cái nên vùng tìm kiếm là nửa sau của dãy (từ vị trí 3 đến vị trí 4).

- Bước 3. Vị trí giữa của vùng tìm kiếm là 3. So sánh ta thấy giá trị ở vị trí giữa đúng là “Hòa” là giá trị cần tìm. Thuật toán kết thúc.

---------------- Còn tiếp ----------------

 
Soạn mới giáo án Tin học 7 KNTT bài 15: Thuật toán tìm kiếm nhị phân

MỘT VÀI THÔNG TIN

  • Giáo án gửi là giáo án bản word, dễ dàng chỉnh sửa theo yêu cầu của địa phương
  • Font chữ: Time New Roman, trình bày rõ ràng, khoa học.

PHÍ GIÁO ÁN:

  • Giáo án word: 250k/học kì - 300k/cả năm
  • Giáo án Powerpoint: 300k/học kì - 400k/cả năm
  • Trọn bộ word + PPT: 400k/học kì - 450k/cả năm

=> Lúc đặt nhận đủ giáo án ngay và luôn

CÁCH ĐẶT:

  • Bước 1: gửi phí vào tk: 10711017 - Chu Văn Trí - Ngân hàng ACB
  • Bước 2: Click vào đây để nhắn tin Zalo thông báo và nhận giáo án

Từ khóa tìm kiếm: giáo án tin học 7 KNTT mới, soạn giáo án tin học 7 mới kết nối bài Thuật toán tìm kiếm nhị phân, giáo án soạn mới tin học 7 kết nối

Đia chỉ: Tòa nhà TH Office, 90 Khuất Duy Tiến, Thanh Xuân, Hà Nội
Điện thoại hỗ trợ: Fidutech - click vào đây
Chúng tôi trên Yotube
Cùng hệ thống: baivan.net - Kenhgiaovien.com - tech12h.com

Chat hỗ trợ
Chat ngay