OPTADS360
AANETWORK
LAVA
YOMEDIA
Banner-Video
IN_IMAGE

Tin học 7 Chân trời sáng tạo Bài 13: Thuật toán tìm kiếm


Bài 13: Thuật toán tìm kiếm trong chủ đề 5 của chương trình Tin học 7 Chân trời sáng tạo bao gồm các kiến thức về thuật toán tìm kiếm sẽ giúp các em giải quyết bài toán một cách dễ dàng. Mời các em tham khảo nội dung bài giảng do HOC247 biên soạn dưới đây!

ADSENSE/lession_isads=0
QUẢNG CÁO
 
 
 

Tóm tắt lý thuyết

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

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.

- Bài tìm kiếm một số trên thẻ được mô tả như sau:

+ Đầu vào: Dãy số (được ghi trên các thẻ) và số cần tìm.

+ Đầ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.

- Sơ đồ khối:

Sơ đồ khối mô tả thuật toán tìm kiếm tuần tự để tìm một số

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

* Bài toán:

Các số được ghi ở mặt úp của các thẻ

* Sơ đồ khối tìm kiếm nhị phân:

Sơ đồ khối mô tả thuật toán tìm kiếm nhị phân để tìm một số trong một dãy thẻ số đã được sắp xếp theo thứ tự không giảm

- 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. 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.

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.

Sắp xếp và tìm kiếm

Sắp xếp giúp việc tìm kiếm được thực hiện nhanh hơn, hiệu quả hơn.

ADMICRO

Bài tập minh họa

Bài tập 1: Tìm một từ tiếng Anh trong cuốn từ điển, em sẽ tìm kiếm theo cách nào nhanh nhất?

Hướng dẫn giải:

Cuốn từ điển đã được sắp xếp theo vần Alphabet. Do đó tìm kiếm nhị phân sẽ tiết kiệm được thời gian và tìm kiếm nhanh hơn.

Bài tập 2: 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?

Hướng dẫn giải:

Với thuật toán tìm kiếm nhị phân ta cần thực hiện 3 lần lặp. Lần 1 so sánh 21 và 19, Lần 2 so sánh 21 và 24. Lần 3 tìm kiếm được số 21.

Bài tập 3: Ưu điểm của thuật toán tìm kiếm nhị phân là gì?

Hướng dẫn giải:

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. 

Thuật toá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.
 

ADMICRO

Luyện tập

Qua bài học các em có thể:

- 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.

3.1. Trắc nghiệm Bài 13 Tin học 7 Chân trời sáng tạo

Các em có thể hệ thống lại nội dung kiến thức đã học được thông qua bài kiểm tra Trắc nghiệm Tin học 7 Chân trời sáng tạo Chủ đề 5 Bài 13 cực hay có đáp án và lời giải chi tiết. 

Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!

3.2. Bài tập SGK Bài 13 Tin học 7 Chân trời sáng tạo

Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 7 Chân trời sáng tạo Chủ đề 5 Bài 13 để giúp các em nắm vững bài học và các phương pháp giải bài tập.

Khởi động trang 71 SGK Tin học 7 Chân trời sáng tạo - CTST

Khám phá 1 trang 72 SGK Tin học 7 Chân trời sáng tạo - CTST

Khám phá 2 trang 72 SGK Tin học 7 Chân trời sáng tạo - CTST

Khám phá trang 74 SGK Tin học 7 Chân trời sáng tạo - CTST

Luyện tập 1 trang 75 SGK Tin học 7 Chân trời sáng tạo - CTST

Luyện tập 2 trang 75 SGK Tin học 7 Chân trời sáng tạo - CTST

Vận dụng 1 trang 75 SGK Tin học 7 Chân trời sáng tạo - CTST

Vận dụng 2 trang 75 SGK Tin học 7 Chân trời sáng tạo - CTST

Hỏi đáp Bài 13 Tin học 7 Chân trời sáng tạo

Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!

Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!

-- Mod Tin Học 7 HỌC247

NONE
OFF