26

Dãy thẻ số

1

Thứ tự

14

2

24

3

18

4

25

5

21

6

19

7

25

8

12

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ẻ.

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

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

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

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.

🖎 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.

• Bài 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Ự

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)

• Bài toán tìm kiếm

26

Dãy thẻ số

1

Thứ tự

14

2

24

3

18

4

25

5

21

6

19

7

25

8

12

9

Em hãy tìm đầu vào, đầu ra của bài toán tìm kiếm trên.

Đầu vào: ……………………………………………………………………………………………….

Đầu ra: ……………………………………………………………………………………………………

Thông báo vị trí tìm thấy hoặc thông báo không tìm thấy số cần tìm.

Dãy số (được ghi trên các thẻ) và số cần 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Ự

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)

• Bài toán tìm kiếm

26

Dãy thẻ số

1

Thứ tự

14

2

24

3

18

4

25

5

21

6

19

7

25

8

12

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Ự

6

• Thuật toán tìm kiếm tuần tự

26

Dãy thẻ số

1

Thứ tự

14

2

24

3

18

4

15

5

21

19

7

25

8

12

9

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ự.

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

1

26

Sai

Sai

2

14

Sai

Sai

3

24

Sai

Sai

4

18

Sai

Sai

5

15

Sai

Sai

6

21

Đúng

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

6

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

BÀI 13. THUẬT TOÁN TÌM KIẾ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

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

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

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

🖎 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

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

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

🖎 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 trướ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.

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

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

12

Dãy thẻ số

1

Thứ tự

14

2

15

3

18

4

19

5

21

6

24

7

25

8

26

9

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

10

2

5

0

Phần dư

Phần nguyên

= 5

5

• 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

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

Lần lặp 1

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

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

Dãy thẻ số

1

Thứ tự

2

3

4

19

5

21

6

24

7

25

8

26

9

Vị trí ở giữa =

(6 + 9) / 2

15

2

7

1

Phần dư

Phần nguyên

= 7

7

• 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).

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

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

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

Lần lặp 2

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

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

Dãy thẻ số

1

Thứ tự

2

3

4

19

5

21

6

24

7

25

8

26

9

6

• 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.

Lật thẻ lần 3

🖎 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ỏ sau lần lặp 2

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

Lần lặp 3

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

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

🖎 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.

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.

Thảo luận nhó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.

8

8

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.

1

67

Sai

Sai

2

72

Sai

Sai

3

77

Sai

Sai

4

69

Sai

Sai

5

27

Sai

Sai

67

Dãy thẻ số

1

Thứ tự

72

2

77

3

69

4

27

5

81

79

7

25

18

9

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

6

21

10

6

81

Sai

Sai

7

79

Sai

Sai

8

25

Đú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 số đầu tiên của biển số xe tỉnh Lai Châu.

An Giang

Dãy thẻ tỉnh

Thứ tự

1

Vị trí ở giữa =

(1 + 10) / 2

11

2

5

1

Phần dư

Phần nguyên

= 5

• 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.

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

BRVT

2

Bình Định

3

Cà Mau

4

Điện Biên

5

Gia Lai

6

Khánh Hòa

7

Lai Châu

8

Nam Định

9

Yên Bái

10

5

Lần lặp 1

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.

An Giang

Dãy thẻ tỉnh

Thứ tự

1

Vị trí ở giữa =

(6 + 10) / 2

16

2

8

0

Phần dư

Phần nguyên

= 8

• 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.

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

BRVT

2

Bình Định

3

Cà Mau

4

Điện Biên

5

Gia Lai

6

Khánh Hòa

7

Lai Châu

8

Nam Định

9

Yên Bái

10

8

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

Lần lặp 2

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 số đầu tiên của biển số xe tỉnh Lai Châu.

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

Bài tập 1 SGK 75.

- Nêu cách tìm từ tiếng anh trong trong cuốn từ điển.