1. Em tìm một từ tiếng Anh trong quyển từ điển theo cách nào?
Câu hỏi: Em tìm một từ tiếng Anh trong quyển từ điển theo cách nào? Tại sao em lại dùng cách đó?
Gợi ý trả lời:
Em tìm một từ tiếng Anh trong quyển từ điển bằng cách thực hiện một phương pháp tìm kiếm có cấu trúc hơn, một phương pháp đòi hỏi sự chia nhỏ và so sánh tỉ mỉ. Thay vì lần lượt kiểm tra từng từ trong từng trang theo thứ tự bảng chữ cái, em chia đổi quyển từ điển thành các phần nhỏ hơn và tìm kiếm từ ở vị trí trung tâm của mỗi phần.
Đầu tiên, em tìm một từ ở giữa quyển từ điển và so sánh với từ cần tìm. Nếu từ đó trùng khớp, em hoàn thành việc tìm kiếm. Nếu không, em tiếp tục chia quyển từ điển thành nửa phần thích hợp hơn và lặp lại quá trình cho đến khi từ cần tìm xuất hiện.
Cách tiếp cận này mang lại sự hiệu quả và tiết kiệm thời gian hơn so với việc tìm kiếm từng từ theo thứ tự bảng chữ cái. Bằng cách này, em không cần phải duyệt qua tất cả các từ một cách lần lượt mà có thể thu gọn phạm vi tìm kiếm một cách đáng kể, tận dụng sự tổ chức của từ điển để nhanh chóng đạt được mục tiêu của mình.
2. Lý thuyết Tin học 7 - Thuật toán tìm kiếm nhị phân
2.1. Thuật toán tìm kiếm nhị phân
Thuật toán tìm kiếm nhị phân hoạt động trên một danh sách đã được sắp xếp và tiến hành các bước sau:
- Bắt đầu từ vị trí ở giữa danh sách.
- Tại mỗi bước, so sánh giá trị cần tìm với giá trị ở vị trí giữa danh sách:
+ Nếu giá trị cần tìm lớn hơn, tìm kiếm trong nửa sau của danh sách.
+ Nếu giá trị cần tìm nhỏ hơn, tìm kiếm trong nửa trước của danh sách.
+ Nếu bằng, dừng lại vì đã tìm thấy.
- Tiếp tục quá trình tìm kiếm cho đến khi tìm thấy giá trị hoặc hết danh sách.
Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên là:
- Nếu không có phần tử nào trong vùng tìm kiếm, kết luận rằng không tìm thấy và kết thúc thuật toán.
- Xác định vị trí giữa của vùng tìm kiếm, chia thành hai nửa: nửa trước và nửa sau vị trí giữa.
- Nếu giá trị cần tìm bằng giá trị ở vị trí giữa, kết luận rằng "giá trị cần tìm xuất hiện tại vị trí giữa" và kết thúc.
- Nếu giá trị cần tìm nhỏ hơn giá trị ở vị trí giữa, thu hẹp vùng tìm kiếm chỉ còn nửa trước của danh sách. Ngược lại, thu hẹp vùng tìm kiếm chỉ còn nửa sau của danh sách.
- Lặp lại từ bước 1 đến bước 4 cho đến khi tìm thấy giá trị cần tìm (bước 3) hoặc không còn phần tử nào trong vùng tìm kiếm (bước 1).
Vị trí giữa của vùng tìm kiếm được tính bằng phần nguyên của (vị trí đầu + vị trí cuối) chia cho 2.
2.2. Sắp xếp và tìm kiếm
- Sắp xếp tạo điều kiện thuận lợi cho việc tìm kiếm nhanh chóng hơn. Ví dụ, trong trường hợp có 10 số trên các tấm thẻ như 2, 3, 5, 6, 8, 9, 11, 15, 16, 18 và A là người giữ thẻ, còn B là người tìm kiếm.
Yêu cầu đặt ra là B phải sử dụng thuật toán tìm kiếm nhị phân để tìm một số nhỏ hơn 20 trong các tấm thẻ của A.
Cách thực hiện như sau:
Bước 1: A sắp xếp lần lượt 10 tấm thẻ trên bàn theo thứ tự tăng dần của các số.
Bước 2: B cho biết số mà B cần tìm.
Bước 3: B chọn tấm thẻ ở vị trí giữa dãy.
Bước 4: A mở tấm thẻ và thông báo kết quả bằng một trong ba cụm từ: "bằng nhau", "lớn hơn" hoặc "bé hơn", tùy thuộc vào kết quả so sánh số B cần tìm với số ở vị trí giữa của dãy.
Bước 5: B dựa vào câu trả lời của A để chọn nửa dãy tiếp theo để tìm kiếm.
Bước 6: B lặp lại các bước 3, 4, 5 cho đến khi B tìm thấy số cần tìm hoặc đã tìm hết dãy số.
Bước 7: Trong lượt tiếp theo, A và B hoán đổi vai trò để tiếp tục trò chơi.
3. Bài tập vận dụng liên quan
Câu 1: Trường hợp nào sử dụng thuật toán tìm kiếm nhị phân?
A. Tìm kiếm một phần tử trong danh sách bất kì.
B. Tiếp cận các phần tử đã được sắp xếp trong danh sách.
Câu 2: Ý tưởng cơ bản của thuật toán tìm kiếm nhị phân là gì?
A. Sử dụng cấu trúc dữ liệu cây tìm kiếm.
B. Duyệt từ đầu đến cuối dãy để tìm kiếm.
C. So sánh X với phần tử giữa của dãy, sau đó dựa vào kết quả so sánh để quyết định tìm kiếm ở nửa đầu hoặc nửa sau của danh sách.
D. Lần lượt so sánh X với các phần tử a1, a2, ..., an.
Câu 3: Cần bao nhiêu bước để tìm thấy "Thailand" trong danh sách các tên quốc gia sau:
Brunei, Campodia, Laos, Myanmar, Singpore, Thailand, Vietnam
A. 1
B. 2
C. 3
D. 4
Câu 4: Số bước lặp cần thiết cho thuật toán tìm kiếm nhị phân để thông báo không tìm thấy số 15 trong danh sách [3, 5, 7, 11, 12, 25] là bao nhiêu?
A. 2
B. 3
C. 4
D. 5
Dùng dữ kiện sau để trả lời các câu hỏi 5 - 8
Em hãy điền các cụm từ: giá trị cần tìm xuất hiện ở vị trí giữa, nửa sau, “Không tìm thấy”, nửa trước vào chỗ chấm (...) được đánh số trong các câu sau để được mô tả chính xác về thuật toán tìm kiếm nhị phân.
Bước 1: Nếu vùng tìm kiếm không có phần tử nào thì kết luận .... (1) và thuật toán kết thúc.
Bước 2. Xác định vị trí giữa vùng tìm kiếm. Vị trí này chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa.
Bước 3. Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận .....(2) và thuật toán kết thúc.
Bước 4. Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn .......(3) của dãy. Ngược lại (nếu giá trị cần tìm lớn hơn giá trị của vị trí giữa) thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn ........ (4) của dãy.
Bước 5. Lặp lại từ Bước 1 đến Bước 5 cho đến vùng tìm kiếm không khi còn phần tử nào (Bước 1) hoặc tìm thấy giá trị cần tìm (Bước 3).
Câu 5: Từ thích hợp để điền vào vị trí (1) là
A. giá trị cần tìm xuất hiện ở vị trí giữa
B. nửa sau
C. “Không tìm thấy”
D. nửa trước
Câu 6: Từ thích hợp để điền vào vị trí (2) là
A. giá trị cần tìm xuất hiện ở vị trí giữa
B. nửa sau
C. “Không tìm thấy”
D. nửa trước
Câu 7: Từ thích hợp để điền vào vị trí (3) là
A. giá trị cần tìm xuất hiện ở vị trí giữa
B. nửa sau
C. “Không tìm thấy”
D. nửa trước
Câu 8: Từ thích hợp để điền vào vị trí (4) là
A. giá trị cần tìm xuất hiện ở vị trí giữa
B. nửa sau
C. “Không tìm thấy”
D. nửa trước
Câu 9: Bao nhiêu bước cần cho thuật toán tìm kiếm nhị phân để tìm thấy "Mai" trong danh sách [Hoa", "Lan”, ”Ly”, ”Mai”, ”Phong”, ”Vi”]?
A. 1.
B. 2.
C. 3.
D. 4.
Câu 10: Trong trường hợp nào sau đây sử dụng thuật toán tìm kiếm nhị phân sẽ phù hợp?
A. Tìm một số trong một danh sách.
B. Tìm một từ tiếng Anh trong quyển từ điển.
C. Tìm tên một bài học trong quyển sách.
D. Tìm tên một nước trong danh sách.
Câu 11: Điều kiện lặp của thuật toán tìm kiếm nhị phân là gì?
A. Chưa tìm thấy phần tử cần tìm.
B. Chưa hết danh sách.
C. Chưa tìm thấy phần tử cần tìm hoặc chưa hết danh sách.
D. Chưa tìm thấy phần tử cần tìm và chưa hết danh sách.
Câu 12: Khi so sánh giá trị cần tìm với giá trị của vị trí giữa, nếu giá trị cần tìm nhỏ hơn giá trị giữa thì:
A. Tìm trong nửa đầu của danh sách.
B. Tìm trong nửa sau của danh sách.
C. Dừng lại.
D. Tìm trong nửa đầu hoặc nửa sau của danh sách.
Câu 13: Cách diễn đạt nào đúng về hoạt động của thuật toán tìm kiếm nhị phân?
A. Tìm trên danh sách đã sắp xếp, bắt đầu từ đầu danh sách, cho đến khi không tìm thấy hoặc hết danh sách.
B. Tìm trên danh sách đã sắp xếp, bắt đầu từ giữa danh sách, cho đến khi không tìm thấy hoặc hết danh sách.
C. Tìm trên danh sách bất kì, bắt đầu từ giữa danh sách, cho đến khi không tìm thấy hoặc hết danh sách.
D. Tiến trên danh sách bất kì, bắt đầu từ đầu danh sách, cho đến khi không tìm thấy hoặc hết danh sách.
Câu 14: Lợi ích của việc sắp xếp trong tìm kiếm là gì?
A. Giúp tìm kiếm chính xác hơn.
B. Giúp tìm kiếm nhanh hơn.
C. Giúp tìm kiếm đầy đủ hơn.
D. Cả A, B và C.
Câu 15: Điều gì xảy ra khi thuật toán tìm kiếm nhị phân không tìm thấy giá trị cần tìm trong danh sách?
A. Tiếp tục tìm kiếm và không bao giờ kết thúc.
B. Thông báo "Tìm thấy" và tiếp tục kiểm tra xem còn phần tử nào khác không.
C. Thông báo "Tìm thấy" và kết thúc.
D. Thông báo "Không tìm thấy" và kết thúc.
Bài viết liên quan: Đề thi giữa học kì 1 môn Tin học lớp 7 cập nhật mới nhất
Trên đây là toàn bộ nội dung bài viết của Luật Minh Khuê về: Em tìm một từ tiếng Anh trong quyển từ điển theo cách nào? Xin cảm ơn quý bạn đọc đã quan tâm theo dõi!
