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 7 – Cá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ét là số ở đầ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:

a1	a2	a3	a4	a5	a6	a7	a8
18	94	42	44	06	55	12	67

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ước	Thực hiện
1	So 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.
2	So 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.
3	So 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.
4	So 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ố

a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11
27	63	12	59	67	45	97	35	13	34	11

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:

a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11
27	63	12	59	67	45	97	35	13	34	11

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ước	Thực hiện
1	So 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.
2	So 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.
3	So 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.
4	So 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.
5	So 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.
6	So 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.