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

Tin học lớp 7 bài 13: Thuật toán tìm kiếm
Khởi động SGK Tin học 7 bài 13
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.
Hình 1: Các thẻ được ghi số ở mặt úp
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. Trả lời:
Em có thể tìm một thẻ bất kì theo yêu cầu trong dãy số trên (Hình 1) bằng cách lặt từng thẻ số.
Khám phá SGK Tin học 7 bài 13 Khám phá 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ự. Trả lời: Lần lặp Số ghi trên thẻ
Đúng số cần tìm? Đã hết số thẻ 1 26 Sai Sai 2 14 Sai Sai 3 24 Sai Sai 4 18 Sai Sai 5 15 Sai Sai 6 21 Đúng Sai
Vậy khi lặp lần thứ 6 ta đã tìm được số cần tìm. Kết thúc quá trình tìm kiếm Khám phá 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 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ố. Đáp án: B
Luyện tập SGK Tin học 7 bài 13 Luyện tập 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 hoạ). Trả lời:
Giả sử tháng sinh của em là tháng 3. Em sẽ đi hỏi tháng sinh của các bạn và ghi vào bảng thống kê: Lần lặp
Tháng sinh của Cùng tháng sinh Đã hết danh sách/ bạn với em đã hỏi hết các bạn 1 4 Sai Sai 2 2 Sai Sai 3 1 Sai Sai 4 5 Sai Sai 5 6 Sai Sai 6 8 Sai Sai 7 12 Sai Sai 8 11 Sai Sai 9 3 Đúng Sai
Sau lần lặp thứ 9 đã có bạn cùng tháng sinh với em. Kết thúc tìm kiếm. Luyện tập 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 hiệ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? Trả lời:
a) Biển số xe cần tìm là 25. Lần lặp Biển số xe tỉnh
Cùng biển số xe Danh sách tìm kết toàn bộ bảng 1 67 Sai Sai 2 72 Sai Sai 3 77 Sai Sai 4 69 Sai Sai 5 27 Sai Sai 6 81 Sai Sai 7 79 Sai Sai 8 25 Đúng Sai
Sau 8 lần lặp đã tìm được kết quả. Kết thúc tìm kiếm.
b) Bước 1. Sắp xếp biển số xe theo thứ tự tăng dần hoặc giảm dần.
Bảng Biển số xe tăng dần
Bước 2. Lật thẻ số ở giữa của dãy (thẻ thứ 5). So sánh số cần tìm là 25 trên thẻ
vừa lật là 67. Do 25 < 67 nên chỉ cần tìm ở nửa đầu của dãy thẻ (gồm 1, 2, 3, 4)
Bước 4. Lật thẻ số ở giữa của dãy (thẻ thứ 2). So sánh số cần tìm là 25 trên thẻ
vừa lật là 21. Do 25 > 21 nên số cần tìm ở nửa sau của dãy thẻ (vị trí số 3, 4).
Bước 5. Lật thẻ vị trí số 3. So sánh số cần tìm là 25 trên thẻ vừa lật là 25. Do 25
= 25 nên đưa ra thông báo đã tìm thấy kết quả. Kết thúc quá trình tìm kiếm.
c) Số lần lặp lại ở câu b ít hơn câu a. Vì tìm kiếm nhị phân chia nhỏ mảng tìm
kiếm nên số lần lặp ít hơn.
d) Ta có thể 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. Vì khi thực hiện tìm kiếm ta sẽ chia nhỏ mảng số và tìm được số cần tìm.
Vận dụng SGK Tin học 7 bài 13 Vận dụng 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 đó? Trả lời:
Các bước tra từ điển: 
Bước 1. Sắp xếp từ ngữ theo thứ tự tăng dần theo bảng chữ cái. 
Bước 2. Chọn chữ cái bắt đầu của từ tiếng anh để tìm kiếm. 
Bước 3. Chia nhỏ danh sách tìm kiếm và tìm chữ tiếng anh.
Vì: Khi thực hiện cách này giúp cho quá trình tìm kiếm nhanh hơn. Vận dụng 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 đượ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? Trả lời:
Câu hỏi đặt ra cho bạn để xác định ngày sinh trong tháng:
Ví dụ: Bạn của em sinh ngày 5. (Em sẽ sử dụng câu hỏi đúng hoặc sai vào từng
lựa chọn Lớn hơn hay Nhỏ hơn). 
Câu hỏi 1: Bạn sinh vào ngày nhỏ hơn 15 (hay lớn hơn 15). 
Câu hỏi 2: Ngày sinh của bạn nhỏ hơn 7 (hay lớn hơn 7). 
Câu hỏi 3: Ngày sinh của bạn nhỏ hơn 4 (hay lớn hơn 4). 
Câu hỏi 4: Ngày sinh của bạn bằng 5 hay lớn hơn 5. Khi đó ta sẽ được kết quả.
Tương tự: Để xác định bạn sinh vào tháng nào trong năm em sẽ dùng 4 câu hỏi đúng sai.