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
cá
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 đó.
