? mục 1

Trả lời câu hỏi mục 1 trang 74 SGK 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àn♔g hơn không?

Phương pháp giải:

Dựa vào sự hiểu biết của bản thân

Lời giải chi tiết:

Để 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.

Hoạt động 2

Trả lời câu hỏi Hoạt động 1 trang 75 SGK 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ôn🐼g?

Phương pháp giải:

- Quan sát Hình 15.1

- Thuật toán tìဣm kiếm tuần tự: tìm kiếm lần lượt từꦦ đầu danh sách cho đến khi tìm được

- Thuật toán tìm kiếm nhị phân: so 🌸sánh giá trị ở giữa danh sách đã được sắp xếp với giá trị cần tìm.

Lời giải chi tiết:

1. Thuật toán tìm kiếm tuần tự phải thực hiện 3 bước để tìm ꦏkhách hàng tên Trúc như ở Hình 15.1.

- Số bước thực hiện của thuật toán tìm kiếm tuần tự nhiều hơn so với số bước thực hiện thuật toán tìm kiếm nhị phân vì thuật toán tìm kiếm tuần tự sẽ tìm kiếm lần lượt từ đầu danh sách cho đến khi tìm được tên của bạn Trúc nên sẽ mất 8 lần lặp, còn thuật toán tìm kiếm nhị phân so sánh giá trị ở giữa danh s𝓀🔥ách nên sẽ nhanh chóng hơn.

2. 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 phải được sắp xếp theo quy tắc (theo bảng chữ cái, số thứ t🍌ự tăng dần🍎 hoặc giảm dần). 

Nếu♒ không thỏa mãn điều kiện đó, thuật toán tìm kiếm nhị phân không thực hiện được.

? mục 2

Trả lời câu hỏi mục 2 trang 76 SGK Tin học 7

Em hãy viết các bước thực hiện thuật t🌼oá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.

Phương pháp giải:

Thuật toán tìm kiếm nhị phân:

- Thực hiện trên danh sách đã đ🌟ược sắp xếp. Bắt đầu từ vị trí ở giữa danh sách.

- Tại mỗi bước, so sánh giá trị cần tìm với giá trị của vị trí giữa dan꧅h sách, nếu lớn hơn thì tìm trong nửa sau của danh sách, nếu nhỏ hơn thì tìm trong nửa trước của danh sách, nếu bằng thì dừng lại.

- Chừng nào chưa ꦍtìm thấy và chưa hết danh sách thì còn tìm t🅷iếp.

Lời giải chi tiết:

- Bước 1: Xé♋t vị trí ở giữa củ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ì sau bước💙 2 đã tìm thấy tên khách hàng nên tไhuật toán kết thúc.

? mục 3

Trả lời câu hỏi mục 3 trang 77 SGK 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.

Phương pháp giải:

Dựa vào kiến thức thực tế của bản thân

Lời giải chi tiết:

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à tr🧔a từ điển Tiếng Anh.

Luyện tập

Trả lời câu hỏi Luyện tập trang 77 SGK Tin học 7

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

Bolivia, A꧟lbania, 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 da💯nh 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 tജhực hiện tìm kiếm ở Câu 2 phần Luyện tập của bài 14.

Phương pháp giải:

Thuật toán tìm kiếm nhị phân:

- Thực hiện trên danh sách đã đ🦂ꦑược sắp xếp. Bắt đầu từ vị trí ở giữa danh sách.

- Tại mỗi bước, so sánh giá trị cần tìm 🦩với⛄ giá trị của vị trí giữa danh sách, nếu lớn hơn thì tìm trong nửa sau của danh sách, nếu nhỏ hơn thì tìm trong nửa trước của danh sách, nếu bằng thì dừng lại.

- Chừng nào chưa tìm t🌠hấy và c𒀰hưa hết danh sách thì còn tìm tiếp.

Lời giải chi tiết:

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 tron🌱g 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

- Vì sau bước 3 đã tìm ♏thấy tên nước nên thuật toán kết thúc.

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 kౠi🎐ếm ở Câu 2 phần Luyện tập của bài 14.

2. 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 đó.

Phương pháp giải:

Vận dụng kiến thức thực tế và thuật✱ toántìm kiếm nhị phân để giải quyết

Lời giải chi tiết:

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🐬ì sau bước 2 đã tìm thấy tên 🅠học sinh nên thuật toán kết thúc.

Vận dụng

Trả lời câu hỏi Vận dụng trang 77 SGK 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 đó?

Phương pháp giải:

Dựa vào kiến thứ🧜c về thuật toán tìm kiếm em đã học

Lời giải chi tiết:

Em tìm một từ tiếng Anh trong quyển từ điển bằng cách chia đổi quyển từ điển, tìm một từ bất kì ở giữa quyển từ điển và so sánh với từ cần tìm. Nếu tìm thấy từ đó thì sẽ kết thúc việc tìm kiếm. Nếu chưa em lại tiếp tục chia quyển từ điển t𒀰heo nửa thích hợp, đến khi nào tìm được từ cần tìm thì kết thúc. Em dùng cách này vì nhanh chóng và thuận tiện hơn là tìm kജiếm từng từ trong bảng chữ cái.

Lý thuyết

>> Xem chi tiết: Lý th෴uyết thuật toán tìm kiếm nhị phân - Tin học 07