Phiếu học tập cá nhân bài 13. THUẬT TOÁN TÌM KIẾM.pdf

PHIẾU HỌC TẬP CÁ NHÂN

CHỦ ĐỀ 5. GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH

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

Họ và tên học sinh: .................................................................................... Lớp: 7 ...................

Nhóm: .......................................................................................................................................

GV hướng dẫn: Phạm Duy Phượng Chi (0903719797)

Trường THPT Trần Cao Vân TP.HCM

HOẠT ĐỘNG 1- KHỞI ĐỘNG

(

Thời gian thực hiện 10 phút) (1 điểm)

1. Phiếu giao nhiệm vụ 1 (4 phút) (0.5 điểm)

Đề xuất 2 cách tìm chính:

– Cách 1: Lật lần lượt từng thẻ số theo thứ tự ......................................................................

................................................................................................................................................

– Cách 2: Lật từng thẻ số một cách ngẫu nhiên ....................................................................

................................................................................................................................................

Thực hiện thao tác:

Số cần tìm: ………

Thứ tự

Dãy thẻ số

Số lần lật tìm ra số cần tìm theo cách 1

(Lật lần lượt từng thẻ số theo thứ tự)

………… lần

Số lần lật tìm ra số cần tìm theo cách 2

(Lật từng thẻ số một cách ngẫu nhiên)

………… lần

Ghi lại các bước lật từng thẻ số một cách ngẫu nhiên để tìm thấy số đã cho:

................................................................................................................................................

Nhận xét về số lần lật thẻ số theo cách 1 và 2 ..........................................................................

................................................................................................................................................

2. Phiếu giao nhiệm vụ 2 (4 phút) (0.5 điểm)

Số cần tìm: 21

Thứ tự

Dãy thẻ số

(Lần 1)

Số lần lật tìm ra số cần tìm theo cách 1

(Lật lần lượt từng thẻ số theo thứ tự)

………… lần

Số lần lật tìm ra số cần tìm theo cách 2

(Lật từng thẻ số một cách ngẫu nhiên)

………… lần

Dãy thẻ số

(Lần 2)

Số lần lật tìm ra số cần tìm theo cách 1

(Lật lần lượt từng thẻ số theo thứ tự)

………… lần

Số lần lật tìm ra số cần tìm theo cách 2

(Lật từng thẻ số một cách ngẫu nhiên)

………… lần

Ghi lại các bước lật từng thẻ số một cách ngẫu nhiên để tìm thấy số đã cho:

................................................................................................................................................

Nhận xét về số lần lật thẻ số theo cách 1 và 2 .......................................................................

................................................................................................................................................

II.

HOẠT ĐỘNG 2- KHÁM PHÁ

(Thời gian thực hiện 35 phút) (6điểm)

Tìm hiểu thuật toán tìm kiếm tuần tự (15-17 phút) (3điểm)

1. Phiếu giao nhiệm vụ 1 (3 phút) (0.5 điểm)

Ví dụ về tìm kiếm trong thực tiễn:

................................................................................................................................................

Bài toán tìm số trong dãy số cho trước ghi trên các thẻ:

* Đầu vào: ................................................................................................................................

* Đầu ra: ..................................................................................................................................

2. Phiếu giao nhiệm vụ 2 (4 phút) (0.5 điểm)

Điền vào chỗ (…..) trên sơ đồ khối (Hình 2)

Hình 2. 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ẻ số ở Hình 1

Sai

Đúng

…………………….

………………………

…………………….

………………………

Lật thẻ ………………

Bắt đầu

Đầu vào: Dãy thẻ số, số cần tìm

Kết thúc

Lật thẻ ………………

Kiểm tra: Số trên thẻ có

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

Kiểm tra: tất cả các thẻ số

đã được lật?

Đúng

3. Phiếu giao nhiệm vụ 3 (4-5 phút) (1.0 điểm)

Điền thông tin vào phiếu học tập 1.

PHIẾU HỌC TẬP 1

Tìm số 21 trong dãy số: 26, 14, 24, 18, 15, 21, 19, 25, 12

bằng thuật toán tìm kiếm tuần tự

Lần lặp

Số ghi trên thẻ

Đúng số cần tìm?

Đã hết thẻ số?

Sai

Ghi ra số lần lật thẻ:………………..

4. Phiếu giao nhiệm vụ 4 (1-2 phút) (0.5 điểm)

Lựa chọn phương án đúng. (Khoanh tròn vào A, B, C hoặc D cho phương án được chọn)

Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự, ta thực hiện:

A. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.

B. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.

C. Sắp xếp dãy số theo thứ tự tăng dần.

D. So sánh số cần tìm với số ở giữa dãy số.

5. Ghi nhớ: (2 phút) (0.5 điểm)

Điền vào chỗ (……….) để hoàn thiện kiến thức của hộp ghi nhớ

Thuật toán tìm kiếm tuần tự thực hiện ……………….. lần lượt từ …………………………

của dãy với …………………………, việc tìm kiếm kết thúc khi ……………………. hoặc

...……………………………. các phần tử trong dãy.

Tìm hiểu thuật toán tìm kiếm nhị phân 18 phút (3điểm)

1. Phiếu giao nhiệm vụ 1 (2 phút) (0.5 điểm)

So sánh dãy số Hình 3 với dãy số Hình 1. Điền vào chỗ (…..)

Dãy số Hình 1:

Dãy số Hình 3:

Dãy số Hình 3 đã được ............................................................................................................

Cho 1 ví dụ về dãy số không giảm: ..........................................................................................

2. Phiếu giao nhiệm vụ 2 (5 phút) (1.5 điểm)

2.1 Điền vào chỗ (…..)

Khi một dãy thẻ số được sắp xếp theo thứ tự không giảm, có thể thực hiện tìm kiếm một số

bất kỳ theo ...............................................................................................................................

2.2 Điền vào chỗ (…….) mô phỏng thuật toán tìm kiếm nhị phân ở 3 lần lặp. Tìm số 21 trong

dãy số 12, 14, 15, 18, 19, 21, 24, 25, 26

* Lần lặp 1: Lật thẻ số ở giữa của dãy ((9+1):2 = 5, thẻ thứ 5). So sánh số cần tìm 21 > 19 nên

chỉ cần tìm ở ……………….của dãy thẻ (gồm các thẻ thứ 6, 7, 8, 9).

* Lần lặp 2: Lật thẻ số ở ………….. của nửa sau (thẻ thứ 7). So sánh 21 < 24 nên chỉ cần tìm

ở nửa trước của dãy thẻ (là thẻ thứ 6).

Thứ tự

Dãy thẻ số

Thứ tự

Dãy thẻ số

Lật thẻ ở vị trí giữa

Đã bỏ qua sau lần lặp thứ nhất

* Lần lặp 3: Lật thẻ số ở ……………củ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 quả là tìm thấy số 21 trong dãy; kết thúc tìm kiếm.

Thứ tự

Dãy thẻ số

Ghi ra số lần lật thẻ:………………..

3. Phiếu giao nhiệm vụ 3 (3 phút) (0.5 điểm)

Điền vào chỗ (…..) trên sơ đồ khối (Hình 4)

Hình 4. Sơ đồ khối mô tả thuật toán tìm kiếm nhị phân

để tìm một số trong dãy thẻ số đã được sắp xếp theo thứ tự không giảm ở Hình 3

Kết thúc

Đầu ra: thông báo

không tìm thấy

Kiểm tra: ………………………………..?

Sai

Xét dãy thẻ số đứng trước

thẻ số vừa lật (nửa trước)

Đúng

Sai

Đầu ra: thông báo

vị trí tìm thấy

Đúng

Đầu vào: Dãy thẻ số (đã sắp xếp

theo ……………………………), số cần tìm

Bắt đầu

Lật thẻ số ở ………………

Kiểm tra: Số cần tìm bằng

giá trị trên thẻ?

Kiểm tra: Số cần tìm nhỏ

hơn giá trị trên thẻ?

Xét dãy thẻ số đứng sau

thẻ số vừa lật (nửa sau)

Đúng

Sai

Lật thẻ ở vị trí giữa

Đã bỏ qua sau lần lặp thứ nhất

Đã bỏ qua sau lần lặp hai

4. Phiếu giao nhiệm vụ 4 (4phút) (0.5 điểm)

Điền vào chỗ (…..) để hoàn thiện kiến thức của hộp ghi nhớ

❖

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

– Áp dụng với dãy giá trị đã được ………….

– Ở 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ị của phần tử ……………… đang xé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 thì xét dãy ở nửa …………, nếu lớn hơn thì xét dãy ở nửa

………….

+ 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 lại Bước 1.

❖

Điều kiện áp dụng thuật toán tìm kiếm nhị phân là dãy số đã được ……………. theo thứ

tự nhất định (không giảm hoặc không tăng).

❖

Khi dãy số đã được ………………… 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 ……….., bởi vì sau mỗi lần lặp, ……………………….. chỉ còn bằng khoảng

một nửa so với bài toán trước đó. Việc chia bài toán thành những bài toán nhỏ hơn giúp tăng

hiệu quả tìm kiếm.

III.

HOẠT ĐỘNG 3- LUYỆN TẬP

(

Thời gian thực hiện 20 phút) (5 điểm)

1. Phiếu giao nhiệm vụ 1 (5 phút) (1.0 điểm)

Hoàn thành bảng 2 tìm bạn trong lớp có cùng tháng sinh với em bằng thuật toán tìm kiếm tuần

tự.

Bảng 2. Tìm bạn sinh cùng tháng với em bằng thuật toán tìm kiếm tuần tự

Lần lặp

Tháng sinh của bạn

Cùng tháng sinh với em

Đã hết danh sách/đã hỏi hết các bạn

Sai

2. Phiếu giao nhiệm vụ 2 (15 phút) (4.0 điểm)

a) Hoàn thành bảng 3 tìm tỉnh có hai số đầu biển số xe là 25 bằng thuật toán tìm kiếm tuần tự.

Số lần lặp được thực hiện là: …………………..

Bảng 3. Tìm tỉnh có hai số đầu biển số xe là 25

Lần lặp

Hai số đầu của biển số xe

Tên tỉnh

Đúng số cần tìm

Đã hết thẻ số

An Giang

Sai

Bà Rịa – Vũng Tàu

Bình Định

Cà Mau

Điện Biên

Gia Lai

Khánh Hòa

Lai Châu

Nam Định

Yên Bái

b) Điền vào chỗ (…..) để hoàn thiện bài toán tìm hai số đầu biển số xe của tỉnh lai Châu bằng

cách áp dụng thuật toán tìm kiếm nhị phân:

+ Lần lặp 1: Có 10 tỉnh đã được sắp xếp theo thứ tự của tên trong bảng chữ cái. Mở thẻ ở

…………. là Điện Biên. Thấy "Đ" < "L" nên chỉ cần tìm ở ……………….. của dãy.

+ Lần lặp 2: Xem kết quả ở giữa của …………………, là "Lai Châu" bằng với kết quả cần

tìm. Đối chiếu hai số đầu biển số xe của Lai Châu là 25.

+ Số lần lặp đã thực hiện là …………………..

c) Số lần lặp ở câu ………. ít hơn. Do dãy đã được sắp xếp nên thuật toán tìm kiếm nhị phân

thu hẹp được phạm vi tìm kiếm chỉ còn tối đa là một nửa sau mỗi lần lặp.

d) …………………... Vì dãy số chưa được sắp xếp theo trình tự không tăng hoặc không giảm.

IV.

HOẠT ĐỘNG 4- VẬN DỤNG

(

Thời gian thực hiện 10 phút) (5 điểm)

1. Phiếu giao nhiệm vụ 1 (5 phút) (2.0 điểm)

Bài 1. Em tìm một từ tiếng Anh trong cuốn từ điển theo cách nào? Tại sao em dùng cách đó?

Em tìm một từ tiếng Anh trong cuốn từ điển theo cách ..........................................................

................................................................................................................................................

Em dùng cách đó vì: .................................................................................................................

2. Phiếu giao nhiệm vụ 2 (5 phút) (3.0 điểm)

Bài 2. Hãy vận dụng thuật toán tìm kiếm nhị phân để xác định một bạ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.

Gợi ý: Ngày sinh là tìm 1 số trong dãy số đã được sắp xếp từ 1 đến 31. Tháng sinh là tìm một

số trong dãy số đã được sắp xếp từ 1 đến 12.

................................................................................................................................................

HS thực hiện tương tự, để xác định một bạn sinh vào tháng nào trong năm thì em cần dùng

nhiều nhất bao nhiêu câu hỏi Đúng/Sai?

................................................................................................................................................

(Mọi thắc mắc cần giải đáp, quý thầy cô trao đổi với tác giả: Phạm Duy Phượng Chi

0903719797, trường THPT Trần Cao Vân TP.HCM)

Hình 2. 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ẻ số ở Hình 1

Sai

Đúng

Đầu ra: thông báo

vị trí tìm thấy

Đầu ra: thông báo

không tìm thấy

Lật thẻ tiếp theo

Bắt đầu

Đầu vào: Dãy thẻ số, số cần tìm

Kết thúc

Lật thẻ thứ nhất

Kiểm tra: Số trên thẻ có

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

Kiểm tra: tất cả các thẻ số

đã được lật?

Đúng

Hình 4. Sơ đồ khối mô tả thuật toán tìm kiếm nhị phân

để tìm một số trong dãy thẻ số đã được sắp xếp theo thứ tự không giảm ở Hình 3

Kết thúc

Đầu ra: thông báo

không tìm thấy

Kiểm tra: dãy rỗng?

Sai

Xét dãy thẻ số đứng trước

thẻ số vừa lật (nửa trước)

Đúng

Sai

Đầu ra: thông báo

vị trí tìm thấy

Đúng

Đầu vào: Dãy thẻ số (đã sắp xếp

theo thứ tự không giảm), số cần tìm

Bắt đầu

Lật thẻ số ở giữa dãy

Kiểm tra: Số cần tìm bằng

giá trị trên thẻ?

Kiểm tra: Số cần tìm nhỏ

hơn giá trị trên thẻ?

Xét dãy thẻ số đứng sau

thẻ số vừa lật (nửa sau)

Đúng

Sai

Xem hướng dẫn

ĐỀ KIỂM TRA TIẾNG ANH 11 GLOBAL SUCCESS TEST UNIT cả năm có đáp án

TIN HOC 3 - BAI (16).pptx

TIN HOC 3 - BAI (14).pptx

TIN HOC 3 - BAI (13).pptx

TIN HOC 3 - BAI (12).pptx

TIN HOC 3 - BAI (11).pptx

TIN HOC 3 - BAI (10).pptx

TIN HOC 3 - BAI (9).pptx

TIN HOC 3 - BAI (8).pptx

TIN HOC 3 - BAI (7).pptx

Phiếu học tập cá nhân bài 13. THUẬT TOÁN TÌM KIẾM.pdf

Có thể bạn cũng quan tâm