Tải giáo án Powerpoint Tin học 7 CTST bài 13: Thuật toán tìm kiếm (2 tiết)

CHÀO MỪNG CÁC EM ĐẾN VỚI TIẾT HỌC HÔM NAY!

KHỞI ĐỘNG

Có 9 thẻ số, mỗi thẻ được ghi số ở một mặt và mặt còn lại không ghi gì. Đặt úp các thẻ số trên mặt bàn và xếp thành một dãy như sau:

Em hãy trao đổi với bạn để thực hiện tìm một số bất kì có trong dãy số ghi trên các thẻ ở trên hay không.

• Cách 1: Lật lần lượt từng thẻ số theo thứ tự cho đến khi tìm thấy hoặc đã lật hết các thẻ mà không tìm thấy.
• Cách 2: Lật từng thẻ số một cách ngẫu nhiên cho đến khi tìm thấy hoặc đã lật hết các thẻ mà không tìm thấy.
• Tuy nhiên, trường hợp có rất nhiều thẻ số mà mỗi lần lật một thẻ số rồi phải úp lại mới được lật thẻ tiếp theo. Điều này sẽ dẫn đến cần thực hiện tìm theo cách 1 để dễ thực hiện, dễ nhớ thẻ đã lật, thẻ chưa lật.

BÀI 13: THUẬT TOÁN TÌM KIẾM (2 Tiết)

NỘI DUNG BÀI HỌC

1. Thuật toán tìm kiếm tuần tự
2. Thuật toán tìm kiếm nhị phân
3. Thuật toán tìm kiếm tuần tự

Dựa vào nội dung thông tin mục 1 và hiểu biết của bản thân, em hãy:

• Lấy ví dụ về bài toán tìm kiếm trong cuộc sống.
• Chỉ ra đầu vào và đầu ra của bài toán tìm kiếm ở phần Khởi động.
• Đầu vào: Dãy số (được ghi trên các thẻ) và số cần tìm.
• Đầu ra: Thông báo vị trí tìm thấy hoặc thông báo không tìm thấy số cần tìm.

Quan sát Hình 2 và mô tả các bước của thuật toán tìm kiếm tuần tự để tìm một số trong dãy thẻ số ở phần Khởi động.

Thuật toán thực hiện lặp đi lặp lại việc duyệt từng thẻ số, vòng lặp sẽ kết thúc khi tìm thấy số cần tìm hoặc đã duyệt hết các thẻ số.

HOẠT ĐỘNG LÀM

1. Các số ghi trên mỗi thẻ Hình 1 lần lượt là: 26, 14, 24, 18, 15, 21, 19, 25, 12.

Em hãy tạo Bảng 1 và điền thông tin của mỗi lần lặp để tìm số 21 trong dãy theo thuật toán tìm kiếm tuần tự.

2. Lựa chọn phương án đúng.

Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự, ta thực hiện:

1. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.
2. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.
3. Sắp xếp dãy số theo thứ tự tăng dần.
4. So sánh số cần tìm với số ở giữa dãy số.

• Thuật toán tìm kiếm tuần tự thực hiện so sánh lần lượt từ phần tử đầu tiên của dãy với giá trị cần tìm.
• Việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử của dãy.

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

Thảo luận nhóm và thực hiện nhiệm vụ:

Hãy so sánh dãy số ở Hình 3 SGK tr.71 với dãy số dãy số của Hoạt động làm ở mục 1 (dãy 26, 14, 24, 18, 15, 21, 19, 25, 12)?

Quan sát Hình 4, em hãy mô tả lại hoạt động của thuật toán tìm kiếm nhị phân.

Lưu ý

• Thẻ số ở giữa dãy có số thứ tự là phần nguyên của phép chia

(Số lượng thẻ của dãy + 1) : 2.

• Khi dãy chỉ còn một thẻ số thì nửa trước (nửa sau) là dãy rỗng (dãy không caó thẻ số nào).
• Theo em, thuật toán tìm kiếm nhị phân lặp đi lặp lại thao tác nào và điều kiện để dừng lặp là gì?
• Thao tác lặp đi lặp lại là chia đôi dãy thẻ số.
• Điều kiện để dừng lặp: Tìm thấy số cần tìm hoặc dãy không có thẻ số nào nữa.