Bài giảng môn Tin học Lớp 7 - Chủ đề F - Bài 2: Tìm kiếm tuần tự

CHỦ ĐỀ F 
GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH 
MỘT SỐ THUẬT TOÁN SẮP XẾP VÀ TÌM KIẾM CƠ BẢN 
BÀI 1 
TÌM KIẾM TUẦN TỰ 
MỞ ĐẦU 
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? 
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 
TÌNH HUỐNG 
1. Tìm kiếm tuần tự một số trong dãy số 
- Dãy xuất phát: 
a 1 
a 2 
a 3 
a 4 
a 5 
a 6 
a 7 
a 8 
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: 
Mô phỏng: Bài toán tìm kiếm tuần tự 
A 
18 
94 
42 
44 
06 
55 
12 
67 
i 
1 
2 
3 
4 
- 
- 
- 
- 
x = 44 
i 
A[1] = 18 ≠ 44 
A[2] = 94 ≠ 44 
A[3] = 42 ≠ 44 
A[4] = 44 = x 
Với i = 4 thì A[4] = 44 = x 
- Nếu thay x = 30 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” 
TÌNH HUỐNG 
- Nếu thay x = 30 thì các bước tìm kiếm sẽ tiếp tục đến hết khi nào? Lúc đó câu trả lời cho bài toán tìm kiếm là gì? 
	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 ? 
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 
TÌNH HUỐNG 
Câu trả lời: 
Thuật toán được mô tả như hình trên là thuật toán tìm kiếm tuần tự. 
- Ý tưởng: 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. 
2. Thuật toán kiếm tuần tự 
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 
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ự 
3. Bài toán tìm kiếm 
Bài toán tìm kiếm trong dãy đã sắp thứ 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: Có hai loại bài toán tìm kiếm: 
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 
Bài 1. Cho một dãy số 
a 1 
a 2 
a 3 
a 4 
a 5 
a 6 
a 7 
a 8 
a 9 
a 10 
a 11 
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?” 
STT 
Nội dung 
1 
So sánh số ở đầu dãy với x: 
Vì a 1  = 27 ≠ x nên chuyển sang xét số tiếp theo a 2  trong dãy. 
2 
So sánh số đang xét với x: 
Vì a 2  = 63 ≠ x nên chuyển sang xét số tiếp theo a 3  trong dãy. 
3 
So sánh số đang xét với x: 
Vì a 3  = 12 ≠ x nên chuyển sang xét số tiếp theo a 4  trong dãy. 
4 
So sánh số đang xét với x: 
Vì a 4  = 59 ≠ x nên chuyển sang xét số tiếp theo a 5  trong dãy. 
5 
So sánh số đang xét với x: 
Vì a 5  = 67 ≠ x nên chuyển sang xét số tiếp theo a 6  trong dãy. 
6 
So sánh số đang xét với x: 
Vì a 6  = 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. 
Hướng dẫn 
- Gọi số phải tìm là x (x=45) 
Bài 2. 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? 
Bài 3. Em 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? 
LUYỆN TẬP 
Câu 1. Hai khả năng xảy ra khi kết thúc tìm kiếm tuần tự là gì? 
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? 
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? 
VẬN DỤNG