Giải Tin học 7 Kết nối tri thức Bài 15: Thuật toán tìm kiếm nhị phân

Giải Tin học 7 Kết nối tri thức Bài 15: Thuật toán tìm kiếm nhị phân ngắn gọn, hay nhất bám sát nội dung Sách giáo khoa Tin học 7 theo chương trình Sách mới. Bài soạn bao gồm 7 câu hỏi được trả lời chính xác bằng 2 cách, giúp học sinh hiểu kĩ hơn về bài học

Câu hỏi 1 trang 74 Tin học 7

Việc kinh doanh mở rộng, số lượng khách hàng của cửa hàng bán giống cây trồng nhà An lên đến hàng trăm người. Việc tìm kiếm tên khách hàng trong danh sách thật khó khăn. Em có gợi ý gì cho bạn An để tìm kiếm được dễ dàng hơn không?

Lời giải

Để tìm kiếm tên khách hàng trong danh sách được dễ dàng hơn, bạn An nên sắp xếp tên khách hàng theo thứ tự trong bảng chữ cái.

Câu hỏi trang 76 Tin học 7

Em hãy viết các bước thực hiện thuật toán tìm kiếm nhị phân để tìm khách hàng tên "Hòa" trong danh sách ở Hình 15.1.

Lời giải

Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí số 5

Vì sau bước 2 đã tìm thấy tên khách hàng nên thuật toán kết thúc.

Hoạt động 2 trang 77 Tin học 7

1. 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 khách hàng tên Trúc như ở 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 thuật toán tìm kiếm nhị phân.

2. 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 thỏa mãn điều kiện gì? Nếu không thỏa 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?

Lời giải

1. Thuật toán tìm kiếm tuần tự cần 3 bước để tìm khách hàng tên Trúc như trong Hình 15.1. So với tìm kiếm nhị phân, tìm kiếm tuần tự chậm hơn vì nó kiểm tra từng phần tử từ đầu đến cuối mà tìm kiếm nhị phân chia đôi danh sách nên rất nhanh

2. Để thực hiện tìm kiếm nhị phân danh sách khách hàng phải được sắp xếp theo thứ tự (chữ cái hoặc số). Nếu không sắp xếp thuật toán tìm kiếm nhị phân sẽ không hoạt động.

Câu hỏi trang 77 Tin học 7

 Em hãy nêu ví dụ trong thực tế cho thấy mối liên quan giữa sắp xếp và tìm kiếm.

Lời giải

Ví dụ trong thực tế cho thấy mối liên quan giữa sắp xếp và tìm kiếm là tra từ điển Tiếng Anh.

Luyện tập 1 trang 77 Tin học 7

Cho danh sách tên các nước sau đây:

Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greendland, 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.

b) Em hãy liệt kê các bước tìm kiếm tên nước Iceland trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân.

c) Em hãy so sánh số bước thực hiện tìm kiếm ở phần b với số bước thực hiện tìm kiếm ở Câu 2 phần Luyện tập của bài 14.

Lời giải

a) Sắp xếp danh sách tên các nước theo thứ tự trong bảng chữ cái: Albania, Bolivia, Canada, Germany, Greendland, Iceland, Portugal, Scotland, Vietnam

b) Các bước tìm kiếm tên nước Iceland trong 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 dãy, đó là vị trí số 5

Bước 2: Xét vị trí ở giữa của nửa sau của dãy là vị trí số 7

Bước 3: Vì nửa trước của dãy chỉ còn một tên, đó là vị trí số 6

c) Số bước thực hiện tìm kiếm ở phần b ít hơn so với số bước thực hiện tìm kiếm ở Câu 2 phần Luyện tập của bài 14.

Luyện tập 2 trang 77 Tin học 7

Em hãy cho ví dụ một bài toán tìm kiếm trong thực tế mà có thể thực hiện bằng thuật toán tìm kiếm nhị phân? Hãy thực hiện thuật toán tìm kiếm nhị phân để giải quyết bài toán đó.

Lời giải

Ví dụ một bài toán tìm kiếm trong thực tế: Giáo viên muốn tìm tên bạn Chung trong danh sách lớp sau:

Các bước thực hiện thuật toán tìm kiếm nhị phân cho bài toán trên:

Bước 1: Xét vị trí ở giữa dãy, đó là vị trí số 5

Bước 2: Xét vị trí ở giữa của nửa đầu của dãy là vị trí số 3

Vận dụng trang 77 Tin học 7

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 đó?

Lời giải

Em tìm từ tiếng Anh trong từ điển bằng cách mở giữa sách và so sánh từ giữa với từ cần tìm. Nếu chưa đúng em sẽ tiếp tục chia đôi phần cần thiết và lặp đi lặp lại cho đến khi tìm thấy. Phương pháp này giúp em tìm nhanh hơn và dễ dàng hơn rất nhiều so với việc tra từng từ theo thứ tự.