Giáo án điện tử tin học 7 cánh diều bài 1: Tìm kiếm tuần tự (1 tiết)

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

KHỞI ĐỘNG

Giáo viên dạy Tin học lớp 7A trả kết quả bài kiểm tra và thông báo: “Trong lớp có duy nhất một bạn đạt điểm 10”. Xem danh sách lớp kèm cột điểm kiểm tra, em làm thế nào để biết ai được điểm 10?

CHỦ ĐỀ F: GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH

BÀI 1: TÌM KIẾM TUẦN TỰ (1 Tiết)

NỘI DUNG BÀI HỌC

1. Tìm kiếm tuần tự một số trong dãy số
2. Thuật toán tìm kiếm tuần tự
3. Bài toán tìm kiếm
4. Tìm kiếm tuần tự một số trong dãy số

Đọc thông tin mục 1 SGK tr.78, và trả lời câu hỏi trong phần Ví dụ:

Cho dãy số 18, 94, 42, 44, 06, 55, 12, 67. Hãy tìm xem số 44 ở trong dãy này không. Nếu có thì đưa ra vị trí đầu tiên tìm thấy.

Hướng dẫn

Gọi số phải tìm là x (x = 44). Các bước thực hiện tìm kiếm:

Cả lớp cùng theo dõi video sau để hiểu rõ các bước thức hiện.

KẾT LUẬN

Trường hợp đến hết dãy mà vẫn không tìm thấy số x cần tìm thì rút ra kết luận “trong dãy số, không có số nào bằng x” nghĩa là thuật toán đảm bảo tính đúng đắn.

Ví dụ, nếu thay x = 30 trong ví dụ vừa nêu thì các bước tìm kiếm sẽ tiếp tục đến hết dãy (Bước 8) và cho kết luận “Không tìm thấy x trong dãy”

2. Thuật toán tìm kiếm tuần tự

Với dãy số đã cho ở ví dụ trên, em hãy thực hiện thuật toán được mô tả ở hình dưới và cho biết đó có phải là thuật toán tìm kiếm tuần tự hay không?

Theo em, trong thuật toán tìm kiếm tuần tự có những thao tác nào được lặp đi lặp lại và điều kiện để lặp lại là gì?

• Thao tác lặp đi lặp lại là bước 2.
• Điều kiện để lặp lại: Sẽ lặp đi lặp lại khi chưa tìm được kết quả và chưa xét hết dãy số.

KẾT LUẬN

Ý tưởng của thuật toán tìm kiếm tuần tự:

Xuất phát từ đầu dãy, nếu số ở đầu dãy không phải là số cần tìm thì chuyển sang số tiếp theo trong dãy xem có phải là số cần tìm không. Cứ như thế cho đến khi tìm thấy hoặc đã xét hết dãy.

Cần áp dụng thuật toán tìm kiếm tuần tự khi dãy đầu vào không có thứ tự.

3. Bài toán tìm kiếm

Em hãy đọc mục 3 SGK tr.79,80 và trả lời câu hỏi:

• Có mấy loại bài toán tìm kiếm?
• Nêu ví dụ cụ thể để phân biệt các loại bài toán tìm kiếm.

Bài toán tìm kiếm chia làm hai loại:

• Tìm kiếm trong dãy không sắp thứ tự
• Tìm kiếm trong dãy đã sắp thứ tự.

Bài toán tìm kiếm trong dãy không sắp thứ tự

Ví dụ: Tập bài kiểm tra của lớp chưa được sắp xếp theo thứ tự bảng chữ cái đối với tên học sinh. Muốn tìm bài làm của em, giáo viên phải xem tên học sinh ghi trên từng bài, lần lượt từ bài đầu tiên cho đến khi tìm thấy bài của em.

Khi dãy không sắp thứ tự cần thực hiện tìm kiếm tuần tự.

Ví dụ: Danh sách tên học sinh trong lớp đã sắp thứ tự theo chữ cái trong từ điển thì ta có thể nhanh chóng tìm thấy bài kiểm tra của em.

KẾT LUẬN

• Bài toán tìm kiếm chia làm hai loại: Tìm kiếm trong dãy không sắp thứ tự và tìm kiếm trong dãy đã sắp thứ tự.
• Khi dãy không sắp thứ tự thì cần thực hiện tìm kiếm tuần tự để đảm bảo không bỏ sót cho đến khi tìm thấy hoặc hết dãy và không tìm thấy.