Giải Tin học 7 Bài 1: Tìm kiếm nhị phân | Cánh diều

Giải bài tập Tin học 7 Bài 1: Tìm kiếm nhị phân sách Cánh diều giúp các em học sinh lớp 7 có thêm nhiều tư liệu tham khảo, đối chiếu lời giải hay, chính xác để biết cách trả lời các câu hỏi trang 81→83.

51 26 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

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:

2 trang 7 tháng trước

Tác giả:

Profile Thanh Hoa
Khởi động Tin học 7 Bài 2 Cánh diều
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?
Gợi ý đáp án
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, chúng
ta sẽ chia đôi dãy số để tìm kiếm nhanh hơn.
Vận dụng Tin học 7 Bài 2 Cánh diều
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?
Gợi ý đáp án
Cách tra cứu, tìm giải nghĩa một từ trong từ điển:
Bước 1: Xác định từ cần tìm là gì. Ví dụ, chúng ta muốn tìm từ "hat".
Bước 2: Chia đổi cuốn từ điển thành 2 phần bằng nhau, chọn 1 từ bất kì nằm ở
giữa cuốn từ điển. Ví dụ, chọn từ "mother". Vì cuốn từ điển sắp xếp theo bảng
chữ cái nên chữ h sẽ đứng trước chữ m, vậy tiếp theo ta chỉ cần tìm trong nửa
đầu của cuốn từ điển.
Bước 3: Ta lại tiếp tục chia đổi nửa đầu cuốn từ điển và thực hiện tương tự như
bước 2. Chọn một từ nằm ở giữa, ví dụ là từ "go". Vì chữ g đứng trước chữ h
nên phạm vi tìm kiếm sẽ từ chữ "go" cho đến chữ "mother".
Bước 4: Chúng ta tiếp tục chia đôi phạm vi từ chữ "go" cho đến chữ
"mother" và thực hiện tương tự bước 3 cho đến khi ta tìm được từ "hat" thì ta
kết thúc việc tìm kiếm.
Cách tìm trên có thể gọi là áp dụng thuật toán tìm kiếm nhị phân.
Tự kiểm tra Tin học 7 Cánh diều Bài 2
Câu 1. Hãy mô tả quy trình chia đổi dần để thực hiện tìm kiếm nhị phân.
Câu 2. 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.
Gợi ý đáp án
Câu 1. Quy trình chia đổi dần để thực hiện tìm kiếm nhị phân là:
Gọi số cần tìm kiếm là x, gọi dãy số đã sắp thứ tự là a
1
cho đến a
n
.
Bước 1: Chia dãy thành 2 phần bằng nhau và so sánh giá trị cần tìm với giá trị nằm
giữa 2 phần đó (gọi là a
n/2
). Có thể xảy ra hai trường hợp:
Nếu giá trị cần tìm lớn hơn (x > a
n/2
), ta xét nửa sau của dãy (từ a
n/2
đến a
n
).
Nếu giá trị cần tìm nhỏ hơn (x < a
n/2
), thực hiện xét nửa trước của dãy (từ a
1
đến a
n/2
).
Bước 2: Sau đó, ta xét lại phạm vi tìm kiếm phù hợp. Nếu x = a
n/2,
ta xác định được vị
trí của số cần tìm và kết thúc tìm kiếm.
Bước 3: Tiếp tục thực hiện 2 bước trên cho đến khi tìm được giá trị cần tìm. Nếu
không tìm được x ta suy ra trong dãy không tồn tại số có giá trị như đề bài yêu cầu.
Câu 2. Không 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 vì chỉ có dãy số có thứ tự thì mới chia đôi và xác định phạm vi tìm
kiếm để tìm ra kết quả chính xác được, còn dãy không có thứ tự thì không thể áp dụng
thuật toán tìm kiếm nhị phân.
| 1/2
| | Tải xuống

Có thể bạn quan tâm:

Preview text:


Khởi động Tin học 7 Bài 2 Cánh diều
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? Gợi ý đáp án
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, chúng
ta sẽ chia đôi dãy số để tìm kiếm nhanh hơn.
Vận dụng Tin học 7 Bài 2 Cánh diều
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? Gợi ý đáp án
Cách tra cứu, tìm giải nghĩa một từ trong từ điển:
 Bước 1: Xác định từ cần tìm là gì. Ví dụ, chúng ta muốn tìm từ "hat".
 Bước 2: Chia đổi cuốn từ điển thành 2 phần bằng nhau, chọn 1 từ bất kì nằm ở
giữa cuốn từ điển. Ví dụ, chọn từ "mother". Vì cuốn từ điển sắp xếp theo bảng
chữ cái nên chữ h sẽ đứng trước chữ m, vậy tiếp theo ta chỉ cần tìm trong nửa
đầu của cuốn từ điển.
 Bước 3: Ta lại tiếp tục chia đổi nửa đầu cuốn từ điển và thực hiện tương tự như
bước 2. Chọn một từ nằm ở giữa, ví dụ là từ "go". Vì chữ g đứng trước chữ h
nên phạm vi tìm kiếm sẽ từ chữ "go" cho đến chữ "mother".
 Bước 4: Chúng ta tiếp tục chia đôi phạm vi từ chữ "go" cho đến chữ
"mother" và thực hiện tương tự bước 3 cho đến khi ta tìm được từ "hat" thì ta
kết thúc việc tìm kiếm.
Cách tìm trên có thể gọi là áp dụng thuật toán tìm kiếm nhị phân.
Tự kiểm tra Tin học 7 Cánh diều Bài 2
Câu 1. Hãy mô tả quy trình chia đổi dần để thực hiện tìm kiếm nhị phân.
Câu 2. 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. Gợi ý đáp án
Câu 1. Quy trình chia đổi dần để thực hiện tìm kiếm nhị phân là:
Gọi số cần tìm kiếm là x, gọi dãy số đã sắp thứ tự là a1 cho đến an.
Bước 1: Chia dãy thành 2 phần bằng nhau và so sánh giá trị cần tìm với giá trị nằm
giữa 2 phần đó (gọi là an/2). Có thể xảy ra hai trường hợp:
 Nếu giá trị cần tìm lớn hơn (x > an/2), ta xét nửa sau của dãy (từ an/2 đến an).
 Nếu giá trị cần tìm nhỏ hơn (x < an/2), thực hiện xét nửa trước của dãy (từ a1 đến an/2).
Bước 2: Sau đó, ta xét lại phạm vi tìm kiếm phù hợp. Nếu x = an/2, ta xác định được vị
trí của số cần tìm và kết thúc tìm kiếm.
Bước 3: Tiếp tục thực hiện 2 bước trên cho đến khi tìm được giá trị cần tìm. Nếu
không tìm được x ta suy ra trong dãy không tồn tại số có giá trị như đề bài yêu cầu.
Câu 2. Không 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 vì chỉ có dãy số có thứ tự thì mới chia đôi và xác định phạm vi tìm
kiếm để tìm ra kết quả chính xác được, còn dãy không có thứ tự thì không thể áp dụng
thuật toán tìm kiếm nhị phân.