Bài giảng Tin học 7 - Bài 1: 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? TÌNH HUỐNG
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 1. Tìm kiếm tuần tự một số trong dãy số
 - 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: Mô phỏng: Bài toán tìm kiếm tuần tự
x = 44
 A[1] = 18 ≠ 44 A[2] = 94 ≠ 44A[3] = 42 ≠ 44A[4] = 44 = x
 A 18 94 42 44 06 55 12 67
 i 1 2 3 4 - - - -
 i
 Với i = 4 thì A[4] = 44 = x 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ì?
 - 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
 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 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ự. 2. Thuật toán 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.
 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 3. Bài toán tìm kiếm
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ự 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ố
 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?” STT Nội dung
 So sánh số ở đầu dãy với x:
 1
 Vì a1 = 27 ≠ x nên chuyển sang xét số tiếp theo a2 trong dãy.
Hướng dẫn So sánh số đang xét với x:
 2
 Vì a = 63 ≠ x nên chuyển sang xét số tiếp theo a trong dãy.
- Gọi số phải 2 3
 So sánh số đang xét với x:
tìm là x 3
 Vì a3 = 12 ≠ x nên chuyển sang xét số tiếp theo a4 trong dãy.
(x=45) So sánh số đang xét với x:
 4
 Vì a4 = 59 ≠ x nên chuyển sang xét số tiếp theo a5 trong dãy.
 So sánh số đang xét với x:
 5
 Vì a5 = 67 ≠ x nên chuyển sang xét số tiếp theo a6 trong dãy.
 So sánh số đang xét với x:
 6 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. LUYỆN TẬP
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? VẬN DỤNG
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?