Thảo luận nhóm

KHỞI ĐỘNG

Có 9 thẻ số, mỗi thẻ được số ở một mặt và mặt còn lại
không ghi gì.
Dãy thẻ số

26

14

24

18

25

21

19

25

12

Thứ tự

1

2

3

4

5

6

7

8

9

Hình 1. Các thẻ được ghi số ở mặt úp

Nêu cách tìm một số bất kì có trong dãy số ghi trên các thẻ.

CHỦ ĐỀ 5. GIẢI QUYẾT VẤN ĐỀ VỚI
SỰ TRỢ GIÚP CỦA MÁY TÍNH

BÀI 13. THUẬT TOÁN TÌM KIẾM

BÀI 13. THUẬT TOÁN TÌM KIẾM
1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
 Bài toán tìm kiếm

 Tìm kiếm là việc con người thường xuyên phải thực hiện trong đời
sống thực tiễn.
Em hãy cho ví dụ để tìm kiếm tìm đầu vào, đầu ra của bài toán
tìm kiếm trên.
Ví dụ:
 Tìm số điện thoại trong danh bạ để biết người đã gọi đến.
 Tìm bạn sinh cùng tháng với em trong danh sách lớp.
 Tìm một bạn trong bức ảnh chụp tập thể lớp.

BÀI 13. THUẬT TOÁN TÌM KIẾM
1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
 Bài toán tìm kiếm

Ví dụ: Hãy tìm một số bất kì có trong dãy số ghi trên các thẻ (các thẻ
được ghi số ở mặt úp)
Dãy thẻ số

26

14

24

18

25

21

19

25

12

Thứ tự

1

2

3

4

5

6

7

8

9

Em hãy tìm đầu vào, đầu ra của bài toán tìm kiếm trên.
số (được ghi trên các thẻ) và số cần cần tìm.
Đầu vào: Dãy
……………………………………………………………………………………………….
Thông báo vị trí tìm thấy hoặc thông báo không tìm thấy số
Đầu ra: ……………………………………………………………………………………………………
cần tìm.

BÀI 13. THUẬT TOÁN TÌM KIẾM
1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
 Bài toán tìm kiếm

Ví dụ: Hãy tìm một số bất kì có trong dãy số ghi trên các thẻ (các thẻ
được ghi số ở mặt úp)
Dãy thẻ số

26

14

24

18

25

21

19

25

12

Thứ tự

1

2

3

4

5

6

7

8

9

Em hãy cho biết cách tìm một số bất kì có trong dãy số ghi trên
các thẻ của bài toán trên.
 Duyệt (lật) lần lượt từng số và so sánh số cần tìm trong dãy số từ
đầu đến cuối. Đó là cách tìm kiếm tuần tự hay còn gọi là thuật toán
tìm kiếm tuần tự.

BÀI 13. THUẬT TOÁN TÌM KIẾM
1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
 Thuật toán tìm kiếm tuần tự

BÀI 13. THUẬT TOÁN TÌM KIẾM
1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
 Thuật toán tìm kiếm tuần tự
Cho các số ghi trên mỗi thẻ. Tìm số 21 trong dãy số bằng thuật toán tìm kiếm tuần tự.
Dãy thẻ số

26

14

24

18

15

21

19

25

12

Thứ tự

1

2

3

4

5

6

7

8

9

Lần lặp
1
2
3 
4 
5
6

Số ghi trên thẻ
26
14 
24 
18 
15
21

Đúng số cần tìm?
Sai
Sai
 
Sai
 
Sai
 
Sai
Đúng

Số 21 được tìm thấy
tại vị trí 6.
Đã hết dãy số?
Sai
Sai
 
Sai
 
Sai
 
Sai

BÀI 13. THUẬT TOÁN TÌM KIẾM
1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
 Thuật toán tìm kiếm tuần tự

 Thuật toán tìm kiếm tuần tự thực hiện so sánh lần lượt từ phần tử
đầu tiên của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy
hoặc đã duyệt hết các phần tử trong dãy.

BÀI 13. THUẬT TOÁN TÌM KIẾM
1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
 Thuật toán tìm kiếm tuần tự

Hãy chọn phương án đúng.
Tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự.
A. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.
B. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.
C. Sắp xếp dãy số theo thứ tự tăng dần.
D. So sánh số cần tìm với số ở giữa dãy số.

BÀI 13. THUẬT TOÁN TÌM KIẾM
2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

Các số được sắp xếp
theo thứ tự không giảm

Vị trí phần tử ở giữa dãy
bằng phần nguyên của
(vị trí đầu + vị trí cuối) / 2

BÀI 13. THUẬT TOÁN TÌM KIẾM
2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
 Việc tìm kiếm áp dụng trên dãy giá trị đã được sắp xếp theo
thứ tự. Thuật toán thực hiện so sánh giá trị của phần tử ở giữa
dãy với giá trị cần tìm, tiếp tục tìm kiếm trên một nửa dãy có
khoảng giá trị mà giá trị cần tìm thuộc vào đến khi tìm thấy hoặc
đã duyệt hết các phần tử trong dãy.
 Vị trí phần tử ở giữa dãy bằng phần nguyên của (vị trí đầu + vị
trí cuối) / 2

BÀI 13. THUẬT TOÁN TÌM KIẾM
2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
 Thuật toán tìm kiếm nhị phân:
Bước 1. So sánh giá trị cần tìm với giá trị của phần tử giữa dãy đang
xét.
Bước 2. Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc.
Bước 3. Nếu nhỏ hơn thì xét dãy ở nửa bước, nếu lớn hơn thì xét
dãy ở nửa sau.
Bước 4. Nếu dãy rỗng thì thông báo không tìm thấy và kết thúc tìm
kiếm, không thì qua lại Bước 1.

BÀI 13. THUẬT TOÁN TÌM KIẾM
2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Thứ tự
Dãy thẻ số
Lần lặp 1

1

2

3

4

55

6

7

8

9

12

14

15

18

19

21

24

25

26

Lật thẻ ở vị trí giữa dãy

 So sánh số cần tìm là 21 với số ghi trên thẻ vừa lật là 19.
 Do 21 > 19 nên chỉ cần tìm ở nửa sau của dãy
Vị trí phần tử ở giữa dãy
bằng phần nguyên của
(vị trí đầu + vị trí cuối) / 2

Vị trí ở giữa = (1 + 9) / 2 = 5
10
2
5
0
Phần dư
Phần nguyên

BÀI 13. THUẬT TOÁN TÌM KIẾM
2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Thứ tự
Dãy thẻ số
Lần lặp 2

1

2

3

4

Đã bỏ sau lần lặp 1

5

6

7

8

9

19

21

24

25

26

Lật thẻ ở vị trí giữa dãy

 So sánh số cần tìm là 21 với số ghi trên thẻ vừa lật là 24.
 Do 21<24 nên chỉ cần tìm ở nửa trước của dãy (là thẻ thứ 6).
Vị trí phần tử ở giữa dãy
bằng phần nguyên của
(vị trí đầu + vị trí cuối) / 2

Vị trí ở giữa = (6 + 9) / 2 = 7
15
2
7
1
Phần dư
Phần nguyên

BÀI 13. THUẬT TOÁN TÌM KIẾM
2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Thứ tự
Dãy thẻ số
Lần lặp 3

1

2

3

4

Đã bỏ sau lần lặp 1

5

6

7

8

9

19

21

24

25

26

Lật thẻ lần 3

Đã bỏ sau lần lặp 2

 Giá trị ghi trên thẻ thứ 6 là 21, bằng với số cần tìm
 Kết quả: tìm thấy số 21 trong dãy ở vị trí thứ 6 và kết thúc tìm kiếm.

 Khi dãy chỉ còn một thẻ số thì nửa trước (hoặc nửa sau) là dãy
rỗng (dãy không có thẻ số nào)

BÀI 13. THUẬT TOÁN TÌM KIẾM
2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
 Dãy sắp xếp theo thứ tự (tăng dần / giảm dần / không giảm / không
tăng) giúp việc tìm kiếm nhanh hơn, hiệu quả hơn nhờ sử dụng thuật
toán tìm kiếm nhị phân.

Thảo luận nhóm

Bài tập 1 SGK 75. Hãy sử dụng thuật toán tìm kiếm tuần tự để tìm trong lớp em có
bạn cùng tháng sinh theo bảng 2.
Lần
Tháng sinh của Cùng tháng sinh Đã hết danh sách
lặp
bạn
với em
lớp
1
2
3
 4
 5
 6

 
 
 
 
 
 

 
 
 
 
 
 

 
 
 
 
 
 

Bài tập 2 SGK 75. Cho bảng danh sách hai số đầu biển số xe của một số tỉnh.
Tên tỉnh
 An Giang
 Bà Rịa – Vũng Tàu
 Bình Định
 Cà Mau
Điện Biên
Gia Lai
Khánh Hòa
Lai Châu
Nam Định
Yên Bái

Hai số đầu của biển số
67
 72
77
69
27
81
79
25
18
21

Bài tập 2 SGK 75. Cho bảng danh sách hai số đầu biển số xe của một số tỉnh.
a) Áp dụng thuật toán tìm kiếm tuần tự để tìm tỉnh có 2 số đầu biển số xe 25.
Dãy thẻ số

67

Thứ tự
Lần lặp
1
2
3 
4 
5
6
7
8

1

72

77

69

27

5
2
3
4
Số ghi trên thẻ
67
72  
77  
69  
27
81
79
25

81

79

25

18

21

Số 25 được tìm
thấy tại vị trí 8.

6
7
9 10
8
Đúng số cần tìm?
Đã hết dãy số?
Sai
Sai
Sai 
Sai
 
Sai 
Sai
 
Sai 
Sai
 
Sai
Sai
Sai
Sai
Sai
Sai
Đúng

Bài tập 2 SGK 75. Cho bảng danh sách hai số đầu biển số xe của một số tỉnh.
b) Áp dụng thuật toán tìm kiếm nhị phân để tìm hai
Lần lặp 1
số đầu tiên của biển số xe tỉnh Lai Châu.

Thứ tự

1

An
Dãy thẻ
Giang
tỉnh

2

3

4

5

6

7

8

9

10

BRVT

Bình
Định

Cà
Mau

Điện
Biên

Gia
Lai

Khánh
Hòa

Lai
Châu

Nam
Định

Yên
Bái

Lật thẻ ở vị trí giữa dãy

Vị trí ở giữa = (1 + 10) / 2 = 5
11
2
5
1
Phần dư

Phần nguyên

 So sánh tên tỉnh cần tìm là Lai
Châu với tên ghi trên thẻ vừa
lật là Điện Biên.
 Vì “L” đứng sau “Đ” trong bảng
chữ cái nên tìm ở nửa sau.

Bài tập 2 SGK 75. Cho bảng danh sách hai số đầu biển số xe của một số tỉnh.
b) Áp dụng thuật toán tìm kiếm nhị phân để tìm hai
Lần lặp 2
số đầu tiên của biển số xe tỉnh Lai Châu.

Thứ tự

1

An
Dãy thẻ
Giang
tỉnh

2

3

4

5

6

7

8

9

10

BRVT

Bình
Định

Cà
Mau

Điện
Biên

Gia
Lai

Khánh
Hòa

Lai
Châu

Nam
Định

Yên
Bái

Đã bỏ sau lần lặp 1

Vị trí ở giữa = (6 + 10) / 2 = 8
16
2
8
0
Phần dư

Phần nguyên

Lật thẻ ở vị trí giữa dãy

 Tên tỉnh ghi trên thẻ thứ 8 là Lai
Châu giống tên tỉnh cần tìm.
 Kết quả: tìm thấy tên tỉnh Lai Châu
ở vị trí thứ 8 và kết thúc tìm kiếm.

Bài tập 2 SGK 75. Cho bảng danh sách hai số đầu biển số xe của một số tỉnh.
c) So sánh số lần lặp của câu a và câu b. Tại sao?

Khi tìm kiếm biển số xe 25 tỉnh Lai Châu.
 Áp dụng thuật toán tìm kiếm tuần tự ở câu a): 8 lần
 Áp dụng thuật toán tìm kiếm nhị phân ở câu b): 2 lần
Số lần lặp ở câu b) ít hơn vì danh sách tên tỉnh đã được sắp xếp nên
có thể áp dụng thuật toán tìm kiếm nhị phân để tìm.

Bài tập 2 SGK 75. Cho bảng danh sách hai số đầu biển số xe của một số tỉnh.
d) Có thể áp dụng thuật toán tìm kiếm nhị phân để tìm ra tỉnh khi biết hai số
đầu của biển số xe của tỉnh đó hay không? Tại sao?

Không áp dụng thuật toán tìm kiếm nhị phân để tìm ra tỉnh khi biết
hai số đầu của biển số xe của tính đó vì danh sách hai số đầu của biển
số xe chưa được sắp xếp.

Bài tập 1 SGK 75.
- Nêu cách tìm từ tiếng anh trong trong cuốn từ điển.
Bài tập 2 SGK 75.
- Áp dụng thuật toán tìm kiếm nhị phân, tự đặt 5 câu hỏi đúng / sai để
xác định ngày sinh, tháng sinh của một bạn.