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.
1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
Làm 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àm 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:
Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.
So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.
Sắp xếp dãy số theo thức tự tăng dần.
So sánh số cần tìm với số ở giữa dãy số.
2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Làm: 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.
LUYỆN TẬP
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 họa).
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 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?
VẬN DỤNG
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 đó?
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 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?
PHẦN II .Lời giải tham khảo
KHỞI ĐỘNG
Trong bài khởi động, để tìm một số bất kỳ trong dãy số ở Hình 1, ta sẽ thực hiện việc lật từng thẻ số lên và so sánh với số cần tìm. Quá trình này tương ứng với thuật toán tìm kiếm tuần tự, vì ta kiểm tra từng phần tử một cho đến khi tìm thấy kết quả.
1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
Làm 1: Để tìm số 21 trong dãy số: 26, 14, 24, 18, 15, 21, 19, 25, 12, theo thuật toán tìm kiếm tuần tự, ta thực hiện các bước lặp sau:
So sánh số đầu tiên (26) với 21: không khớp.
So sánh số thứ hai (14) với 21: không khớp.
So sánh số thứ ba (24) với 21: không khớp.
So sánh số thứ tư (18) với 21: không khớp.
So sánh số thứ năm (15) với 21: không khớp.
So sánh số thứ sáu (21) với 21: khớp.
Kết quả: Số 21 được tìm thấy ở lần lặp thứ 6.
Lần lặp
Số đang xét
Kết quả so sánh
1
26
Không khớp
2
14
Không khớp
3
24
Không khớp
4
18
Không khớp
5
15
Không khớp
6
21
Khớp
Làm 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ự. Phương án đúng là:
"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
Làm: Để thực hiện trò chơi mô phỏng thuật toán tìm kiếm nhị phân:
Sắp xếp các thẻ số theo thứ tự tăng dần: Ví dụ: 12, 14, 15, 18, 19, 21, 24, 25, 26.
Lật từng thẻ số ở vị trí giữa dãy hiện tại, sau đó
Nếu số trên thẻ bằng số cần tìm, kết thúc.
Nếu số trên thẻ nhỏ hơn số cần tìm, loại bỏ nửa dãy bên trái.
Nếu số trên thẻ lớn hơn số cần tìm, loại bỏ nửa dãy bên phải.
Tiếp tục lặp lại bước 2 cho đến khi tìm được số.
LUYỆN TẬP
Luyện tập 1: Sử dụng thuật toán tìm kiếm tuần tự để tìm bạn cùng tháng sinh. Ta tiến hành hỏi từng bạn hoặc tra cứu danh sách lớp theo thứ tự.
Ví dụ minh họa bảng kết quả:
Lần lặp
Tên bạn
Tháng sinh
Kết quả so sánh
1
An
3
Không khớp
2
Bình
5
Không khớp
3
Chi
3
Khớp
Nếu tìm thấy bạn cùng tháng sinh, quá trình dừng lại.
Luyện tập 2:
a) Tìm tỉnh có biển số xe là 25 bằng thuật toán tìm kiếm tuần tự. Danh sách các tỉnh:
Các số biển số xe: 01, 02, 04, 06, 11, 14, 17, 19, 20, 22, 24, 25, 26.
Thực hiện các bước lặp:
So sánh lần lượt từng số với 25.
Đến lần lặp thứ 12, ta tìm được số 25.
Số lần lặp: 12.
b) Tìm tỉnh có biển số xe Lai Châu (25) bằng thuật toán tìm kiếm nhị phân:
Sắp xếp danh sách đã có thứ tự tăng dần.
Xét phần tử giữa (biển số xe 14):
25 > 14, loại bỏ nửa dưới (dãy còn lại: 17, 19, 20, 22, 24, 25, 26).
Xét phần tử giữa dãy còn lại (biển số xe 22):
25 > 22, loại bỏ nửa dưới (dãy còn lại: 24, 25, 26).
Xét phần tử giữa dãy còn lại (biển số xe 25): Tìm thấy.
Số lần lặp: 3.
c) So sánh số lần lặp:
Tìm kiếm tuần tự: 12 lần.
Tìm kiếm nhị phân: 3 lần.
Kết luận: Tìm kiếm nhị phân ít lần lặp hơn, vì thuật toán này giảm số phần tử cần xét theo cấp số nhân (chia đôi dãy sau mỗi lần lặp).
d) Có thể áp dụng thuật toán tìm kiếm nhị phân để tìm tỉnh khi biết hai số đầu của biển số không?
Trả lời: Có thể, nhưng chỉ khi danh sách các tỉnh đã được sắp xếp theo thứ tự tăng dần của biển số xe. Nếu danh sách không được sắp xếp, cần sử dụng thuật toán tìm kiếm tuần tự.
VẬN DỤNG
Vận dụng 1: Khi tìm từ trong từ điển tiếng Anh, em dùng cách tra từ theo thứ tự bảng chữ cái. Đây là cách áp dụng thuật toán tìm kiếm nhị phân, vì từ điển đã được sắp xếp theo thứ tự tăng dần, cho phép tra cứu nhanh hơn bằng cách lật đến giữa từ điển, so sánh, và tiếp tục chia dãy.
Vận dụng 2:
Xác định ngày sinh:
Một tháng có tối đa 31 ngày.
Với mỗi câu hỏi Đúng/Sai, em có thể loại bỏ một nửa số ngày.
Do đó, cần tối đa:
\(\lceil \log_2{31} \rceil = 5\) câu hỏi.
Xác định tháng sinh:
Một năm có 12 tháng. Cần tối đa:
\(\lceil \log_2{12} \rceil = 4\) câu hỏi.
TỔNG KẾT
Qua bài tập, chúng ta đã hiểu rõ cách áp dụng các thuật toán tìm kiếm tuần tự và nhị phân trong các tình huống thực tế. Việc nắm rõ cách hoạt động của từng thuật toán giúp giải quyết vấn đề nhanh chóng và hiệu quả hơn, đặc biệt là khi xử lý dữ liệu lớn.
