KHBD BÀI 13. THUẬT TOÁN TÌM KIẾM (Dạy bằng bảng đen hoặc trắng).pdf

Không thẻ bỏ qua các nhóm để nhận nhiều tài liệu hay 1. Ngữ văn THPT 2. Giáo viên tiếng anh THCS 3. Giáo viên lịch sử 4. Giáo viên hóa học 5. Giáo viên Toán THCS 6. Giáo viên tiểu học 7. Giáo viên ngữ văn THCS 8. Giáo viên tiếng anh tiểu học 9. Giáo viên vật lí CLB HSG Hà Nội xin giới thiệu tới thầy cô và các bạn Bộ Tài liệu tập huấn lớp 7 (Tất cả các môn) - Sách CTST. Đây là tài liệu hay và quý giúp các thầy cô tham khảo trong quá trình dạy học lớp 7. Hãy tải ngay Bộ Tài liệu tập huấn lớp 7 (Tất cả các môn) - Sách CTST. Baigiangxanh nơi luôn cập nhật các kiến thức mới nhất. Chúc các bạn thành công !!!!!!!Xem trọn bộ Bộ Tài liệu tập huấn lớp 7 (Tất cả các môn) - Sách CTST. Để tải trọn bộ chỉ với 50k hoặc 200K để sử dụng toàn bộ kho tài liệu, vui lòng liên hệ qua Zalo 0388202311 hoặc Fb: Hương Trần.

Spinning

Đang tải tài liệu...

Tiết PPCT: 30,31

Ngày soạn: 00/00/2023

Ngày dạy: 00/00/2023

GV: Phạm Duy Phượng Chi (0903719797)

Lớp dạy: 7ijk

Trường THPT Trần Cao Vân TP.HCM

KẾ HOẠCH BÀI DẠY MÔN TIN HỌC

CHỦ ĐỀ 5. GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH

BÀI 13. THUẬT TOÁN TÌM KIẾM

Thời gian thực hiện: 2 tiết

I. MỤC TIÊU:

1. Về kiến thức: Học xong bài này, em sẽ

– Giải thích được thuật toán tìm kiếm tuần tự, 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 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 hoạ.

– Nêu được ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn.

2. Về năng lực

a) Năng lực chung

Năng lực tự chủ và tự học: HS biết tự tìm hiểu, tự khám phá kiến thức.

Năng lực giao tiếp và hợp tác: HS biết cách trao đổi, thảo luận với nhau để thực.

Năng lực giải quyết vấn đề: học sinh biết cách vận dụng các các kiến thức đã học vào

thực tế, tìm tòi, phát hiện giải quyết các vấn đề trong cuộc sống.

b) Năng lực Tin học

NLc: Giải quyết vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông (tư duy

thuật toán).

+ Đọc sơ đồ khối, mô tả cách tìm một số trong dãy số đã cho.

+ Hiểu được hiệu quả của tìm kiếm nhị phân.

3. Phẩm chất:

* HS hình thành và phát triển phẩm chất chăm chỉ, trung thực và trách nhiệm:

– Chăm chỉ: miệt mài, chú ý lắng nghe, đọc, làm bài tập, vận dụng kiến thức vào thực

tiễn.

– Trung thực: Sẵn sàng chia sẻ sản phẩm của mình cho các bạn góp ý, đánh giá.

– Trách nhiệm: Có trách nhiệm khi thực hiện và báo cáo kết quả hoạt động nhóm.

* Có thái độ cởi mở, hợp tác khi làm việc nhóm.

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

1. Thiết bị dạy học

– Bảng đen/trắng

2. Học liệu

Giáo viên:

+ Kế hoạch bài dạy, SGK, SGV, SBT Tin học 7, Phiếu học tập cá nhân,

+ Giấy khổ to vẽ sơ đồ khối Hình 2 và 4 SGK.

+ 2 bộ số, mỗi bộ gồm 09 thẻ số ghi các số: 26, 14, 24, 18, 15, 21, 19, 25, 12

(đính lên bảng).

+ Nam châm (đính lên bảng) hoặc băng dính (dán mặt sau của thẻ số)

+ Giấy khổ lớn (HS hoạt động nhóm lập bảng mô phỏng thuật toán).

+ Danh sách lớp hoặc tổ có thông tin ngày sinh (in giấy A4).

Học sinh:

+ SGK, SBT Tin học 7.

+ Dụng cụ học tập theo yêu cầu giáo viên: Mỗi học sinh chuẩn bị 20 thẻ (hoặc

20 mảnh giấy) kích thước 10cm x 15cm để ghi số (ở hoạt động Khám phá), tên tỉnh (ở

hoạt động Luyện tập).

+ Mỗi nhóm 1 bộ số, mỗi bộ gồm 09 thẻ số ghi các số: 26, 14, 24, 18, 15, 21, 19,

25, 12

+ Đọc bài trước theo sự hướng dẫn của GV.

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

KHỞI ĐỘNG (10 phút)

a) Mục tiêu: Tìm hiểu, thảo luận về thuật toán tìm kiếm tuần tự, tạo tâm thế hứng thú cho

học sinh và từng bước làm quen bài học.

b) Nội dung: Đề xuất cách tìm một số bất kì có trong dãy số ghi trên các thẻ đặt úp và thực

hiện tìm kiếm trong dãy thẻ ghim trên bảng theo cách đã đề xuất.

c) Sản phẩm:

+ Nêu được cách tìm một số bằng cách lật lần lượt từng thẻ số theo thứ tự.

+ Thực hiện, mô tả được các thao tác thực hiện cách tìm này trên một dãy số cụ thể.

+ Câu trả lời trên phiếu học tập cá nhân.

+ Tích cực, hứng thú với bài học mới.

d) Tổ chức thực hiện: Giao nhiệm vụ, HS báo cáo, đánh giá và nhận xét.

+ GV chia lớp (xx HS) thành n nhóm (mỗi nhóm a HS)

+ GV phát phiếu học tập cá nhân và giao nhiệm vụ cho các nhóm.

Nội dung

GV chuyển giao nhiệm vụ/

nhận định, kết luận

HS thảo luận/ thực hiện

nhiệm vụ và báo cáo

Tìm 1 số trong

dãy các thẻ được

ghi số ở mặt úp.

GV giao nhiệm vụ cho HS: sử dụng

SGK, làm việc theo nhóm nhỏ

+ Nhiệm vụ 1. Đọc, thảo luận, thực

hiện thao tác (4 phút)

* Đọc kênh hình và kênh chữ, sau đó

trao đổi với bạn, nêu cách tìm (

(HS đọc, nói, làm, ghi chép

và giao tiếp)

+ HS đọc SGK.

+ Thảo luận trong nhóm nhỏ.

+ Đại diện nhóm đề xuất các

cách thực hiện:

tưởng) một số bất kì có trong dãy số

ghi trên các thẻ Hình 1 (trang 71)

* Sử dụng bộ số có sẵn của nhóm, sắp

theo mẫu như Hình 1 trên mặt bàn,

thực hiện thao tác tìm số (theo 2 cách

đã đề xuất) để kiểm chứng.

* GV chốt ý, nhận xét, kết luận: thông

thường có 2 cách tìm số trong dãy số

cho trước, đánh giá nhiệm vụ số 1.

+ Nhiệm vụ 2. Quan sát thao tác và

ghi chép (4 phút)

* GV ghim thẻ số lên bảng và đánh số

thứ tự (như Hình 1 trong SGK), gọi

HS lên bảng thực hiện lật thẻ tìm một

số, sau đó GV đảo thứ tự các thẻ số,

yêu cầu HS tìm một số khác.

+ HS thứ 1 sẽ thực hiện thao tác lật thẻ

theo cách 1

+ HS thứ 2 sẽ thực hiện thao tác lật thẻ

theo cách 2

* GV gợi ý để HS nêu thao tác lật thẻ

tìm số như:

- Lật thẻ nào?

- Kiểm tra số trên thẻ có đúng

là số cần tìm không?

- Nếu đúng thì làm gì?

- Nếu sai thì làm gì?

- Các thẻ số đã được lật hết

chưa?

- Nếu đã hết thì làm gì?

- Nếu chưa hết thì làm gì?

* GV chốt ý nhận xét, đánh giá nhiệm

vụ số 2.

GV nhận định, kết luận (1 phút)

* GV cho HS nhận xét câu trả lời của

nhóm bạn, yêu cầu HS nhóm khác

đóng góp ý kiến.

* GV nhận xét và chốt ý nội dung câu

trả lời: Ở cách 2, mỗi lần lật một thẻ

số rồi phải úp lại mới được lật thẻ tiếp

theo. Nếu có rất nhiều thẻ số, thẻ đã

lật úp lại có thể được lật lại, điều này

sẽ dẫn đến cần thực hiện tìm theo cách

1 để dễ thực hiện, dễ nhớ thẻ nào đã

lật, thẻ nào chưa lật.

* Cách 1. Lật theo thứ tự cho

đến khi tìm thấy hoặc đã lật

hết các thẻ mà không tìm thấy.

* Cách 2. Lật ngẫu nhiên cho

đến khi tìm thấy hoặc đã lật

hết các thẻ mà không tìm thấy.

* HS nhận xét câu trả lời của

nhóm bạn.

+ Ghi phiếu học tập cá nhân-

Phiếu giao nhiệm vụ 1.

(HS quan sát thao tác, đối

chiếu và ghi chép)

+ 2 HS lên bảng thực hiện tìm

một số, cả lớp quan sát.

* HS nhận xét câu trả lời của

nhóm bạn.

+ Ghi phiếu học tập cá nhân -

Phiếu giao nhiệm vụ 2.

(HS lắng nghe, củng cố kiến

thức thu nhận ở Nhiệm vụ 1

và 2)

* GV nhận xét và công bố kết quả

hoạt động của các nhóm.

GV chuyển ý (1 phút): Tìm kiếm là công việc con người thường xuyên thực hiện trong cuộc

sống hằng ngày. Con người muốn thực hiện công việc tìm kiếm nhanh chóng và hiệu quả

hơn. Để giải quyết vấn đề đặt ra chúng ta sẽ cùng tìm hiểu phần khám phá về thuật toán tìm

kiếm.

Ở phần khởi động, chúng ta đã thực hiện cách lật từng thẻ số theo thứ tự để tìm một số trong

dãy thẻ số đã cho theo cách 1, đó là cách tìm kiếm tuần tự hay còn được gọi là thuật toán tìm

kiếm tuần tự.

HÌNH THÀNH KIẾN THỨC (35 phút)

1. Thuật toán tìm kiếm tuần tự (17 phút)

a) Mục tiêu: Giải thích được thuật toán tìm kiếm tuần tự; biểu diễn và mô phỏng được hoạt

động của thuật toán tìm kiếm tuần tự trên bộ dữ liệu vào có kích thước nhỏ.

b) Nội dung: Một số ví dụ về bài toán tìm kiếm, sơ đồ khối mô tả thuật toán tìm kiếm tuần

tự một số trong dãy.

c) Sản phẩm:

+ Nêu được một số ví dụ về bài toán tìm kiếm trong thực tiễn cuộc sống.

+ Giải thích được thuật toán thông qua sơ đồ khối.

+ Điền đúng các bước mô phỏng được hoạt động của thuật toán như Bảng 1.

+ Câu trả lời trên phiếu học tập cá nhân.

+ Tích cực, hứng thú với bài học mới.

d) Tổ chức thực hiện: Giao nhiệm vụ, HS báo cáo, đánh giá và nhận xét.

+ GV tiếp tục giao nhiệm vụ cho các nhóm.

Nội dung

GV chuyển giao nhiệm vụ/

nhận định, kết luận

HS thảo luận/ thực hiện

nhiệm vụ và báo cáo

Tìm hiểu thuật

toán tìm kiếm tuần

tự

GV chuyển giao nhiệm vụ cho HS:

sử dụng SGK, làm việc theo nhóm

nhỏ

+ Nhiệm vụ 1. Đọc, thảo luận, nêu

ví dụ và trình bày (3 phút)

* HS đọc kênh chữ trong SGK kết

hợp với những kiến thức đã có từ

thực tiễn, nêu ví dụ về bài toán tìm

kiếm.

* HS mô tả đầu vào và đầu ra của

bài toán tìm kiếm ở hoạt động khởi

động.

(HS đọc, quan sát, nói, ghi

chép và giao tiếp)

+ Thảo luận trong nhóm nhỏ.

+ Đại diện nhóm trình bày:

Ví dụ:

- Tìm tên của HS trong danh

sách kết quả của kì thi;

- Tìm 1 từ trong từ điển;

- Tìm cuốn sách Tin học 7

trong thư viện,...

Mô tả bài toán tìm 1 số trong

dãy số cho trước ghi trên các

thẻ ở phần khởi động:

* Đầu vào: Dãy số (được ghi

trên các thẻ) và số cần tìm.

* GV chốt ý nhận xét, đánh giá

nhiệm vụ số 1.

+ Nhiệm vụ 2. Đọc, thảo luận và

trình bày (4 phút)

* HS đọc, quan sát kênh chữ trong

sơ đồ khối ở Hình 2 (Trang 72) SGK

trình bày và giải thích các bước của

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

* GV treo sơ đồ khối Hình 2 (được

vẽ trên giấy khổ to) lên bảng,

* GV gọi 1 HS lên bảng nhìn vào sơ

đồ khối, trình bày thuật toán.

* GV chốt ý nhận xét, đánh giá

nhiệm vụ số 2.

HOẠT ĐỘNG LÀM

+ Nhiệm vụ 3. Điền thông tin vào

PHIẾU HỌC TẬP 1 (4-5 phút)

* GV hướng dẫn, giải thích các bước

thực hiện thuật toán và ghi thông tin

vào dòng 1, 2 trong Bảng 1 trong

SGK.

* HS điền thông tin vào PHIẾU

HỌC TẬP 1

* GV chốt ý nhận xét, đánh giá

nhiệm vụ số 3.

Lưu ý: nếu HS làm sai, GV quay lại

sơ đồ khối giải thích các bước thực

hiện, nhấn mạnh bước kết thúc của

thuật toán.

+ Nhiệm vụ 4. Chọn phương án

đúng (1-2 phút)

* HS sử dụng SGK, đọc câu hỏi

* HS phát biểu lựa chọn phương án

đúng của câu hỏi

* GV mời HS nhận xét câu trả lời

của các bạn và GV chốt ý nhận xét,

đánh giá nhiệm vụ số 4.

GHI NHỚ (2 phút)

* Đầu ra: Thông báo vị trí tìm

thấy hoặc thông báo không tìm

thấy số cần tìm.

* HS nhận xét câu trả lời của

nhóm bạn.

+ Ghi phiếu học tập cá nhân -

Phiếu giao nhiệm vụ 1.

(HS đọc, quan sát, nói, ghi

chép và giao tiếp)

+ Thảo luận trong nhóm nhỏ.

+ Đại diện nhóm trình bày sơ

đồ khối mô tả thuật toán tìm

kiếm tuần tự để tìm một số

trong dãy thẻ đã cho ở Hình 1

+ Trình bày được thuật toán

thực hiện lặp đi lặp lại việc

duyệt từng thẻ số, vòng lặp sẽ

kết thúc khi thấy số cần tìm

hoặc đã duyệt hết các thẻ số.

* HS nhận xét câu trả lời của

nhóm bạn.

+ Ghi phiếu học tập cá nhân -

Phiếu giao nhiệm vụ 2.

(HS quan sát, lắng nghe

hướng dẫn của GV, làm)

+ HS lắng nghe, quan sát GV

hướng dẫn, trao đổi, làm việc

nhóm đôi.

* HS nhận xét câu trả lời của

nhóm bạn.

+ Điền PHIẾU HỌC TẬP 1

trong phiếu học tập cá nhân -

Phiếu giao nhiệm vụ 3.

+ HS nêu nhận xét: Khi đã tìm

thấy thì kết thúc.

+ Đếm được là có 6 lần lật thẻ

mới tìm được số 21 ở vị trí số

6

(HS làm)

+ HS thực hiện nhiệm vụ số 4:

làm việc cá nhân và trình bày

câu trả lời.

* HS nhận xét câu trả lời của

nhóm bạn.

+ Ghi phiếu học tập cá nhân -

Phiếu giao nhiệm vụ 4

* GV yêu cầu HS đọc thầm nội dung

trong hộp ghi nhớ.

* Gọi HS đọc trước lớp.

GV nhận định, kết luận (2 phút)

* GV yêu cầu HS nhận xét, góp ý

câu trả lời của nhóm bạn.

* GV chốt ý nội dung:

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

hiện so sánh lần lượt từ phần tử đầu

tiên của dãy với giá trị cần tìm, việc

tìm kiếm kết thúc khi tìm thấy hoặc

đã duyệt hết các phần tử trong dãy.

Số lần tìm thấy 1 số cần tìm trong

dãy số cho trước khi tìm kiếm tuần

tự thường là ít hơn so với cách thực

hiện tìm kiếm ngẫu nhiên.

* GV nhận xét và công bố kết quả

hoạt động của các nhóm.

+ HS điền vào chỗ (….) Ghi

nhớ

trong

phiếu

học

tập

nhân.

(HS lắng nghe, củng cố kiến

thức về thuật toán tìm kiếm

tuần tự)

GV nêu vấn đề để chuyển ý:

- Ví dụ như trong bảng xếp loại HKI, cột ĐTBHKI được sắp xếp thì việc tìm kết quả cho

một học sinh nào đó là dễ dàng và nhanh chóng hơn.

- Vậy, nếu dãy số đã cho ở trên được sắp xếp thì việc tìm kiếm số 21 sẽ được thực hiện như

thế nào? Có nhanh hơn không?

- Có thuật toán tìm kiếm nào khác (với thuật toán tìm kiếm tuần tự) để tìm một số trong dãy

số đã sắp xếp không? Thuật toán đó có hiệu quả và nhanh chóng hơn không?

Chúng ta cùng nhau tìm hiểu thuật toán tìm kiếm nhị phân là một thuật toán cơ bản trong

khoa học máy tính.

2. Thuật toán tìm kiếm nhị phân (18 phút)

a) Mục tiêu:

– Giải thích thuật toán tìm kiếm nhị phân.

– Biểu diễn và mô phỏng 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 mối liên quan giữa sắp xếp và tìm kiếm, nêu được ví dụ minh hoạ.

– Nêu ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn.

b) Nội dung:

– Sơ đồ khối mô tả thuật toán tìm kiếm nhị phân để tìm một số trong dãy số (được

ghi trên các thẻ) đã được sắp xếp theo thứ tự không giảm.

– Mô phỏng thuật toán trên bộ dữ liệu nhỏ.

– Ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn.

c) Sản phẩm:

– Giải thích được trình tự thực hiện các bước của thuật toán tìm kiếm nhị phân thông

qua sơ đồ khối.

– Mô phỏng được thuật toán trên bộ dữ liệu nhỏ.

– Nêu được lợi ích dãy số đã sắp xếp giúp dễ dàng tìm kiếm hơn.

– Nêu được việc chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm

kiếm.

– Câu trả lời của HS trên phiếu học tập.

– Tích cực, hứng thú với bài học mới.

d) Tổ chức thực hiện: Giao nhiệm vụ, HS báo cáo, đánh giá và nhận xét.

+ GV tiếp tục giao nhiệm vụ cho các nhóm.

Nội dung

GV chuyển giao nhiệm vụ/

nhận định, kết luận

HS thảo luận/ thực hiện

nhiệm vụ và báo cáo

Tìm hiểu thuật

toán tìm kiếm nhị

phân

GV chuyển giao nhiệm vụ cho HS:

+ Nhiệm vụ 1. HS so sánh dãy số ở

Hình 3 trong SGK với dãy số ở Bài

tập 1 của hoạt động Làm ở mục 1 (2

phút)

Dãy số Hình 1: 26, 14, 24, 18, 15, 21,

19, 25, 12

Dãy số Hình 3: 12, 14, 15, 18, 19, 21,

24, 25, 26

* GV ví dụ về dãy không giảm:

Dãy không giảm (tức là số hạng

trước không lớn hơn số hạng sau)

1, 2, 4, 5, 6, 8, 12, 15

* GV chốt ý nhận xét, đánh giá

nhiệm vụ số 1.

+ Nhiệm vụ 2. (5 phút)

* HS quan sát kênh chữ ở Hình 4

trong SGK tìm hiểu thuật toán tìm

kiếm nhị phân.

* HS thực hiện thuật toán qua các

Lần lặp 1, 2, 3 với bộ số có sẵn của

nhóm, sắp theo mẫu như Hình 3 trên

mặt bàn.

Thực hiện thao tác tìm số 21 theo

yêu cầu của GV

(HS đọc, nói, ghi chép và

giao tiếp)

+ Thảo luận trong nhóm nhỏ.

+ Đại diện nhóm trình bày.

+ HS nêu được nhận xét: dãy

số ở Hình 3 trong SGK đã được

sắp

xếp

theo

thứ

tự

không

giảm.

* HS nhận xét câu trả lời của

nhóm bạn.

+ Ghi phiếu học tập cá nhân -

Phiếu giao nhiệm vụ 1

(HS đọc, quan sát, nói, ghi

chép và giao tiếp)

+ Thảo luận trong nhóm nhỏ.

+ Đại diện nhóm trình bày: khi

một dãy thẻ số được sắp xếp

theo thứ tự không giảm, có thể

thực hiện tìm kiếm một số bất

kỳ theo thuật toán tìm kiếm nhị

phân.

+ HS mô phỏng thuật toán tìm

kiếm nhị phân

* Lần lặp 1: Lật thẻ số

ở giữa của dãy (thẻ thứ 5). So

sánh 21 > 19 nên chỉ cần tìm ở

nửa sau của dãy thẻ (gồm các

thẻ thứ 6, 7, 8, 9)

* Lần lặp 2: Lật thẻ số

ở giữa của nửa sau (thẻ thứ 7).

So sánh 21 < 24 nên chỉ cần tìm

ở nửa trước của dãy thẻ (là thẻ

thứ 6).

* GV ghim thẻ số lên bảng và đánh

số thứ tự (như Hình 3 trong SGK),

gọi HS lên bảng thực hiện lật thẻ tìm

một số, sau đó yêu cầu HS tìm một

số không có mặt trong dãy.

* Phát biểu mô tả hoạt động của

thuật toán

* GV giải thích cho HS về phần

nguyên, dãy rỗng.

* GV nêu ví dụ về dãy rỗng, cách

tìm thẻ ở giữa. Thẻ số ở giữa dãy có

số thứ tự là phần nguyên của phép

chia:

(Số lượng thẻ của dãy+1):2

* GV chốt ý nhận xét, đánh giá

nhiệm vụ số 2.

ở Hình 4, thuật toán tìm kiếm nhị

phân thực hiện lặp đi lặp lại việc

chia đôi dãy thẻ số. Vòng lặp sẽ kết

thúc khi tìm thấy số cần tìm hoặc

dãy không còn thẻ số nào nữa.

+ Nhiệm vụ 3. Quan sát thao tác

và ghi chép (3 phút)

+ GV ghim thẻ số (đã được sắp xếp

theo thứ tự không giảm) lên bảng và

đánh số thứ tự như Hình 3 trong

SGK (không ghi giá trị số trên thẻ

lên bảng). Yêu cầu HS đại diện lên

bảng thực hiện thao tác tìm số 21

theo các bước mô phỏng

* GV chốt ý nhận xét, đánh giá

nhiệm vụ số 3.

+ Nhiệm vụ 4. (4 phút)

+ HS mô tả thuật toán tìm kiếm nhị

phân bằng lời, so sánh số lần lặp của

thuật toán tìm kiếm nhị phân và

thuật toán tìm kiểm tuần tự? điều

kiện áp dụng thuật toán tìm kiếm nhị

phân.

GHI NHỚ

* Lần lặp 3: Lật thẻ số

ở giữa của nửa trước. So sánh

giá trị ghi ở thẻ 6 là 21 bằng với

số cần tìm nên kết quả là tìm

thấy số 21 trong dãy; kết thúc

tìm kiếm.

+ 2 HS lên bảng thực hiện tìm

một số, cả lớp quan sát.

* HS nhận xét câu trả lời của

nhóm bạn.

+ HS quan sát kênh chữ trong

sơ đồ khối ở Hình 4 (Trang 73)

SGK trình bày và giải thích các

bước của thuật toán tìm kiếm

nhị phân, nêu được:

Lặp đi lặp lại việc chia đôi

dãy số,

Vòng lặp sẽ kết thúc khi tìm

thấy số cần tìm hoặc dãy không

còn thẻ số nào nữa.

+ Ghi phiếu học tập cá nhân -

Phiếu giao nhiệm vụ 2

(HS làm)

+ HS thực hiện thao tác lật thẻ

+ Đếm được là có 3 lần lật thẻ

thì tìm được số 21 ở vị trí số 6

+ Ghi phiếu học tập cá nhân -

Phiếu giao nhiệm vụ 3

+ HS thực hiện nhiệm vụ số 4:

làm việc cá nhân và trình bày

câu trả lời.

+ HS phải nêu được các ý:

Dãy đã sắp xếp

Thu hẹp phạm vi tìm kiếm

Tăng hiệu quả tìm kiếm.

Số lần lặp ít hơn

* GV yêu cầu HS đọc thầm nội dung

trong hộp ghi nhớ.

* Gọi HS đọc trước lớp

* GV chốt ý nhận xét, đánh giá

nhiệm vụ số 4.

HOẠT ĐỘNG LÀM (2 phút)

GV tổ chức hoạt động,

Em và bạn hãy thực hiện trò chơi mô

phỏng thuật toán tìm kiếm nhị phân

theo hướng dẫn sau:

a) Chuẩn bị 10 thẻ, mỗi thẻ ghi một

số khác nhau. Sắp xếp các thẻ số

thành một dãy trên mặt bàn theo thứ

tự giá trị tăng dần của số ghi trên thẻ.

Đặp úp mặt ghi số để không nhìn

thấy số ghi trên các thẻ.

b) Em đề nghị bạn thực hiện thuật

toán tìm kiếm nhị phân để tìm một

số do em đưa ra.

c) Hoán đổi vai trò, em thực hiện tìm

kiếm theo đề nghị của bạn.

* HS nhận xét câu trả lời của

nhóm bạn.

+ Ghi phiếu học tập cá nhân -

Phiếu giao nhiệm vụ 4

HS thực hiện theo yêu cầu.

GV nhận định, kết luận (2 phút)

Thuật toán tìm kiếm nhị phân:

– Áp dụng với dãy giá trị đã được sắp xếp.

– Ở mỗi lần lặp, thực hiện:

+ Bước 1. So sánh giá trị cần tìm với giá trị của phần tử giữa dãy đang xét.

+ Bước 2. Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc.

+ Bước 3. Nếu nhỏ hơn thì xét dãy ở nửa trước, nếu lớn hơn thì xét dãy ở nửa sau.

+ Bước 4. Nếu dãy rỗng thì thông báo không tìm thấy và kết thúc tìm kiếm, không thì

quay lại Bước 1.

Điều kiện áp dụng thuật toán tìm kiếm nhị phân là dãy số đã được sắp xếp theo thứ tự

nhất định (không giảm hoặc không tăng).

Khi dãy số đã được sắp xếp việc tìm kiếm số theo thuật toán tìm kiếm nhị phân sẽ được

nhanh hơn, tiết kiệm thời gian hơn.

Thuật toán tìm kiếm nhị phân thực hiện chia bài toán tìm kiếm ban đầu thành những bài

toán tìm kiếm nhỏ hơn, bởi vì sau mỗi lần lặp, phạm vi của bài toán chỉ còn bằng khoảng

một nửa so với bài toán trước đó.

Việc chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.

Hiểu được ý nghĩa của nhị phân: sau mỗi lần lặp, phạm vi của bài toán chỉ còn bằng

khoảng một nửa so với bài toán trước đó.

LUYỆN TẬP (20 phút)

a) Mục tiêu: Củng cố, khắc sâu kiến thức đã học

– Nắm được trình tự các bước của thuật toán tìm kiếm tuần tự.

– Nắm được trình tự các bước của thuật toán tìm kiếm nhị phân

b) Nội dung: HS làm việc cá nhân hoặc làm việc nhóm, phát biểu trước lớp để hoàn thành

các câu hỏi, bài tập trong SGK.

c) Sản phẩm: HS hoàn thiện các bài tập

d) Tổ chức thực hiện: Giao nhiệm vụ, HS báo cáo, đánh giá và nhận xét.

– GV tiếp tục giao nhiệm vụ cho các nhóm

Nội dung

GV chuyển giao nhiệm vụ/

nhận định, kết luận

HS thảo luận/ thực hiện

nhiệm vụ và báo cáo

Bài tập 1. Hãy sử dụng thuật

toán tìm kiếm tuần tự để tìm

trong lớp em có bạn cùng

tháng sinh với em hay không.

Có thể sử dụng danh sách lớp

có ghi thông tin ngày sinh

hoặc hỏi trực tiếp. Lập Bảng

2 vào vở và ghi kết quả thực

hiện (dòng 1 là ví dụ minh

họa).

GV chuyển giao nhiệm vụ

cho HS:

Nhiệm vụ 1 (5 phút): HS

hoàn thành bài tập 1 thực

hiện yêu cầu sau:

– Nếu có DS thông tin học

sinh (đã in), GV phát danh

sách lớp (hoặc tổ) cho các

nhóm HS, yêu cầu HS tìm lần

lượt từng bạn và ghi thông tin

vào bảng 2.

– Nếu không in danh sách ra

giấy thì GV có thể cho HS đi

hỏi các bạn ở một tổ khác,

mỗi lần chỉ hỏi một bạn và

ghi thông tin vào bảng.

*

GV

nhận

xét,

đánh

giá

nhiệm vụ số 1.

+ HS điền thông tin ở bảng

2,

+ Ghi phiếu học tập cá nhân -

Phiếu giao nhiệm vụ 1

Bài tập 2. Bảng 3 là danh

sách hai số đầu biển số xe của

một số tỉnh (tên tỉnh đã được

sắp

xếp

theo

thứ

tự

trong

bảng chữ cái).

a) Áp dụng thuật toán tìm

kiếm tuần tự để tìm ra tỉnh có

hai số đầu của biển số xe là

Nhiệm vụ 2 (15 phút): HS

hoàn thành bài tập 2 thực

hiện yêu cầu sau a, b, c, d và

ghi kết quả vào Phiếu học tập

2.

GV tổ chức hoạt động luyện

tập, HS thực hiện đưa ra được

kết quả:

a) Thực hiện 8 lần lặp.

+ HS hoàn thành thông tin ở

trong bảng 3, và điền vào chỗ

(……….)

+ Thảo luận, đại diện nhóm

trình bày câu trả lời.

25. Cho biết em đã thực hiện

bao nhiêu lần lặp?

b) Áp dụng thuật toán tìm

kiếm nhị phân để tìm hai số

đầu tiên của biển số xe của

tỉnh Lai Châu. Cho biết em

đã thực hiện bao nhiêu lần

lặp?

c) Số lần lặp em thực hện ở

câu a ít hơn hay ở câu b ít

hơn? Tại sao?

d) Có thể áp dụng thuật toán

tìm kiếm nhị phân để tìm ra

tỉnh khi biết hai số đầu của

biển số xe của tỉnh đó hay

không? Tại sao?

b) Lần lặp 1: Có 10 tỉnh đã

được sắp xếp theo thứ tự của

tên trong bảng chữ cái. Mở

thẻ ở giữa là Điện Biên. Thấy

"Đ" < "L" nên chỉ cần tìm ở

nửa sau của dãy.

Lần lặp 2: Xem kết quả ở

giữa

của

nửa

sau,

là

"Lai

Châu" bằng với kết quả cần

tìm. Đối chiếu hai số đầu biển

số xe của Lai Châu là 25.

Em đã thực hiện hai lần lặp.

c) Số lần lặp ở câu b ít hơn.

Do dãy đã được sắp xếp nên

thuật toán tìm kiếm nhị phân

thu hẹp được phạm vi tìm

kiếm chỉ còn tối đa là một

nửa sau mỗi lần lặp.

d) Không. Vì dãy số chưa

được sắp xếp theo trình tự

không tăng hoặc không giảm.

* GV chốt ý nhận xét, đánh

giá nhiệm vụ 2.

b

)

Áp dụng công thức tính

thứ tự tỉnh đứng ở giữa

= (số lượng tên các tỉnh +1): 2

– Ta tìm được tỉnh đứng ở

giữa có số thứ tự là 5 (tỉnh

Điện Biên).

– So sánh “Lai Châu” đứng

sau tỉnh “Điện Biên”, chỉ cần

tìm ở nửa sau của dãy tên các

tỉnh (ở các thứ tự 6, 7, 8, 9,

10)

– Tỉnh mới đứng ở giữa của

nửa sau dãy tên các tỉnh có

thứ tự là 8 (tỉnh Lai Châu). So

sánh “Lai Châu” với tên tỉnh

cần tìm ta thấy trùng nhau,

kết thúc thuật toán.

– Số lần lặp là: 2

c

)

Số lần lặp em thực hiện ở

câu b ít hơn. Ở câu b, sử dụng

thuật toán tìm kiếm nhị phân

đã chia bài toán thành những

bài toán nhỏ hơn giúp tăng

hiệu quả tìm kiếm nhanh hơn

d

)

Không thể áp dụng thuật

toán tìm kiếm nhị phân để

tìm ra tỉnh khi biết hai số đầu

của biển số xe của tỉnh đó vì

hai số đầu biển số xe của các

tỉnh chưa sắp xếp theo thứ tự

nhất định.

+ Ghi phiếu học tập cá nhân -

Phiếu giao nhiệm vụ 2

VẬN DỤNG (10 phút)

a) Mục tiêu: Vận dụng kiến thức đã học vào thực tiễn cuộc sống.

b) Nội dung: GV đưa ra bài tập, yêu cầu HS thảo luận nhóm hoàn thành.

c) Sản phẩm: Kết quả thực hiện của HS.

d) Tổ chức thực hiện: Giao nhiệm vụ, HS báo cáo, đánh giá và nhận xét.

– GV tiếp tục giao nhiệm vụ cho các nhóm.

Nội dung

GV chuyển giao nhiệm vụ/

nhận định, kết luận

HS thảo luận/ thực hiện

nhiệm vụ và báo cáo

Bài tập 1. Em tìm một từ

tiếng Anh trong cuốn từ điển

theo cách nào? Tại sao em

dùng cách đó?

GV chuyển giao nhiệm vụ

cho HS:

+ HS thảo luận và trình bày

câu trả lời:

Em sẽ tra theo thứ tự của lần

lượt từng chữ cái trong từ đó.

Nhiệm vụ 1 (5 phút): HS trả

lời câu hỏi 1 ở mục Vận dụng

vào Phiếu giao nhiệm vụ và

giải thích lí do HS thực hiện

tìm từ trong từ điển?

(GV hướng dẫn để HS biết từ

trong từ điển được sắp xếp

theo thứ tự a, b, c. Do vậy, có

thể áp dụng tìm kiếm nhị

phân

để

tìm

kiếm

nhanh

hơn.)

* GV chốt ý nhận xét, đánh

giá nhiệm vụ số 1.

Em dùng cách này vì tiện và

nhanh

chóng

tìm

được

từ

mình muốn tra.

+

HS

trao

đổi,

thảo

luận

nhóm, đại diện nhóm trình

bày.

+ HS khác nhận xét.

+ Ghi phiếu học tập cá nhân -

Phiếu giao nhiệm vụ 1

Bài

tập

2.

Hãy

vận

dụng

thuật toán tìm kiếm nhị phân

để xác định một bạn trong lớp

được sinh vào ngày nào trong

tháng với không quá 5 câu

hỏi

trắc

nghiệm

Đúng/Sai.

Tương tự, để xác định một

bạn sinh vào tháng nào trong

năm thì em cần dùng nhiều

nhất

bao

nhiêu

câu

hỏi

Đúng/Sai?

Nhiệm vụ 2 (5 phút):

GV gợi ý: ngày sinh là tìm 1

số trong dãy số đã được sắp

xếp từ 1 đến 31; xác định

tháng sinh là tìm một số trong

dãy số đã được sắp xếp từ 1

đến 12. Do vậy, có thể áp

dụng thuật toán tìm kiếm nhị

phân để xác định ngày sinh,

tháng sinh của một bạn.

* GV chốt ý nhận xét, đánh

giá nhiệm vụ số 2.

+ HS thảo luận và trình bày

câu trả lời.

+ HS khác nhận xét.

+ Ghi phiếu học tập cá nhân -

Phiếu giao nhiệm vụ 2

TÓM TẮT NỘI DUNG BÀI HỌC (15 phút)

Hai thuật toán tìm kiếm thường sử dụng:

1. Thuật toán tìm kiếm tuần tự thực hiện so sánh lần lượt từ phần tử đầu tiên của

dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần

tử trong dãy.

2. Thuật toán tìm kiếm nhị phân:

– Áp dụng với dãy giá trị đã được sắp xếp theo thứ tự nhất định (không giảm hoặc

không tăng).

– Khi dãy số đã được sắp xếp việc tìm kiếm sẽ được nhanh hơn, tiết kiệm thời gian

hơn.

– Việc chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.

– Sau mỗi lần lặp, phạm vi của bài toán chỉ còn bằng khoảng một nửa so với bài toán

trước đó.