Giải Tin học 7 Bài 15 (Kết nối tri thức): Thuật toán tìm kiếm nhị phân
Với soạn, giải bài tập Tin học lớp 7 Bài 15: Thuật toán tìm kiếm nhị phân sách Kết nối tri thức hay nhất, chi tiết sẽ giúp học sinh dễ dàng trả lời câu hỏi và làm bài tập Tin học 7 Bài 15.
Giải bài tập Tin học 7 Bài 15: Thuật toán tìm kiếm nhị phân
Video giải bài tập Tin học 7 Bài 15: Thuật toán tìm kiếm nhị phân
Trả lời:
Để việc tìm kiếm tên khách hàng được dễ dàng hơn, An cần soạn thảo danh sách khách hàng trên máy tính với tên khách hàng được sắp xếp theo thứ tự chữ cái. Giả sử An cần tìm địa chỉ của khách hàng tên là “Trúc” trong danh sách khách hàng. An không cần tìm từ đầu mà so sánh chữ cái đầu của tên chữ cái đầu của tên ở vị trí giữa danh sách. Nếu đúng tên thì tìm thấy và dừng lại, nếu chữ cái đầu của tên đứng sau chữ cái đầu tên giữa danh sách thì tìm ở nửa sau của danh sách, nếu đứng trước thì tìm ở nửa đầu của danh sách. Lặp lại quá trình đó cho đến khi tìm thấy hoặc hết danh sách.
1. Thuật toán tìm kiếm nhị phân
Hoạt động 1 trang 75 Tin học 7: Sắp xếp và tìm kiếm
Câu 1 trang 75 Tin học lớp 7: Em hãy cho biết thuật toán tìm kiếm tuần tự phải thực hiện bao nhiêu bước để tìm được khách hàng tên “Trúc” trong danh sách ở Hình 15.1? Em hãy so sánh số bước thực hiện của thuật toán tìm kiếm tuần tự với số bước thực hiện của thuật toán tìm kiếm nhị phân.
Trả lời:
Thuật toán tìm kiếm tuần tự phải thực hiện 8 lần để tìm được khách hàng tên “Trúc”. Thuật toán tìm kiếm nhị phân chỉ thực hiện 3 lần lần để tìm được khách hàng tên “Trúc”.
Câu 2 trang 75 Tin học lớp 7: Theo em trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần thoả mãn điều kiện gì? Nếu không thoả mãn điều kiện đó, thuật toán tìm kiếm nhị phân có thực hiện được không?
Trả lời:
Trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần sắp xếp theo thứ tự từ nhỏ đến lớn. Nếu không sắp xếp thứ tự từ nhỏ đến lớn thì thuật toán tìm kiếm nhị phân không thực hiện được.
Trả lời:
Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí số 5
So sánh “Hoà” và “Mai”. Vì “H” đứng trước “M” trong bảng chữ cái nên bỏ đi nữa sau danh sách.
Bước 2: Xét vị trí ở giữa của nửa đầu của dãy là vị trí số 3
So sánh “Hòa” và “Hòa”, vì hai giá trị bằng nhau nên thuật toán kết thúc.
Sau 2 bước đã tìm thấy tên khách hàng tên “Hoà” nên thuật toán kết thúc.
2. Sắp xếp và tìm kiếm
Hoạt động 2 trang 77 Tin học 7: Trò chơi tìm số
Câu hỏi trang 77 Tin học lớp 7: Chuẩn bị: Hai bạn chơi A, B và 10 tấm thẻ ghi 10 số khác nhau (các số đều nhỏ hơn 20). Ví dụ, 10 số trên các tấm thẻ là 2, 3, 5, 6, 8, 9, 11, 15, 16, 18. Giả sử A giữ 10 tấm thẻ và B là người tìm kiếm.
Yêu cầu: Bạn B 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 bạn A.
Cách chơi:
Bước 1. A úp lần lượt 10 chiếc thẻ lên bàn theo thứ tự các số từ bé đến lớn.
Bước 2. B cho A biết con số mình cần tìm.
Bước 3. B chọn tấm thẻ ở vị trí giữa.
Bước 4. A hé mở tấm thẻ và trả lời B bằng cách nói một trong ba cụm từ: “bằng nhau”, “lớn hơn” hoặc “bé hơn” tuỳ thuộc vào kết quả so sánh số bạn B cần tìm với số ở vị trí
giữa của dãy.
Bước 5. Tuỳ vào câu trả lời của A mà B chọn nửa dãy tiếp theo để tìm kiếm.
Bước 6. 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. Hoán đổi vị trí của A và B trong lượt chơi tiếp theo.
Trả lời:
Các em tìm 1 bạn chơi cùng mình.
Trả lời:
Trong thực tế trong quản lý học sinh, danh sách học sinh luôn được sắp xếp theo chữ cái đầu của tên để dễ tìm kiếm.
Luyện tập
Luyện tập 1 trang 77 Tin học lớp 7: Cho danh sách tên các nước sau đây:
Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greenland, Germany
a) Em hãy sắp xếp danh sách tên các nước theo thứ tự trong bảng chữ cái.
Trả lời:
a) Danh sách tên các nước theo thứ tự trong bảng chữ cái: Albania, Bolivia, Canada, Germany, Greenland, Iceland, Portugal, Scotland, Vietnam.
b) Các bước tìm kiếm tên nước Icelandtrong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân:
Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí thứ 5
So sánh “Greenland” và “Iceland” vì “G” đứng trước “I” trong bảng chữ cái nên bỏ đi nữa đầu danh sách.
Bước 2: Xét vị trí ở giữa của nữa sau của dãy, đó là vị trí thứ 7
So sánh Portugal và “Iceland” vì “P” đứng sau “I” trong bảng chữ cái nên bỏ đi nữa sau danh sách.
Bước 3: Xét vị trí ở giữa của dãy, đó là vị trí thứ 6
So sánh “Iceland” và “Iceland” vì hai giá trị bằng nhau nên thuật toán kết thúc.
Sau 3 bước đã tìm thấy tên nước “Iceland” nên thuật toán kết thúc.
Trả lời:
Ví dụ: Tìm tên một bạn trong danh sách lớp.
- Danh sách lớp, tên học sinh được sắp xếp theo thứ tự trong bảng chữ cái.
⇒ Để tìm tên một học sinh, chúng ta có thể thực hiện thuật toán tìm kiếm nhị phân để tìm kiếm.
- Hướng dẫn tìm tên bạn Nga, (giả sử trong lớp không có tên trùng nhau).
+ Chúng ta, xem xét từ vị trí giữa sách. So sánh tên cần tìm với tên ở vị trí xét.
Nếu kí tự đầu của tên đứng trước vần N thì tên cần tìm ở nửa sau danh sách.
Nếu kí tự đầu của tên đứng sau vần N thì tên cần tìm ở nửa trước của danh sách.
Nếu tên trùng nhau thì dừng lại.
+ Nếu chưa tìm thấy thì tiếp tục tìm như bước trên.
Vận dụng
Trả lời:
Em tìm một từ tiếng Anh trong quyển từ điển theo cách tìm kiếm nhị phân.
Giả sử cuốn từ điển có khoảng 300 nghìn mục từ. Nếu tìm kiếm tuần tự thì mất rất nhiều thời gian. Nếu tra 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.
Xem thêm lời giải bài tập Tin học lớp 7 Kết nối tri thức với cuộc sống hay, chi tiết khác:
Bài 3: Quản lí dữ liệu trong máy tính
Bài 4: Mạng xã hội và một số kênh trao đổi thông tin trên internet
Xem thêm các chương trình khác:
- Giải sgk Toán 7 – Kết nối tri thức
- Giải sbt Toán 7 – Kết nối tri thức
- Lý thuyết Toán 7 – Kết nối tri thức
- Giải VTH Toán 7 – Kết nối tri thức
- Chuyên đề dạy thêm Toán 7 cả 3 sách (2024 có đáp án)
- Giải sgk Lịch sử 7 – Kết nối tri thức
- Lý thuyết Lịch Sử 7 – Kết nối tri thức
- Giải sbt Lịch sử 7 – Kết nối tri thức
- Giải VTH Lịch sử 7 – Kết nối tri thức
- Soạn văn lớp 7 (hay nhất) – Kết nối tri thức
- Tác giả tác phẩm Ngữ văn lớp 7 – Kết nối tri thức
- Soạn văn lớp 7 (ngắn nhất) – Kết nối tri thức
- Tóm tắt tác phẩm Ngữ văn lớp 7 – Kết nối tri thức
- Bố cục tác phẩm Ngữ văn lớp 7 – Kết nối tri thức
- Nội dung chính tác phẩm Ngữ văn lớp 7 – Kết nối tri thức
- Văn mẫu lớp 7 – Kết nối tri thức
- Giải VTH Ngữ văn lớp 7 – Kết nối tri thức
- Giải sgk Địa Lí 7 – Kết nối tri thức
- Lý thuyết Địa Lí 7 – Kết nối tri thức
- Giải sbt Địa lí 7 – Kết nối tri thức
- Giải VTH Địa lí 7 – Kết nối tri thức
- Giải sgk Tiếng Anh 7 Global Success – Kết nối tri thức
- Giải sbt Tiếng Anh 7 Global Success - Kết nối tri thức
- Bài tập Tiếng Anh 7 Global success theo Unit có đáp án
- Trọn bộ Từ vựng Tiếng Anh 7 Global success đầy đủ nhất
- Ngữ pháp Tiếng Anh 7 Global success
- Giải sgk Giáo dục công dân 7 – Kết nối tri thức
- Lý thuyết GDCD 7 – Kết nối tri thức
- Giải sbt Giáo dục công dân 7 – Kết nối tri thức
- Giải vth Giáo dục công dân 7 – Kết nối tri thức
- Giải sgk Khoa học tự nhiên 7 – Kết nối tri thức
- Lý thuyết Khoa học tự nhiên 7 – Kết nối tri thức
- Giải sbt Khoa học tự nhiên 7 – Kết nối tri thức
- Giải sbt Hoạt động trải nghiệm lớp 7 - KNTT
- Giải sgk Hoạt động trải nghiệm 7 - KNTT
- Giải sgk Công nghệ 7 – Kết nối tri thức
- Lý thuyết Công nghệ 7 – Kết nối tri thức
- Giải sbt Công nghệ 7 – Kết nối tri thức
- Giải VTH Công nghệ 7 – KNTT
- Giải sgk Giáo dục thể chất 7 – Kết nối tri thức
- Giải sgk Âm nhạc 7 – Kết nối tri thức