Bài 1. Tìm kiếm tuần tự

Bài Tìm kiếm tuần tự trang 78 SGK Tin Học lớp 7Cánh Diều, mời các em tham khảo cùng Bumbii.

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

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?

Đáp án:

Em kiểm tra danh sách lớp kèm cột điểm kiểm tra từ trên xuống, chỉ dừng khi tìm thấy điểm 10 duy nhất ở cột điểm kiểm tra, sau khi nhìn sang cột họ tên, sẽ tìm ra tên của bạn duy nhất đạt điểm 10.

THUẬT TOÁN TÌM KIẾM TUẦN TỰ

Hoạt động

Cho dãy số 18, 94, 42, 44, 06, 55, 12, 67, hãy tìm số 44. Em hãy thực hiện thuật toán được mô tả dưới đây và cho biết đó có phải là thuật toán tìm kiếm tuần tự hay không?

Bước 1. Số đang xétsố ở đầu dãy

Bước 2. Lặp khi (chưa xét hết dãy số)

                   Nếu số đang xét ≠ x: Chuyển đến xét số tiếp theo trong dãy

                   Trái lại: Thông báo vị trí tìm thấy x và kết thúc thuật toán

                   Hết nhánh

          Hết lặp

Bước 3. Thông báo không tìm thấy x và kết thúc thuật toán

Đáp án:

Dãy xuất phát:

a1a2a3a4a5a6a7a8
1894424406551267

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

BướcThực hiện
1So sánh số ở đầu dãy với x: Vì a1 = 18 ≠ x nên chuyển sang xét số tiếp theo a2 trong dãy.
2So sánh số đang xét dãy với x: Vì a2 = 94 ≠ x nên chuyển sang xét số tiếp theo a3 trong dãy.
3So sánh số đang xét dãy với x: Vì a3 = 42 ≠ x nên chuyển sang xét số tiếp theo a4 trong dãy.
4So sánh số đang xét dãy với x: Vì a4 = 44 = x. Kết luận: Tìm thấy x ở vị trí thứ tư trong dãy; kết thúc thuật toán.

Thuật toán trên là thuật toán tìm kiếm tuần tự.

Bài toán tìm kiếm có 2 loại:

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

2) Tìm kiếm trong dãy đã sắp thứ tự.

LUYỆN TẬP

Cho dãy số

a1a2a3a4a5a6a7a8a9a10a11
2763125967459735133411

Em hãy thể hiện từng bước của thuật toán giải bài toán “Tìm xem số 45 có trong dãy này không? Nếu có thì nằm ở vị trí nào?”

Đáp án:

Dãy xuất phát:

a1a2a3a4a5a6a7a8a9a10a11
2763125967459735133411

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

BướcThực hiện
1So sánh số ở đầu dãy với x: Vì a1 = 27 ≠ x nên chuyển sang xét số tiếp theo a2 trong dãy.
2So sánh số đang xét dãy với x: Vì a2 = 63 ≠ x nên chuyển sang xét số tiếp theo a3 trong dãy.
3So sánh số đang xét dãy với x: Vì a3 = 12 ≠ x nên chuyển sang xét số tiếp theo a4 trong dãy.
4So sánh số đang xét dãy với x: Vì a4 = 59 ≠ x nên chuyển sang xét số tiếp theo a5 trong dãy.
5So sánh số đang xét dãy với x: Vì a5 = 67 ≠ x nên chuyển sang xét số tiếp theo a6 trong dãy.
6So sánh số đang xét dãy với x: Vì a6 = 45 = x. Kết luận: Tìm thấy x ở vị trí thứ sáu trong dãy; kết thúc thuật toán.

VẬN DỤNG

Bài 1. Em có cách nào khác để giải bài toán tìm kiếm trong dãy không sắp thứ tự không? Tại sao?

Đáp án: Không. Thuật toán tìm kiếm tuần tự là cách đơn giản để thực hiện tìm kiếm đảm bảo không bỏ sót nào trong dãy không sắp thứ tự.

Bài 2. Có thể áp dụng thuật toán tìm kiếm tuần tự cho dãy đã sắp thứ tự không? Tại sao?

Đáp án: Có. Để cho ra kết quả tìm thấy đúng.

CÂU HỎI TỰ KIỂM TRA

Câu 1. Hai khả năng xảy ra khi kết thức tìm kiếm tuần tự là gì?

Đáp án: Hai khả năng đó là:

– Tìm thấy x và kết thúc.

– Hết dãy mà vẫn chưa tìm thấy; kết luận trong dãy không có số nào bằng x.

Câu 2. Khi nào thì việc tìm kiếm tuần tự kết thúc ở giữa chừng của dãy?

Đáp án: Khi có số x cần tìm ở giữa chừng của dãy.

Câu 3. Khi nào thì việc tìm kiếm tuần tự dò tìm đến phần tử cuối dãy?

Đáp án: Khi x cần tìm là phần tử cuối dãy hoặc không có x trong dãy.

Xem thêm các bài khác tại Giải sách bài tập tin học lớp 7 – NXB Cánh Diều

Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech

0 0 đánh giá
Article Rating
Theo dõi
Thông báo của
guest

0 Bình luận
Cũ nhất
Mới nhất Được bỏ phiếu nhiều nhất
Phản hồi nội tuyến
Xem tất cả bình luận
0
Cùng chia sẻ bình luận của bạn nào!x
×