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

Khởi động trang 71 Bài 13 Tin học lớp 7:
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. Hướng dẫn trả lời:
Cách tìm: Tìm lần lượt từ đầu dãy, tìm thẻ bài nào chứa số cần tìm thì dừng lại.
1. Thuật toán tìm kiếm tuần tự
Khám phá 1 trang 72 Tin học lớp 7: 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ự.
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ố? Quảng cáo 1 26 Sai Sai 2 14 Sai Sai ....... ....... ....... .......
Hướng dẫn trả lời: Lần lặp Số ghi trên thẻ Đúng số cần tìm? Đã hết thẻ số? Quảng cáo 1 26 Sai Sai 2 14 Sai Sai 3 24 Sai Sai 4 18 Sai Sai 5 15 Sai Sai 6 21 Đúng Sai
⇒ Sau 6 lần lặt thẻ mới tìm được thẻ ghi số 21.
Khám phá 2 trang 72 Tin học lớp 7: 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ố. Hướng dẫn trả lời: Đáp án: B
Để 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
so sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.
2. Thuật toán tìm kiếm nhị phân
Khám phá trang 74 Tin học lớp 7: 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. Hướng dẫn trả lời:
Em và bạn mình tự thực hiện trò chơi.
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:
+ 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.
+ Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc.
+ 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.
+ 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 đầu tiên
Luyện tập trang 75 Tin học lớp 7
Luyện tập 1 trang 75 Tin học lớp 7: 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ạ).
Hướng dẫn trả lời: 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 trang 75 Tin học lớp 7: 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ự 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? Hướng dẫn trả lời: a) Lần Tỉnh Hai số đầu của Có bằng 25 Đã hỏi hết danh lặp biển số xe không sách? 1 An Giang 67 Sai Sai 2 Bà Rịa – Vũng 72 Sai Sai Tàu 3 Bình Định 77 Sai Sai 4 Cà Mau 69 Sai Sai 5 Điện Biên 27 Sai Sai 6 Gia Lai 81 Sai Sai 7 Khánh Hoà 79 Sai Sai 8 Lai Châu 25 Đúng Sai b)
- Lần lặp 1: Lật thẻ ở giữa dãy: Điện Biên. Do Lai Châu > Điện Biên nên ta tìm
ở nửa sau của dãy gồm Gia Lai, Khánh Hoà, Lai Châu, Nam Định, Yên Bái.
- Lần lặp 2: Lật thẻ ở giữa dãy: Lai Châu = Lai Châu nên ta dừng thuật toán ở
đây. Hai số đầu của tỉnh Lai Châu là 25
Có 2 lần lặp được thực hiện.
c) Số lần lặp ở câu b ít hơn. Câu b sử dụng thuật toán tìm kiếm nhị phân hạn
chế được số lần lặp nên ít hơn câu a. d) Có thể
Ví dụ tìm tỉnh biết 2 số đầu của biển số xe đó là 25:
- Sắp xếp các số theo thứ tự tăng dần 18, 21, 25, 27, 67, 69, 72, 77, 79, 81.
- Lần lặp 1: Lật thẻ ở giữa dãy: 67. Do 25 < 67 nên chỉ cần tìm ở nửa trước gồm 18, 21, 25, 27
- Lần lặp 2: Lật thẻ ở giữa dãy: 21. Do 25 > 21 nên ta tìm ở nửa sau gồm 25, 27.
- Lần lặp 3: Lật thẻ ở giữa dãy: 25. Do 25 = 25 nên ta dừng thuật toán. Tỉnh cần tìm là tỉnh Lai Châu
Có 3 lần lặp được thực hiện.
Vận dụng trang 75 Tin học lớp 7
Vận dụng 1 trang 75 Tin học lớp 7: 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 đó? Hướng dẫn trả lời:
Em tìm một từ tiếng Anh trong cuốn từ điển theo cách:
- Tìm chữ cái đầu tiên của từ đó bằng thuật toán tìm kiếm nhị phân
- Sử dụng tiếp thuật toán tìm kiếm nhị phân để tìm khoảng nhỏ của từ đó
- Tìm từ cần tra trong khoảng đó bằng thuật toán tìm kiếm tuần tự
Cách làm trên nhanh chóng, thuận tiện, tiết kiệm thời gian.
Vận dụng 2 trang 75 Tin học lớp 7: 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? Hướng dẫn 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.