Nội dung chính tin học 7 cánh diều Chủ đề F Bài 2: tìm kiếm nhị phân

Hệ thống kiến thức trọng tâm Chủ đề F Bài 2: tìm kiếm nhị phân sách tin học 7 cánh diều. Với các ý rõ ràng, nội dung mạch lạc, đi thẳng vào vấn đề hi vọng người đọc sẽ nắm trọn kiến thức trong thời gian rất ngắn. Nội dung chính được tóm tắt ngắn gọn sẽ giúp thầy cô ôn tập củng cố kiến thức cho học sinh. Bộ tài liệu có file tải về. Mời thầy cô kéo xuống tham khảo

Xem: => Giáo án tin học 7 cánh diều (bản word)

BÀI 2: TÌM KIẾM NHỊ PHÂN

 

1. CHIA ĐÔI DẦN ĐỂ TÌM KIẾM MỘT SỐ TRONG DÃY SỐ ĐÃ SẮP XẾP THỨ TỰ

- Ý tưởng: chia đôi dần để tìm một số trong một dãy số

- Ví dụ: Tìm x = 44 trong dãy 8 phần tử đã sắp xếp thứ tự không giảm

 

a1

a2

a3

a4

a5

a6

a7

a8

Xuất phát

6

12

18

42

44

55

67

94

Bước 1

   

42

44

55

67

94

Bước 2

    

44

55

  

Bươc 3

    

44

   

- Giải thích:

          + 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 = 44, tiếp theo chỉ cần 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 con từ a5 đến a8.

          + 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 sau chắc chắn không chứa x = 44, tiếp theo chỉ cần tìm trong nửa đầu của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con chỉ còn một số a5

=> Phạm vi tìm kiếm chỉ còn 1 số kết thúc thuật toán với kết quả: Tìm thấy x ở vị trí thứ 5

2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

- Thuật toán tìm kiếm nhị phân là thuật toán tìm kiếm x trong dãy đã sắp thứ tự với ý tưởng chia đôi dần để giảm nhanh phạm vi tìm kiếm.

- Mô tả thuật toán:

Text

Description automatically generated

- Chú ý: Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp thứ tự

3. PHƯƠNG PHÁP “CHIA ĐỂ TRỊ” VỚI BÀI TOÁN TÌM KIẾM

- Để giải một bài toán lớn, người ta tìm cách chia bài toán ban đầu ra thành các bài toán nhỏ hơn rồi giải những bài toán nhỏ hơn sẽ dễ hơn. Cách làm này gọi là “chia để trị”

- Thuật toán tìm kiếm nhị phân chia bài toán ban đầu thành hai bài toán con nhỏ hơn và chỉ phải tiếp tục giải một trong hai bài toán con đó. Áp dụng liên tiếp cách này cho đến khi nhận được kết quả.

 

 

=> Giáo án tin học 7 cánh diều bài 2: Tìm kiếm nhị phân (1 tiết)

Thông tin tải tài liệu:

Phía trên chỉ là 1 phần, tài liệu khi tải về là file word, có nhiều hơn + đầy đủ đáp án. Xem và tải: Kiến thức trọng tâm tin học 7 cánh diều - Tại đây

Tài liệu khác

Tài liệu của bạn

Tài liệu mới cập nhật

Tài liệu môn khác

Chat hỗ trợ
Chat ngay