Danh mục bài soạn

Giải tin học 7 cánh diều bài 2 Tìm kiếm nhị phân

Hướng dẫn học môn Tin học 7 sách mới cánh diều. Dưới đây là lời giải chi tiết bài 2: Tìm kiếm nhị phân. Từng bài tập được giải chi tiết, rõ ràng, dễ hiểu. Hi vọng, hocthoi.net sẽ hỗ trợ các em trong quá trình học tập, giúp các em ngày càng tiến bộ hơn.

KHỞI ĐỘNG

Câu hỏi. 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?

Lời giải:

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.

1. Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự

Câu hỏi. 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 một thẻ lên xem mà vẫn trả lời được câu hỏi. Bạn Thanh An cho răng chỉ cần không quá ba lần lật thẻ là trả lời được. Em đồng ý với Thanh An không? Vì sao?

Lời giải:

Em đồng ý với ý kiến của bạn Thanh An vì chúng ta chỉ cần chia đôi dần dãy số đã sắp thứ tự và lần lượt tìm kiếm trong phạm vi phù hợp để tìm ra kết quả mà chúng ta mong muốn thì chỉ cần 3 lần là có thể tìm ra kết quả.

LUYỆN TẬP

Câu hỏi. 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.

Gợi ý: Có thể trình bày thông tin mô tả dưới dạng bảng như trong bài học.

Lời giải:

Các bước tìm kiếm nhị phân để tìm kiếm x = 60 trong dãy trên:

 

a1

a2

a3

a4

a5

a6

a7

a8

Xuất phát

5

11

18

39

41

52

63

70

Bước 1

    

41

52

63

70

Bước 2

    

41

52

  

Bước 3

        
  • Bước 1: Chia đổi lần 1
    • Phạm vi tìm kiếm là dãy từ 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 tìm trong nửa sau của dãy.
    • Như vậy, phạm vi tìm kiếm tiếp theo là dãy từ a5 đến a8.
  • Bước 2: Chia đôi lần 2
    • Phạm vi tìm kiếm là dãy từ a5 đến a8.
    • Lấy a6 là số 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 tìm trong nửa sau của dãy.
    • Như vậy, phạm vi tìm kiếm tiếp theo là dãy từ a7 đến a8.
  • Bước 3: Như vậy, phạm vi tìm kiếm chỉ còn 2 số.
    • Vì x<a7 nên x không nằm ở trong dãy này.
    • Kết luận: Không có x trong dãy.

VẬN DỤNG

Câu hỏi. 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?

Lời giải:

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

Câu hỏi 1. Hãy mô tả quy trình chia đổi dần để thực hiện tìm kiếm nhị phân.

Lời giải:

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 hỏi 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.

Lời giải:

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.
  • 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.

Từ khóa tìm kiếm google:

giải sgk tin học 7 sách mới, giải tin học 7 cánh diều, giải tin học 7 CD bài 2, giải bài tìm kiếm nhị phân
Phần trên, hocthoi.net đã soạn đầy đủ lý thuyết và bài tập của bài học: Giải tin học 7 cánh diều bài 2 Tìm kiếm nhị phân . Bài học nằm trong chuyên mục: Giải tin học 7 cánh diều. Phần trình bày do Quỳnh Chi tổng hợp và thực hiện giải bài. Nếu có chỗ nào chưa rõ, có phần nào muốn hiểu rộng thêm, bạn đọc vui lòng comment bên dưới. Ban biên tập sẽ giải đáp giúp các bạn trong thời gian sớm nhất.

Bài soạn các môn khác

Bình luận