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).
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 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?
Bài Làm:
Câu 1. HS tự thực hiện.
Câu 2.
a)
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.