Giáo án điện tử Tin học 7 Bài 13 Chân trời sáng tạo: Thuật toán tìm kiếm

Bài giảng PowerPoint Tin học 7 Bài 13 Chân trời sáng tạo: Thuật toán tìm kiếm hay nhất, với thiết kế hiện đại, dễ dàng chỉnh sửa giúp Giáo viên có thêm tài liệu tham khảo để soạn Giáo án Tin học 7. Mời bạn đọc đón xem!

30 15 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Chủ đề: Bài giảng điện tử Tin Học 7

Môn: Tin học 7

Sách: Chân trời sáng tạo

Thông tin:

24 trang 5 tháng trước

Tác giả:

Profile Lê Na

26
Dãy thẻ số
1Thứ 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ì.

 !
"#$%&' (
$&' ()
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.
"*+,-./,012+31
"#$%&' (
$&' ()
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)
"*+,-./,012+31
26
Dãy thẻ số
1Thứ 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.
456*-: ……………………………………………………………………………………………….
4578: ……………………………………………………………………………………………………
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.
"#$%&' (
$&' ()
"*+,-./,012+31
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)
26
Dãy thẻ số
1Thứ 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ự.
"#$%&' (
$&' ()
95:,,-./,012+31,54/,;
"#$%&' (
6
$&' ()
95:,,-./,012+31,54/,;
26
Dãy thẻ số
1Thứ 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ố <$ trong dãy số bằng thuật toán tìm kiếm tuần tự.
Số <$ được tìm thấy
tại vị trí =
>4/?@A BC9+,7D/,9E F/CGBH4/,01I J93,KJLGBI
U U U
M U U U
M U U U
1 26 Sai Sai
2 14 Sai Sai
3 24 Sai Sai
4 18 Sai Sai
5 15 Sai Sai
6 21 F/C
"#$%&' (
=
$&' ()
95:,,-./,012+31,54/,;
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.
"#$%&' (
$&' ()
95:,,-./,012+31,54/,;
Hãy chọn phương án đúng.
012+311N,GB,7-/CKJLGBOP/C,95:,,-./,012+31,54/,;
. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.
". So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.
. Sắp xếp dãy số theo thứ tự tăng dần.
Q. So sánh số cần tìm với số ở giữa dãy số.
"#$%&' (
<&' (RS
"#$%&' (
Vị trí phần tử ở giữa dãy
bằng phần nguyên của
T6U,7VW45X6U,7VH5B+YZ<
Các số được sắp xếp
theo thứ tự 29[/CC+\1
<&' (RS
"#$%&' (
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 T6U,7VW45X6U
,7VH5B+YZ<
<&' (RS
"#$%&' (
Thuật toán tìm kiếm nhị phân:
"]^H$. 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.
"]^H<. Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc.
"]^H%. 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.
"]^H_. 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 "]^H$.
<&' (RS
"#$%&' (
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
T6U,7VW45X6U,7VH5B+YZ<
U,7V`C+a8b
T$XcYZ<
$d
<
d
Phần dư Phần nguyên
b
So sánh số cần tìm là <$ với số ghi trên thẻ vừa lật là $c.
Do 21 > 19 nên chỉ cần tìm ở /e8G85của dãy
Lật thẻ ở vị trí giữa dãy
>4/?@A$
<&' (RS
"#$%&' (
Dãy thẻ số
1
Thứ tự
2 3 4
19
5
21
6
24
7
25
8
26
9
U,7V`C+a8b
T=XcYZ<
$
<
f
$
Phần dư Phần nguyên
bf
f
So sánh số cần tìm là <$ với số ghi trên thẻ vừa lật là <_.
Do 21<24 nên chỉ cần tìm ở /e8,7]^H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
T6U,7VW45X6U,7VH5B+YZ<
>4/?@A<
<&' (RS
"#$%&' (
Dãy thẻ số
1
Thứ tự
2 3 4
19
5
21
6
24
7
25
8
26
9
=
Giá trị ghi trên thẻ thứ 6 là <$, bằng với số cần tìm
Kết quả: tìm thấy số <$ trong dãy ở 6U,7V,9g=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
>4/?@A%
<&' (RS
"#$%&' (
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
>4/
?@A
9./CG+/9Hh8
Oi/
j/C,9./CG+/9
6^+k1
J93,K8/9G.H9
?^A
1 U U U
2 U U U
3 U U U
U4 U U U
U5 U U U
U6 U U U
D/,l/9 8+GBW45Hh8O+m/GB
UAn Giang 67
UBà Rịa – Vũng Tàu U72
UBình Định 77
UCà Mau 69
Điện Biên 27
Gia Lai 81
Khánh Hòa 79
Lai Châu 25
Nam Định 18
Yên Bái 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.
8
n
8Y Áp dụng ,95:,,-./,012+31,54/,;để tìm tỉnh có 2 số đầu biển số xe <.
>4/?@A BC9+,7D/,9E F/CGBH4/,01I J93,KJLGBI
U U U
M U U U
M U U U
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ố
1Thứ tự
72
2
77
3
69
4
27
5
81 79
7
25 18
9
Số < được tìm
thấy tại vị trí n
6
21
10
6 81 Sai Sai
7 79 Sai Sai
n <
F/C
"*+,:A< SGK 75. Cho bảng danh sách hai số đầu biển số xe của một số tỉnh.
OY Áp dụng ,95:,,-./,012+31/9UA9o/để tìm hai
số đầu tiên của biển số xe tỉnh >8+9o5
An
Giang
Dãy thẻ
tỉnh
Thứ tự
1
U,7V`C+a8b
T$X$dYZ<
$$
<
$
Phần dư Phần nguyên
b
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
>4/?@A$
"*+,:A< 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
U,7V`C+a8b
T=X$dYZ<
$=
<
n
d
Phần dư Phần nguyên
bn
Tên tỉnh ghi trên thẻ thứ 8 là >8+
9o5 giống tên tỉnh cần tìm.
Kết quả: tìm thấy tên tỉnh Lai Châu
ở 6U,7V,9gn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
n
Đã bỏ sau lần lặp 1
>4/?@A<
"*+,:A< SGK 75. Cho bảng danh sách hai số đầu biển số xe của một số tỉnh.
OY Áp dụng ,95:,,-./,012+31/9UA9o/để tìm hai
số đầu tiên của biển số xe tỉnh >8+9o5
"*+,:A< SGK 75. Cho bảng danh sách hai số đầu biển số xe của một số tỉnh.
HY 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.
"*+,:A< SGK 75. Cho bảng danh sách hai số đầu biển số xe của một số tỉnh.
KY 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.
| 1/24
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

KHỞI ĐỘNG
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ì. 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. 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.
Đầu vào: ……………………………………………………………………………………………….
Dãy số (được ghi trên các thẻ) và số cần cần tìm.
Đầ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.
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
Số 21 được tìm thấy Thứ tự 1 2 3 4 5 6 7 8 9 tại vị trí 6. Lần lặp Số ghi trên thẻ Đúng số cần tìm? Đã hết dãy số? 1 26 Sai Sai 2 1 4 Sai Sai 3 2 4 Sai Sai 4 1 8 Sai Sai 5 15 Sai Sai 6 21 Đúng
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 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.
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ự 1 2 3 4 5 6 7 8 9 Dãy thẻ số 12 14 15 18 19 21 24 25 26 Lần lặp 1
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í ở giữa = (1 + 9) / 2 = 5
Vị trí phần tử ở giữa dãy 10 2 bằng phần nguyên của 0 5
(vị trí đầu + vị trí cuối) / 2 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ự 1 2 3 4 5 6 7 8 9 Dãy thẻ số 19 21 24 25 26 Lần lặp 2 Đã bỏ sau lần lặp 1
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í ở giữa = (6 + 9) / 2 = 7
Vị trí phần tử ở giữa dãy 15 2 bằng phần nguyên của 1 7
(vị trí đầu + vị trí cuối) / 2 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ự 1 2 3 4 5 6 7 8 9 Dãy thẻ số 19 21 24 25 26 Lần lặp 3 Đã bỏ sau lần lặp 1 Đã bỏ sau lần lặp 2 Lật thẻ lần 3
 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
Hai số đầu của biển số An Giang 67 Bà Rịa – Vũng Tàu 72 Bình Định 77 Cà Mau 69 Điện Biên 27 Gia Lai 81 Khánh Hòa 79 Lai Châu 25 Nam Định 18 Yên Bái 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 72 77 69 27 81 79 25 18 21 Số 25 được tìm
thấy tại vị trí 8. Thứ tự 1 2 3 4 5 6 7 8 9 10 Lần lặp Số ghi trên thẻ Đúng số cần tìm? Đã hết dãy số? 1 67 Sai Sai 2 72 Sai Sai 3 77 Sai Sai 4 69 Sai Sai 5 27 Sai Sai 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 Lần lặp 1
số đầu tiên của biển số xe tỉnh Lai Châu. Thứ tự 1 2 3 4 5 6 7 8 9 10 An Dãy thẻ Bình Cà Điện Gia Khánh Lai Nam Yên BRVT Giang tỉnh Định Mau Biên Lai Hòa Châu Định Bái
Lật thẻ ở vị trí giữa dãy
 So sánh tên tỉnh cần tìm là Lai
Vị trí ở giữa = (1 + 10) / 2 = 5
Châu với tên ghi trên thẻ vừa 11 2 lật là Điện Biên. 1 5
 Vì “L” đứng sau “Đ” trong bảng Phần dư Phần nguyên
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 2 3 4 5 6 7 8 9 10 An Dãy thẻ Bình Cà Điện Gia Khánh Lai Nam Yên BRVT Giang tỉnh Định Mau Biên Lai Hòa Châu Định Bái Đã bỏ sau lần lặp 1
Lật thẻ ở vị trí giữa dãy
Vị trí ở giữa = (6 + 10) / 2 = 8
 Tên tỉnh ghi trên thẻ thứ 8 là Lai 16 2
Châu giống tên tỉnh cần tìm. 0 8
 Kết quả: tìm thấy tên tỉnh Lai Châu Phần dư Phần nguyên
ở 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.
Document Outline

  • Khởi động
  • Slide 2
  • 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
  • 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
  • 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
  • 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
  • 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
  • 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
  • 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ
  • 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
  • 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
  • 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
  • 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
  • 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
  • 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
  • 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
  • Slide 17
  • Slide 18
  • Slide 19
  • Slide 20
  • Slide 21
  • Slide 22
  • Slide 23
  • Slide 24