Lời giải bài tập Tin học lớp 7 Bài 2: Tìm kiếm nhị phân sách Cánh diều hay, ngắn gọn sẽ giúp học sinh dễ dàng trả lời câu hỏi Tin học 7 Bài 2 từ đó học tốt môn Tin 7.

Giải bài tập Tin học lớp 7 Bài 2: Tìm kiếm nhị phân

Khởi động trang 81 Tin học 7: 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?

Trả lời:

Em sẽ chia đôi dãy làm hai phần để tìm kiếm nhanh hơn.

1. Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự

Hoạt động trang 81 Tin học 7: Có 8 thẻ, mỗi thẻ có ghi một số nguyên trên đó. Tất cả các thẻ được sắp xếp thành dãy theo thứ tự không giảm của các số ghi trên đó và đặt sấp mặt ghi số xuống bàn để em không nhìn thấy. Cô giáo đọc một số, gọi là X chẳng hạn. Cần trả lời câu hỏi: Có hay không một thẻ ghi số X? Hãy sử dụng ít nhất số lần lật một thẻ lên xem mà vẫn trả lời được câu hỏi. Bạn Thanh An cho rằng chỉ cần không quá ba lần lật thẻ là trả lời được. Em đồng ý với Thanh An không? Vì sao?

Trả lời:

Em đồng ý với ý kiến của bạn Thanh An.

Vì khi ta chia đôi để tìm một số trong dãy thì ta có thể tìm được kết quả nhanh hơn.

Ta sẽ sắp xếp dãy theo thứ tự không giảm, sau đó chia đôi để tìm kiếm. Nên sẽ không tìm quá ba lần lật thẻ.

Luyện tập trang 83 Tin học 7: Cho dãy số 5, 11, 18, 39, 41, 52, 63, 70. Hãy mô tả diễn biến từng bước tìm kiếm nhị phân để tìm kiếm x = 60 trong dãy trên

Trả lời:

Tìm kiếm x = 60.

Bước 1. Ta sắp xếp dãy theo thứ tự không giảm.

Bước 2. Ta chia đôi dãy số để tìm x trong dãy. Ta sẽ chia ngay vị trí a₆ (a₆=52) vì x > a₆. Phạm vi tìm kiếm tiếp theo là từ a₇ đến a₈.

Bước 3. Khi đó phạm vi tìm kiếm chỉ có a₇ đến a₈ và ta thấy không có số nào bằng x. Kết thúc thuật toán không tìm thấy kết quả x.

Vận dụng trang 83 Tin học 7: 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?

Trả lời:

Cách tra cứu, tìm giải nghĩa từ điển:

Danh sách các giá trị dữ liệu không được sắp xếp và có thể được thay đổi bằng cách sử dụng các phương thức tích hợp sẵn. Từ điển được sử dụng để tạo ra một bản đồ cho các khóa (keys) độc nhất tới giá trị (values). Từ điển sẽ sắp xếp một tập các đối tượng (khóa) đến một tập các đối tượng là giá trị, do đó người sử dụng có thể tạo ra một danh sách các đối tượng không theo thứ tự. Các từ điển được tạo ra có thể biến đổi được, có nghĩa là chúng có thể được thay đổi tùy theo mục đích của người dùng.

Ta gọi cách tìm kiếm đó là thuật toán nhị phân.

Câu hỏi tự kiểm tra (trang 83)

Câu 1 trang 83 Tin học 7: Hãy mô tả quy trình chia đôi dần để thực hiện tìm kiếm nhị phân

Trả lời:

Bước 1. Sắp xếp dãy theo thứ tự không giảm.

Bước 2. Ta chia đôi dãy số để tìm x trong dãy.

Bước 3. Lấy phần tử đứng giữa dãy để so sánh với x.

Nếu phần tử đó chính là x thì kết luận đã tìm thấy x và kết thúc thuật toán.

Ngược lại, ta có thể xác định được x chắc chắn không có trong nửa đầu hay nửa sau của dãy. Từ đó ta xác định được phạm vi tìm kiếm và thực hiện tìm kiếm trong phạm vi nữa dãy còn lại, sẽ được lặp lại theo cách như thế cho đến khi tìm được kết quả.

Câu 2 trang 83 Tin học 7: 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.

Trả lời:

Theo em, chỉ thực hiện tìm kiếm nhị phân ở một số dãy số. Vì khi dãy có thứ tự thì mới áp dụng được tìm kiếm nhị phân.

Xem thêm các bài giải SGK Tin học lớp 7 Cánh diều hay, chi tiết khác:

Bài 1: Tìm kiếm tuần tự

Bài 2: Tìm kiếm nhị phân

Bài 3: Sắp xếp chọn

Bài 4: Sắp xếp nổi bọt

Bài 5 : Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp