Giải tin học 7 CTST bài 13 Thuật toán tìm kiếm

Hướng dẫn học môn Tin học 7 sách mới chân trời sáng tạo. Dưới đây là lời giải chi tiết bài 13: Thuật toán tìm kiếm. Từng bài tập được giải chi tiết, rõ ràng, dễ hiểu. Hi vọng, hocthoi.net sẽ hỗ trợ các em trong quá trình học tập, giúp các em ngày càng tiến bộ hơn.

KHỞI ĐỘNG

Câu hỏi. 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ì trong dãy số ghi trên các thẻ ở Hình 1.

Lời giải:

Lần lượt lật các thẻ số lên cho đến khi tìm được số cần tìm.

KHÁM PHÁ

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

Câu hỏi 1. Các số ghi trên mỗi thẻ ở Hình 1 lần lượt là: 26, 14, 24, 18, 15, 21, 19, 25, 12.

Em hãy tạo Bảng 1 và điền thông tin của mỗi lần lặp để tìm số 21 trong dãy theo thuật toán tìm kiếm tuần tự.

Lời giải:

Bảng 1. Tìm số 21 trong dãy số băng thuật toán tìm kiếm

Lần lặp

Số ghi trên thẻ

Đúng số cần tìm?

Đã hết thẻ số

1

26

Sai

Sai

2

14

Sai

Sai

3

24

Sai

Sai

4

18

Sai

Sai

5

15

Sai

Sai

6

21

Đúng

Sai

Câu hỏi 2. Lựa chọn phương án đúng

Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm, 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ức tự tăng dần.

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

Lời giải:

Chọn B.

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

Câu hỏi. 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.

Lời giải:

HS tự thực hiện.

LUYỆN TẬP

Câu hỏi 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).

Lời giải:

HS tự thực hiện.

Câu hỏi 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à 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?

Lời giải:

a. Ta có:

Bảng. Tìm tỉnh có hai số đầu biển số xe là 25

Lần lặp

Hai số đầu của biển số xe

Tên tỉnh

Đúng số cần tìm?

Đã hết thẻ số

1

67

An Giang

Sai

Sai

2

72

Bà Rịa - Vũng Tàu

Sai

Sai

3

77

Bình Định

Sai

Sai

4

69

Cà Mau

Sai

Sai

5

27

Điện Biên

Sai

Sai

6

81

Gia Lai

Sai

Sai

7

79

Khánh Hòa

Sai

Sai

8

25

Lai Châu

Đúng

-

=> Thực hiện 8 lần lặp.

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.

VẬN DỤNG

Câu hỏi 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 đó?

Lời giải:

Em sẽ tra theo thứ tự của lần lượt từng chữ cái trong từ đó. Em dùng cách này vì tiện và nhanh chóng tìm được từ mình muốn tra.

  • Em sẽ tra theo thứ tự của lần lượt từng chữ cái trong từ đó.
  • Em dùng cách này vì tiện và nhanh chóng tìm được từ mình muốn tra.

Câu hỏi 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?

Lời giải:

HS tự thực hiện.

Từ khóa tìm kiếm google:

giải sgk tin học 7 sách mới, giải tin học 7 chân trời sáng tạo, giải tin học 7 CTST bài 13, giải bài thuật toán tìm kiếm
Phần trên, hocthoi.net đã soạn đầy đủ lý thuyết và bài tập của bài học: Giải tin học 7 CTST bài 13 Thuật toán tìm kiếm . Bài học nằm trong chuyên mục: Giải tin học 7 chân trời sáng tạo. Phần trình bày do Quỳnh Chi tổng hợp và thực hiện giải bài. Nếu có chỗ nào chưa rõ, có phần nào muốn hiểu rộng thêm, bạn đọc vui lòng comment bên dưới. Ban biên tập sẽ giải đáp giúp các bạn trong thời gian sớm nhất.

Bài soạn các môn khác

Bình luận