BÀI 1. TÌM KIẾM TUẦN TỰ

PHẦN I. HỆ THỐNG CÂU HỎI, BÀI TẬP TRONG SGK

MỞ ĐẦU

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

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

Hoạt động: 

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 bên 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 khác 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.

LUYỆN TẬP

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?”.

VẬN DỤNG

Vận dụng 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?

Vận dụng 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?

TỰ KIỂM TRA

Tự kiểm tra 1: Hai khả năng xảy ra khi thực hiện tìm kiếm tuần tự là gì?

Tự kiểm tra 2: Khi nào thì việc tìm kiếm tuần tự được kết thúc giữa chừng của dãy?

Tự kiểm tra 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?

PHẦN II. 5 PHÚT TRẢ LỜI CÂU HỎI, BÀI TẬP SGK

MỞ ĐẦU

Đáp án KD: 

Em phải nhìn và tìm kiếm lần lượt từ đầu đến cuối của cột điểm đến khi thấy điểm 10, sau đó gióng sang cột tên để tìm bạn được điểm 10.

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

Đáp án HD: 

• Thực hiện thuật toán ở ví dụ trên.
• Bước 1. Số 18 là số ở đầu dãy.
• Bước 2. Lặp
• Số 18 khác số 44: Chuyển đến xét số tiếp theo trong dãy.
• Số 94 khác số 44: Chuyển đến xét số tiếp theo trong dãy.
• Số 42 khác số 44: Chuyển đến xét số tiếp theo trong dãy.
• Số 44 trùng số 44. Thông báo tìm thấy số 44.
• Hết nhánh
• Bước 3. Tìm thấy số 44 trong dãy.
• Đó là thuật toán tìm kiếm tuần tự.

LUYỆN TẬP

Đáp án LT:

Dãy xuất phát:

Gọi số phải tìm là x (x=45):

• Bước 1. Số đang xét là số ở đầu dãy; Kết quả chưa tìm thấy
• Bước 2. Lặp khi (chưa xét hết dãy số) và (Kết quả = chưa tìm thấy);

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

                    Trái lại: Kết quả = tìm thấy ; Thông báo vị trí tìm thấy x

                    Hết nhánh

Hết lặp

• Bước 3. Nếu kết quả = chưa tìm thấy: Thông báo không có x trong dãy

          Hết nhánh

VẬN DỤNG

Đáp án VD1: Cần tìm kiếm tuần tự hoặc sắp xếp dãy trước rồi tìm kiếm.

Đáp án VD2: Có thể vì việc sắp xếp dãy theo thứ tự không ảnh hưởng đến thuật toán tìm kiếm tuần tự.

TỰ KIỂM TRA

Đáp án TKT1: 

• Tìm được số
• Không tìm được số khi kết thúc dãy số.

Đáp án TKT2: 

Khi số đã được tìm thấy ở đó.

Đáp án TKT3: 

Khi số cần tìm chưa được tìm thấy.