Bài 13 Thuật toán tìm kiếm trang 71 sách giáo khoa tin học lớp 7, NXB Chân trời sáng tạo, mời các em tham khảo cùng Bumbii.
Chủ đề 5. Giải quyết vấn đề với sự trợ giúp của máy tính. Bài 13. Thuật toán tìm kiếm.
KHỞI ĐỘNG
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.
Đáp án:
Có 2 cách tìm:
Cách 1: Lật lần lượt từng thẻ số theo thứ tự cho đến khi tìm thấy hoặc đã lật hết thẻ mà không tìm thấy.
Cách 2: Lật từng thẻ số một cách ngẫu nhiên cho đến khi tìm thấy hoặc đã lật hết các thẻ mà không tìm thấy. Cách này có thể sẽ rất nhiều thẻ số và mỗi lần lật một thẻ số rồi phải úp lại mới được lật thẻ tiếp theo.
Như vậy cách 1 để dễ thực hiện, dễ nhớ thẻ đã lật, thẻ chưa lật.
KHÁM PHÁ
Thuật toán tìm kiếm tuần tự
Câu 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 đãy theo thuật toán tìm kiếm tuần tự.
Bảng 1. Tìm số 21 trong dãy số bằng thuật toán tìm kiếm tuần tự
| 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 |
| … | … | … | … |
Đáp án:
Bảng 1. Tìm số 21 trong dãy số bằng thuật toán tìm kiếm tuần tự
| 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 |
Đã tìm thấy số 21 ở lần lặp 6, thuật toán kết thúc.
Câu 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:
Phương án đúng là B.
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.
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ẻ. Đặt ú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.
Đáp án: (gợi ý)
Ví dụ, có 10 thẻ số được sắp xếp tăng dần như sau:
| Thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Dãy thẻ số | 12 | 14 | 18 | 19 | 21 | 24 | 26 | 27 | 30 | 32 |
Dùng thuật toán tìm kiếm nhị phân để tìm số 26 trong dãy thẻ số ở trên.
Lần lặp 1. Lật thẻ số ở giữa của dãy (thẻ thứ 5)
| Thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Dãy thẻ số | 12 | 14 | 18 | 19 | 21 | 24 | 26 | 27 | 30 | 32 |
So sánh số cần tìm là 26 với số ghi trên thẻ vừa lật là 21. Do 26 > 21 nên chỉ cần tìm ở nửa sau của dãy thẻ.
| Thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Dãy thẻ số | 12 | 14 | 18 | 19 | 21 | 24 | 26 | 27 | 30 | 32 |
Lần lặp 2. Lật thẻ số ở giữa của nửa sau (thẻ thứ 8).
| Thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Dãy thẻ số | 12 | 14 | 18 | 19 | 21 | 24 | 26 | 27 | 30 | 32 |
So sánh số cần tìm là 26 với số ghi trên thẻ vừa lật là 27. Do 26 < 27 nên chỉ cần tìm ở nửa trước của dãy thẻ.
| Thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Dãy thẻ số | 12 | 14 | 18 | 19 | 21 | 24 | 26 | 27 | 30 | 32 |
Lần lặp 3. Lật thẻ số ở giữa của nửa trước (thẻ thứ 6)
| Thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Dãy thẻ số | 12 | 14 | 18 | 19 | 21 | 24 | 26 | 27 | 30 | 32 |
So sánh số cần tìm là 26 với số ghi trên thẻ vừa lật là 24. Do 26>24 nên chỉ cần tìm ở nửa sau của dãy thẻ.
| Thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Dãy thẻ số | 12 | 14 | 18 | 19 | 21 | 24 | 26 | 27 | 30 | 32 |
Lần lặp 4. Lật thẻ số ở giữa của nửa sau (thẻ thứ 7)
| Thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Dãy thẻ số | 12 | 14 | 18 | 19 | 21 | 24 | 26 | 27 | 30 | 32 |
Giá trị ghi trên thẻ thứ 7 là 26, bằng với số cần tìm nên kết quả là: tìm thấy số 21 trong dãy ở vị trí thứ 6 và thuật toán kết thúc.
LUYỆN TẬP
Câu 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).
Bảng 2. Tìm bạn sinh cùng tháng với em bằng thuật toán tìm kiếm tuần tự
| Lần lặp | Tháng sinh của bạn | Cùng tháng sinh với em | Đã hết danh sách/ đã hỏi hết các bạn |
| 1 | 4 | Sai | Sai |
| 2 | … | … | … |
| … | … | … | … |
Đáp án: (gợi ý)
Ví dụ: Em (tên là An) sinh tháng 2 (14/02/2009), em tìm và hỏi được ngày sinh của 5 bạn trong lớp như sau:
| Tên học sinh | Ngày sinh |
| Quí | 14/07/2009 |
| Bình | 02/05/2009 |
| Minh | 01/01/2009 |
| Hoa | 16/09/2009 |
| Phát | 26/02/2009 |
| Hòa | 11/12/2009 |
Bảng 2. Tìm bạn sinh cùng tháng với em bằng thuật toán tìm kiếm tuần tự
| Lần lặp | Tháng sinh của bạn | Cùng tháng sinh với em | Đã hết danh sách/ đã hỏi hết các bạn |
| 1 | 7 | Sai | Sai |
| 2 | 5 | Sai | Sai |
| 3 | 1 | Sai | Sai |
| 4 | 9 | Sai | Sai |
| 5 | 2 | Đúng |
Sau 5 lần lặp, em đã tìm thấy bạn sinh cùng tháng 2 là bạn Phát và thuật toán kết thúc.
Câu 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ủa một số 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 đầ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?
Bảng 3. Danh sách hai số đầu biển số xe của một số tỉnh
| Tên tỉnh | Hai số đầu của biển số xe |
| An Giang | 67 |
| Bà Rịa – Vũng Tàu | 72 |
| Bình Định | 77 |
| Cà Mau | 69 |
| Điện Biên | 27 |
| Gia Lai | 81 |
| Khánh Hòa | 79 |
| Lai Châu | 25 |
| Nam Định | 18 |
| Yên Bái | 21 |
Đáp án:
a. Áp dụng thuật toán tìm kiếm tuần tự để tìm ra tỉnh có hai đầu của biển số xe là 25.
| Lần lặp | Hai số đầu của biển số xe | Đúng số cần tìm? | Đã hết danh sách cần tìm? |
| 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 |
Sau khi thực hiện 8 lần lặp, thuật toán đã tìm thấy số cần tìm là 25, thuật toán kết thúc. Đó là tỉnh Lai Châu.
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.
Hai số đầu tiên của biển số xe của tỉnh Lai Châu là 25.
Ta sắp xếp các hai số đầu tiên của biển số xe các tỉnh thành một dãy số tăng dần như sau:
| Thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Dãy số | 18 | 21 | 25 | 27 | 67 | 69 | 72 | 77 | 79 | 81 |
Lần lặp 1. Chọn số ở vị trí giữa dãy (vị trí thứ 5)
| Thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Dãy số | 18 | 21 | 25 | 27 | 67 | 69 | 72 | 77 | 79 | 81 |
So sánh số cần tìm là 25 với số ở giữa dãy là 67. Do 25<67 nên chỉ cần tìm ở nửa trước của dãy.
Lần lặp 2. Chọn số ở vị trí giữa dãy (vị trí thứ 2)
| Thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Dãy số | 18 | 21 | 25 | 27 | 67 | 69 | 72 | 77 | 79 | 81 |
So sánh số cần tìm là 25 với số ở giữa dãy là 21. Do 25>21 nên chỉ cần tìm ở nửa sau của dãy.
Lần lặp 3. Chọn số ở vị trí giữa dãy (vị trí thứ 1)
| Thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Dãy số | 18 | 21 | 25 | 27 | 67 | 69 | 72 | 77 | 79 | 81 |
So sánh số cần tìm là 25 với số ở giữa dãy là 25. Do 25=25 nên thuật toán đã tìm thấy số 25 -> thuật toán kết thúc.
Như vậy sau 3 lần lặp, ta đã tìm thấy số 25.
c. Số lần lặp ở câu b) ít hơn vì danh sách tên tỉnh đã được sắp xếp nên có thể áp dụng thuật toán tìm kiếm nhị phân để tìm.
d. Không 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 đó vì danh sách hai số đầu của biển số xe chưa được sắp xếp.
VẬN DỤNG
Câu 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 đó?
Đáp án:
Các từ trong từ điển được sắp xếp theo thứ tự 24 chữ cái trong bảng chữ cái: a, b, c, …, z. Nên để tìm một từ tiếng Anh trong cuốn từ điển, em dùng thuật toán tìm kiếm nhị phân để tìm kiếm nhanh hơn.
Câu 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?
Đáp án:
Để xác định ngày sinh là tìm một số trong dãy số được sắp xếp từ 1 đến 31.
Để xác định ngày sinh là tìm một số trong dãy số được sắp xếp từ 1 đến 12.
Như vậy có thể áp dụng thuật toán tìm kiếm nhị phân để xác định ngày sinh, tháng sinh của một bạn.
Áp dụng thuật toán tìm kiếm nhị phân để xác định ngày sinh như sau:
Ta có dãy số theo ngày sinh:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31.
Câu hỏi 1: Ngày sinh của bạn có phải ở nửa trước của dãy số ngày sinh đúng không?
Dự đoán trả lời: Đúng-> Như vậy ngày sinh cần tìm ở phần nửa trước của dãy.
Ta có số 16 là vị trí giữa dãy:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31.
Nửa trước của dãy là: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
Câu hỏi 2: Ngày sinh của bạn có phải ở nửa trước của dãy số ngày sinh mới đúng không?
Dự đoán trả lời: Đúng -> Như vậy ngày sinh cần tìm ở phần nửa trước của dãy.
Ta có số 8 là vị trí giữa dãy mới:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
Nửa trước của dãy mới này là: 1, 2, 3, 4, 5, 6, 7.
Câu hỏi 3: Ngày sinh của bạn có phải ở nửa trước của dãy số ngày sinh mới đúng không?
Dự đoán trả lời: Đúng -> Như vậy ngày sinh cần tìm ở phần nửa trước của dãy.
Ta có số 4 là vị trí giữa dãy mới: 1, 2, 3, 4, 5, 6, 7.
Nửa trước của dãy mới này là: 1, 2, 3.
Câu hỏi 4: Ngày sinh của bạn có phải ở nửa trước của dãy số ngày sinh đúng không?
Dự đoán trả lời: Đúng -> Như vậy ngày sinh cần tìm ở phần nửa trước của dãy.
Ta có số 2 là vị trí giữa dãy mới: 1, 2, 3.
Nửa trước của dãy mới này là: 1.
Câu hỏi 5: Ngày sinh của bạn có phải là số trong dãy mới này không?
Trả lời: Đúng. Vì dãy mới còn có một số trong dãy.
Tương tự cho các câu trả lời là Đúng/Sai ở các trường hợp khác. Như vậy, để tìm ngày sinh của một bạn, chúng ta dùng nhiều nhất không quá 5 câu hỏi Đúng/Sai.
Áp dụng thuật toán tìm kiếm nhị phân để xác định tháng sinh như sau:
Ta có dãy số theo tháng sinh:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
Câu hỏi 1: Tháng sinh của bạn có phải ở nửa trước của dãy số tháng sinh đúng không?
Dự đoán trả lời: Sai -> Như vậy tháng sinh cần tìm ở phần nửa sau của dãy.
Ta có số 6 là vị trí giữa dãy:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.
Nửa sau của dãy: 7, 8, 9, 10, 11, 12.
Câu hỏi 2: Tháng sinh của bạn có phải ở nửa trước của dãy số tháng sinh mới đúng không?
Dự đoán trả lời: Sai -> Như vậy tháng sinh cần tìm ở phần nửa sau của dãy.
Ta có số 9 là vị trí giữa dãy:
7, 8, 9, 10, 11, 12.
Nửa sau của dãy: 10, 11, 12.
Câu hỏi 3: Tháng sinh của bạn có phải ở nửa trước của dãy số tháng sinh đúng không?
Dự đoán trả lời: Đúng -> Như vậy tháng sinh cần tìm ở phần nửa trước của dãy.
Ta có số 11 là vị trí giữa dãy: 10, 11, 12.
Nửa trước của dãy: 10.
Câu hỏi 4: Tháng sinh của bạn có phải là số trong dãy mới này không?
Trả lời: Đúng. Vì dãy mới chỉ còn một số trong dãy.
Tương tự cho các câu trả lời là Đúng/Sai ở các trường hợp khác. Như vậy, để tìm ngày sinh của một bạn, chúng ta dùng nhiều nhất không quá 4 câu hỏi Đúng/Sai.
__________***__________
Xem các bài giải khác tại https://bumbii.com/giai-bai-tap-sgk-tin-hoc-lop-7-nxb-chan-troi-sang-tao/
Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech
Không bao giờ từ bỏ hy vọng. Cố gắng mỗi ngày.