Giáo án và PPT Tin học 7 chân trời Bài 13: Thuật toán tìm kiếm

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

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

GV yêu cầu HS hoạt động cặp đôi và nêu nhiệm vụ: Có 9 thẻ số, mỗi thẻ được ghi số ở một mặt và mặt còn lại không ghi gì. Đặt úp các thẻ số trên mặt bàn và xếp thành một dãy như Hình 1.

Em hãy trao đổi với bản để thực hiện tìm một số bất kì có trong dãy số ghi trên các thẻ ở Hình 1 hay không.

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

1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ

Hoạt động 1: Thuật toán tìm kiếm tuần tự

- GV yêu cầu HS hoạt động cá nhân, đọc nội dung mục 1.Thuật toán tìm kiếm tuần tự kết hợp quan sát Hình 2 SGK tr.71, 72 và trả lời câu hỏi:

+ Khái niệm tìm kiếm

+ Em hãy nêu ví dụ về thuật toán tìm kiếm.

+ Em hãy quan sát Hình 2 và mô tả các bước của thuật toán tìm kiếm tuần tự.

Sản phẩm dự kiến:

- Tìm kiếm: là việc con người thường xuyền phải thực hiện trong đời sống thực tiễn.

- Thuật toán tìm kiếm tuần tự thực hiện so sánh tuần 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.

- Các bước của thuật toán tìm kiếm tuần tự:

          + Bắt đầu

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

          + Lật thẻ thứ nhất

          + Kiểm tra: Số trên thẻ có đúng là số cần tìm không?

=> Đúng → Đầu ra: thông báo vị trí tìm thấy → Kết thúc

=> Sai → Kiểm tra: tất cả các thẻ số đã được lật?

· Đúng → Đầu ra: thông báo không tìm thấy → Kết thúc.

· Sai → Lập thẻ tiếp theo → Kiểm tra số trên thẻ có phải là số cầm tìm không? (thực hiện lặp đi lặp lại

2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

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

- GV yêu cầu HS hoạt động thảo luận nhóm và trả lời câu hỏi:

+ So với cách tìm kiếm tuần tự, cách tìm kiếm nhị phân đối với bài toán này tìm nhanh hơn hay chậm hơn? Vì sao?

+ Điều kiện để thực hiện tìm kiếm nhị phân là gì?

Sản phẩm dự kiến:

- Các bước của 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):

          + 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

HOẠT ĐỘNG LUYỆN TẬP

Từ nội dung bài học, GV yêu cầu HS hoàn thành các bài tập trắc nghiệm sau:

Câu 1: Đầu ra của bài toán tìm kiếm một số trong dãy số cho trước là:

A. Số cần tìm

B. Dãy số và số cần tìm

C. Thông báo vị trí số được tìm thấy

D. Thông báo vị trí số được tìm thấy hoặc thông báo không tìm thấy số cần tìm

Câu 2: Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự, ta thực hiện:

A. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.

B. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.

C. Sắp xếp dãy số theo thứ tự tăng dần.

D. So sánh số cần tìm với số ở giữa dãy số.

Câu 3: Cho dãy số A = {24, 28, 14, 18, 19, 12, 19}. Để tìm kiếm số 19 trong dãy theo thuật toán tìm kiếm tuần tự cần thực hiện mấy lần lặp?

A. 5 lần

B. 6 lần

C. 7 lần

D. 8 lần

Câu 4: Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm nhị phân, ta thực hiện:

A. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.

B. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.

C. Sắp xếp dãy số theo thứ tự tăng dần.

D. So sánh số cần tìm với số ở giữa dãy số.

Câu 5: Với dãy số lần lượt là: 12, 14, 15, 18, 19, 21, 24, 25, 26. Nếu thực hiện theo thuật toán tìm kiếm nhị phân để tìm số 21 ta cần thực hiện mấy lần lặp?

A. 2 lần

B. 3 lần

C. 4 lần

D. 5 lần

Sản phẩm dự kiến:

HOẠT ĐỘNG VẬN DỤNG

Vận dụng kiến thức, GV yêu cầu HS trả lời câu hỏi:

Câu 1: Tìm một từ điển trong tiếng anh bằng cách nào? Tại sao em dùng cách đó?

Câu 2: Sử 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 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 được 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?