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

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

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.
 

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.

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 1:

  Thuật toán tìm kiếm tuần tự kết thúc khi nào?

  • A. Tìm kiếm được vị trí số cần tìm
  • B. Thông báo không tìm thấy số cần tìm
  • C. Tìm thấy hoặc đã duyệt hết các phần tử trong dãy
  • D. Cả A, B, C đều sai

• 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 như thế nào?

  • 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ố 39 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. Không lần nào

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é!

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

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!