Giải SGK Tin học 7 Bài 2: Tìm kiếm nhị phân| Cánh diều
Bài 2: Tìm kiếm nhị phân sách Cánh diều bao gồm đáp án chi tiết cho từng phần, từng mục trong SGK Tin học lớp 7, cho các em học sinh tham khảo luyện giải Tin học 7, chuẩn bị cho các bài học trên lớp được tốt hơn. Sau đây mời các bạn tham khảo chi tiết.
Chủ đề: Chủ đề F: Giải quyết vấn đề với sự trợ giúp của máy tính 7 (CD)
Môn: Tin học 7
Sách: Cánh diều
Thông tin:
Tác giả:
Thông tin :
Chủ đề:
Chủ đề F: Giải quyết vấn đề với sự trợ giúp của máy tính 7 (CD)
Môn:
Sách:
Tác giả:
Preview text:
Khởi động trang 81 Tin học lớp 7:
Nếu phải tìm một số trong dãy đã sắp xếp theo thứ tự tăng 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? Hướng dẫn:
Em sẽ chia đôi dãy làm hai phần để tìm kiếm nhanh hơn.
Hoạt động trang 81 Tin học lớp 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 thẻ lên xem mà vẫn trả lời được câu hỏi. Bạn Thành An cho rằng chỉ cần
không quá 3 lần lật thẻ là trả lời được. Em đồng ý với Thành An không? Vì sao? Hướng dẫn:
Em đồng ý với Thành An vì:
- Dãy số đã được sắp xếp không giảm, ta chia đôi dãy số, loại bỏ nửa dãy chắc
chắn không chứa phần tử cần tìm, chỉ tìm kiếm trong nửa dãy còn lại. Nửa còn
lại ta làm tương tự như trước.
Luyện tập trang 83 Tin học lớp 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.
Có thể trình bày thông tin mô tả dưới dạng bảng như bài học. Hướng dẫn: Tìm x = 60: A1 A2 A3 A4 A5 A6 A7 A8 Xuất phát 5 11 18 39 41 52 63 70 Bước 1 39 52 Bước 2 52
- Chia đôi lần 1. Phạm vi tìm kiếm từ dãy A1 đến A8. Lấy A4 là số có vị trí giữa
dãy. Vì x >A4 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần
tìm trong nửa sau cảu dãy. Phạm vi tìm kiếm từ A5 đến A8.
- Chia đôi lần 2. Phạm vi tìm kiếm từ dãy A5 đến A8. Lấy A6 có vị trí giữa dãy.
Vì x>A6 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần tìm
trong nửa sau của dãy. Phạm vi tìm kiếm từ A7 đến A8.
- Chia đôi lần 3. Phạm vi tìm kiếm từ A7 đến A8. Lấy A7 có vị trị giữa dãy. Vì x
Kết thúc thuật toán: Không tìm thấy x có trong dãy.
Vận dụng trang 83 Tin học lớp 7:
Em hãy mô tả cách tra cứu, tìm một từ trong từ điển. Có thể gọi cách tìm kiếm
đó là áp dụng thuật tìm kiếm nhị phân không? Hướng dẫn:
Giả sử cuốn từ điển có khoảng 300 nghìn mục từ. Để dễ tính toán, ta coi là từ
điển có 218 = 262144 mục từ và được sắp xếp theo vần bảng chữ cái. Nếu tra
tìm một từ trong từ điển bằng cách tìm kiếm nhị phân thì sau một lần chia đôi,
phạm vi tìm kiếm giảm đi chỉ còn một nửa, tức là còn 217 = 131072 mục từ. Dễ
thấy rằng nếu theo thuật toán tìm kiếm nhị phân, ta phải chia đôi 17 lần cho
đến khi phạm vi kiếm là 20 = 1 mục từ mới tìm thấy. Nên có thể gọi đây là tìm kiếm nhị phân.
Câu hỏi tự kiểm tra
Câu 1 trang 83 Tin học lớp 7: Hãy mô tả quy trình chia đôi dần để thực hiện tìm kiếm nhị phân? Hướng dẫn:
Mô tả quy trình chia đôi dần để thực hiện tìm kiếm nhị phân:
Khi bắt đầu thuật toán, phạm vi tìm kiếm là dãy đã cho ban đầu. Lấy phần tử
đứng giữa để 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.
+ Trái 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ừ đó xác định được phạm vi tìm kiếm ở bước tiếp theo là nửa còn lại.
Tiếp theo, việc tìm x trong phạm vi tìm kiếm (tức là nửa dãy còn lại) sẽ được
lặp lại cho cho đến khi tìm thấy hoặc độ dài cần tìm chỉ còn bằng 1 và so sánh
được ngay để biết tìm thấy x hay không.
Câu 2 trang 83 Tin học lớp 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. Hướng dẫn:
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.