Giải bài tập Tin học 7 Bài 1: Tìm kiếm nhị phân sách Cánh diều giúp các em học sinh lớp 7 có thêm nhiều tư liệu tham khảo, đối chiếu lời giải hay, chính xác để biết cách trả lời các câu hỏi trang 81→83.
Bạn đang đọc: Tin học 7 Bài 2: Tìm kiếm nhị phân
Tin học 7 Tìm kiếm nhị phân thuộc chủ đề F: Giải quyết vấn đề với sự trợ giúp của máy tính giúp các bạn học sinh nắm được kiến thức về chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự. Đồng thời biết cách trả lời các câu hỏi phần nội dung bài học trang 81, 82, 83. Vậy sau đây là nội dung chi tiết, mời các bạn cùng theo dõi.
Tin học 7 Bài 2: Tìm kiếm nhị phân
Khởi động Tin học 7 Bài 2 Cánh diều
Nếu phải tìm một số trong dãy đã sắp xếp theo thứ tự tăng dần hoặc giảm dần, em có cách nào tìm nhanh hơn tìm kiếm tuần tự không?
Gợi ý đáp án
Nếu phải tìm một số trong dãy đã sắp xếp theo thứ tự tăng dần hoặc giảm dần, chúng ta sẽ chia đôi dãy số để tìm kiếm nhanh hơn.
Vận dụng Tin học 7 Bài 2 Cánh diều
Em hãy mô tả cách tra cứu, tìm giải nghĩa một từ trong từ điển. Có thể gọi cách tìm đó là áp dụng thuật toán tìm kiếm nhị phân không?
Gợi ý đáp án
Cách tra cứu, tìm giải nghĩa một từ trong từ điển:
- Bước 1: Xác định từ cần tìm là gì. Ví dụ, chúng ta muốn tìm từ “hat”.
- Bước 2: Chia đổi cuốn từ điển thành 2 phần bằng nhau, chọn 1 từ bất kì nằm ở giữa cuốn từ điển. Ví dụ, chọn từ “mother”. Vì cuốn từ điển sắp xếp theo bảng chữ cái nên chữ h sẽ đứng trước chữ m, vậy tiếp theo ta chỉ cần tìm trong nửa đầu của cuốn từ điển.
- Bước 3: Ta lại tiếp tục chia đổi nửa đầu cuốn từ điển và thực hiện tương tự như bước 2. Chọn một từ nằm ở giữa, ví dụ là từ “go”. Vì chữ g đứng trước chữ h nên phạm vi tìm kiếm sẽ từ chữ “go” cho đến chữ “mother”.
- Bước 4: Chúng ta tiếp tục chia đôi phạm vi từ chữ “go” cho đến chữ “mother” và thực hiện tương tự bước 3 cho đến khi ta tìm được từ “hat” thì ta kết thúc việc tìm kiếm.
Cách tìm trên có thể gọi là áp dụng thuật toán tìm kiếm nhị phân.
Tự kiểm tra Tin học 7 Cánh diều Bài 2
Câu 1. Hãy mô tả quy trình chia đổi dần để thực hiện tìm kiếm nhị phân.
Câu 2. Theo em, có phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân không? Giải thích tại sao.
Gợi ý đáp án
Câu 1. Quy trình chia đổi dần để thực hiện tìm kiếm nhị phân là:
Gọi số cần tìm kiếm là x, gọi dãy số đã sắp thứ tự là a1 cho đến an.
Bước 1: Chia dãy thành 2 phần bằng nhau và so sánh giá trị cần tìm với giá trị nằm giữa 2 phần đó (gọi là an/2). Có thể xảy ra hai trường hợp:
- Nếu giá trị cần tìm lớn hơn (x > an/2), ta xét nửa sau của dãy (từ an/2 đến an).
- Nếu giá trị cần tìm nhỏ hơn (x n/2), thực hiện xét nửa trước của dãy (từ a1 đến an/2).
Bước 2: Sau đó, ta xét lại phạm vi tìm kiếm phù hợp. Nếu x = an/2, ta xác định được vị trí của số cần tìm và kết thúc tìm kiếm.
Bước 3: Tiếp tục thực hiện 2 bước trên cho đến khi tìm được giá trị cần tìm. Nếu không tìm được x ta suy ra trong dãy không tồn tại số có giá trị như đề bài yêu cầu.
Câu 2. Không phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân vì chỉ có dãy số có thứ tự thì mới chia đôi và xác định phạm vi tìm kiếm để tìm ra kết quả chính xác được, còn dãy không có thứ tự thì không thể áp dụng thuật toán tìm kiếm nhị phân.
