NHIỆT LIỆT CHÀO MỪNG
THẦY CÔ VÀ CÁC EM ĐẾN VỚI
TIẾT CHUYÊN ĐỀ HÔM NAY !
Tin học định hướng khoa học máy tính 11

HOẠT ĐỘNG KHỞI ĐỘNG

TIẾT 41,42:

CHUYÊN ĐỀ :
BÀI TOÁN TÌM KIẾM

NỘI DUNG BÀI HỌC

1. Bài toán tìm kiếm
trên thực tế

2. Tìm kiếm tuần tự
3. Tìm kiếm nhị phân

01

BÀI TOÁN TÌM KIẾM
TRÊN THỰC TẾ

Chia lớp thành 3 nhóm, thực hiện nhiệm vụ và thuyết trình kết quả?
Với các bài toán tìm kiếm sau, hãy thảo luận về miền dữ liệu và khả
năng các kết quả có thể tìm được của bài toán:
Nhóm 1

Tìm hiểu bài toán: Tìm kiếm tệp trong máy tính và 5 quốc gia có
diện tích lớn nhất thế giới?

Nhóm 2

Tìm hiểu bài toán: Tìm 5 địa điểm du lịch được đánh giá cao
nhất ở Việt Nam và tìm kiếm tệp văn bản trong máy tính

Nhóm 3

Tìm hiểu bài toán: Mô phỏng việc tìm kiếm trong thực tế qua
một bài toán tìm kẹo màu đỏ trong túi kẹo ?

Câu hỏi gợi ý tìm hiểu:
• Vì sao cần tìm kiếm?
• Miền tìm kiếm là gì? Dữ liệu tìm kiếm là gì?
• Kết quả tìm thấy là gì?
• Mô tả một kết quả tìm thấy.
• Nêu cách tìm kiếm kiểm tra lời giải (nếu có).

Sau đây là
phần thuyết
trình của các
nhóm

GHI NHỚ
Tìm kiếm là một trong những bài toán quan trọng nhất của Tin
học. Việc thiết kế thuật toán tìm kiếm sẽ phụ thuộc vào cấu trúc
của miền dữ liệu cần tìm kiếm và tiêu chí cụ thể của bài toán tìm
kiếm.

02

TÌM KIẾM TUẦN TỰ

Sau đây là
phần thuyết
trình của
nhóm 3

Các nhóm thực
hiện làm phiếu
học tập

Kết quả :

Cho dãy số A = [1, 4, 7, 8, 3, 9, 10] và cần tìm kiếm phần
tử có giá trị bằng 9.

Có thể thực hiện tìm kiếm tuần tự như sau:
 Bước 1: i = 0: A[0] = 1 không bằng 9
 Bước 2: i = 1: A[1] = 4 không bằng 9
 Bước 3: i = 2: A[2] = 7 không bằng 9
 Bước 4: i = 3: A[3] = 8 không bằng 9
 Bước 5: i = 4: A[4] = 3 không bằng 9
 Bước 6: i = 5: A[5] = 9 là phần tử cần tìm.

Lưu ý

Miền dữ liệu tìm kiếm phải có
cấu trúc là một dãy tuyến tính các số
được đánh số theo chỉ số, ví dụ đánh
chỉ số từ 0, 1, 2,…, n – 1.

GHI NHỚ
Thuật toán tìm kiếm tuần tự được thực
hiện bằng cách duyệt lần lượt các phần
tử của dãy từ đầu đến cuối để tìm phần
tử có giá trị bằng giá trị cần tìm.

Thuật toán tìm kiếm tuần tự có thể viết như sau:
1 deaf LinearSearch(A,K):
2
3
4
5

for i in range(len(A)):
if A[i] == K:
return i
return -1

Câu hỏi củng cố kiến thức:

Câu 1: Cho dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86].
Thuật toán tìm kiếm tuần tự cần thực hiện bao nhiêu lần
duyệt để tìm ra phần tử có giá trị bằng 47 trong dãy?

Cần duyệt 8 bước sẽ tìm thấy số 47.

Câu 2: Khi nào thì tìm kiếm tuần tự sẽ tìm
được ngay kết quả, cần ít bước nhất?
Khi giá trị cần tìm trùng với số đầu tiên của dãy.

Câu 1: Thuật toán tìm kiếm tuần tự thực hiện công việc gì?

A. Lưu trữ dữ liệu

B. Sắp xếp dữ liệu theo
chiều tăng dần

C. Xử lí dữ liệu

D. Tìm kiếm dữ liệu cho
trước trong một danh sách
đã cho.

Câu 2: Thuật toán tìm kiếm tuần tự thực hiện công việc
như thế nào?
A. Sắp xếp lại dữ liệu theo

C. Chia nhỏ dữ liệu thành

thứ tự bảng chữ cái.

từng phần để tìm kiếm

B. Xem xét từ mục dữ liệu đầu
tiên cho đến khi tìm thấy mục dữ
liệu được yêu cầu hoặc đến khi
hết danh sách.

D. Bắt đầu tìm từ vị trí bất kì
trong danh sách.

Câu 3: Thực hiện thuật toán tìm kiếm tuần tự để tìm số 20 trong
danh sách [1, 3, 5, 4, 20, 2, 11]. Kết quả là?

A. Thông báo “Không tìm
thấy”

B. Thông báo “Tìm thấy”

C. Thông báo “Tìm thấy”,
giá trị cần tìm tại vị trí thứ 5
của danh sách
D. Thông báo “Tìm thấy”,
giá trị cần tìm tại vị trí thứ 20
của danh sách

Câu 4: Thuật toán tìm kiếm tuần tự bắt đầu thực hiện ở vị trí nào
trong danh sách?

A. Vị trí ở giữa

C. Vị trí đầu tiên

B. Vị trí cuối cùng

D. Bất kì vị trí nào

LUYỆN TẬP
Bài 1. Em hãy chỉnh sửa thuật toán tìm kiếm tuần tự để tìm ra tất cả các
phần tử trong dãy bằng giá trị cần tìm, biết dãy đó có nhiều phần tử
bằng giá trị cần tìm.
Chương trình sau sẽ thực hiện tìm
kiếm tuần tự trên dãy A và trả về dãy
bao gồm tất cả các chỉ số phần tử có
giá trị bằng K, nếu không tìm thấy thì
trả về dãy rỗng.

1 deaf LinearSearch(A,K):
2
kq = []
3
for
i
range(len(A)):
4
if A[i] == K:
5
kq.append(i)

in

VẬN DỤNG
Bài 1. Cho A là danh sách tên các học sinh trong lớp, viết chương trình tìm
kiếm tuần tự để tìm ra các học sinh có tên là Hoàn.
Chương trình tham khảo:

HƯỚNG DẪN VỀ NHÀ

1. Ôn tập các kiến thức

2. Làm các bài tập

đã học

trong SBT

3. Chuẩn bị trước
mục 3. thuật toán
tìm kiếm nhị phân

CẢM ƠN CÁCTHẦY CÔ VÀ CÁC
EM ĐÃ THAM GIA TIẾT HỌC
HÔM NAY!