Tin hoc 10: Bai 4 Thuat toan tim kiem

V D V Thuật toán tìm kiếm
Hai bạn chó (Bi và Bông) chơi trốn tìm, Bông đã trốn vào một
trong những chiếc mũ của ông già Nôen trên. Hãy chỉ ra các
cách tìm chiếc mũ mà Bông đang trốn? Cho biết có những cách
nào?
Bông trốn
đâu nhỉ ?

C1: Tìm kiếm tuần tự
( mở từng mũ)

C2: Do các mũ đã sắp xếp
lớn dần, hai mũ đầu nhỏ hơn
người của Bông nên chỉ tìm
hai mũ sau thôi!

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

Xột mt bi toỏn tỡm kim n gin sau :
Cho dóy A gm N s nguyờn khỏc nhau:
a
1
,a
2
.a
N
v mt s nguyờn k.Cn bit cú
hay khụng ch s i(1<=i<=N) m a
i
=k. Nu
cú hóy cho bit s ú.

INPUT: Dãy A gồm N số nguyên a
1
, a
2
, , a
N
đôi
một khác nhau và số nguyên k.


OUTPUT: Chỉ số i mà a
i
= k hoặc thông báo
không có số hạng nào của dóy A cú giỏ tr bằng k.
1. Thuật toán tìm kiếm tuần tự


Xác định bài toán:

54321I
5125118924175A


Mô phỏng thuật toán tìm kiếm tuần tự
Mô phỏng thuật toán tìm kiếm tuần tự
Với k = 2 và dãy A gồm 10 số hạng như sau:
Tại vị trí i = 5 có a
5
= 2 = k
Với k = 6 và dãy A gồm 10 số hạng như sau:
A 5 7 1 4 2 9 8 11 25 51
I 1 2 3 4 5 6 7 8 9 10 11
Với mọi i từ 1 10 không có a
i
có giá trị bằng 6
5

ý tưởng:
Lần lượt từ số hạng thứ nhất, ta so sánh giá trị
số hạng đang xét với khoá (k) cho đến khi có sự
trùng nhau, nếu đã xét tới số hạng cuối cùng mà
không có sự trùng nhau thì có nghĩa là dãy A
không có số hạng nào có giá trị bằng k.

Cách 1: Liệt kê các bước
Cách 1: Liệt kê các bước

Bước 1: Nhập N, các số hạng a
Bước 1: Nhập N, các số hạng a
1
1
, a
, a
2
2
, , a
, , a
N
N


và giá trị khoá k;
và giá trị khoá k;

Bước 2: i
Bước 2: i


1;
1;

Bước 3: Nếu a
Bước 3: Nếu a
i
i
= k thì thông báo chỉ số i, rồi kết thúc;
= k thì thông báo chỉ số i, rồi kết thúc;

Bước 4: i
Bước 4: i


i+1;
i+1;

Bước 5: Nếu i > N thì thông báo dãy A không có số
Bước 5: Nếu i > N thì thông báo dãy A không có số
hạng nào có giá trị bằng k, rồi kết thúc;
hạng nào có giá trị bằng k, rồi kết thúc;

Bước 6: Quay lại B3.
Bước 6: Quay lại B3.

Nhập N, a
1
, a
2
, , a
N
và k
i 1
a
i
=
k ?
Đưa ra i
rồi kết thúc
Đ
S
Đ
i i + 1
i >
N ?
Thông báo dãy A không
có số hạng có giá trị
bằng k, rồi kết thúc
S
Cách 2
Vẽ sơ đồ khối

2. Thuật toán tìm kiếm nhị phân
ý tưởng:
Sử dụng tính chất dãy A đã sắp xếp tăng, ta tìm
cách thu hẹp nhanh phạm vi tìm kiếm bằng cách
so sánh k với số hạng ở giữa dãy (a
giữa
), khi đó chỉ
xảy ra một trong ba trường hợp:
Quá trình trên được lặp đi lặp lại cho đến khi tìm được OUTPUT.
- Nếu a
giữa
= k => tìm được chỉ số i, kết thúc;
- Nếu a
giữa
> k => do dãy A đã được sắp xếp tăng
nên việc tìm kiếm thu hẹp chỉ xét từ a1 a
giữa
- 1;
- Nếu a
giữa
< k => do dãy A đã được sắp xếp tăng nên
việc tìm kiếm thu hẹp chỉ xét từ a
giữa
+ 1 a
N
.

Thuật toán tìm kiếm nhị phân
Xác định bài toán:
INPUT: Dãy A l dóy tng gồm N số nguyên
a
1
, a
2
, , a
N
đôI một khác nhau và m t số
nguyên k.
OUTPUT: Chỉ số i mà a
i
= k hoặc thông
báo không có số hạng nào của dóy A cú giỏ
tr bằng k.



Liệt kê các bước
Liệt kê các bước

Bước 1: Nhập N, các số hạng a
Bước 1: Nhập N, các số hạng a
1
1
, a
, a
2
2
, , a
, , a
N
N


và giá trị khoá k;
và giá trị khoá k;

Bước 2: Đầu
Bước 2: Đầu


1, Cuối
1, Cuối


N;
N;

Bước 3: Giữa
Bước 3: Giữa


[(Đầu + Cuối)/2];
[(Đầu + Cuối)/2];

Bước 4: Nếu a
Bước 4: Nếu a
Giữa
Giữa
= k thì thông báo chỉ số Giữa
= k thì thông báo chỉ số Giữa
rồi kết thúc;
rồi kết thúc;

Bước 5: Nếu a
Bước 5: Nếu a
Giữa
Giữa
> k thì đặt Cuối = Giữa - 1 rồi
> k thì đặt Cuối = Giữa - 1 rồi
chuyển sang bước 7;
chuyển sang bước 7;

Bước 6: Đầu
Bước 6: Đầu


Giữa + 1;
Giữa + 1;

Bước 7: Nếu Đầu >= Cuối thì thông báo dãy A không có
Bước 7: Nếu Đầu >= Cuối thì thông báo dãy A không có
số hạng có giá trị bằng k, rồi kết thúc;
số hạng có giá trị bằng k, rồi kết thúc;

Bước 8: Quay lại bước 3.
Bước 8: Quay lại bước 3.




S KHI
S KHI
Dau 1;Cuoi N
a
Giua
= k ?
a ra Giua
ri kt thỳc
ỳng
Sai
Cuoi Giua - 1
a
Giua
>k
ỳng
Thụng bỏo dóy A khụng cú s
hng cú giỏ tr bng k ri kt thỳc
Sai
Giua [(Dau + Cuoi)/2]
Dau Giua + 1 Dau> Cuoi
Sai
ỳng
Nhp N v
a1,a2,aN;k

Mô phỏng thuật toán tìm kiếm nhị phân
Mô phỏng thuật toán tìm kiếm nhị phân


Với k = và dãy A gồm 10 số hạng như sau:
Lượt thứ nhất
: a
: a
giữa
giữa
là a
là a
5
5
= 9; 9 <
= 9; 9 <


vùng tìm kiếm thu hẹp trong phạm vi từ a
vùng tìm kiếm thu hẹp trong phạm vi từ a
6
6


a
a
10
10
;
;
Lượt thứ hai
Lượt thứ hai
: a
: a
giữa
giữa
là a
là a
8
8
= 30; 30 >
= 30; 30 >


vùng tìm kiếm thu hẹp trong phạm vi từ a
vùng tìm kiếm thu hẹp trong phạm vi từ a
6
6


a
a
7
7
;
;
Lượt thứ ba
Lượt thứ ba
: a
: a
giữa
giữa
là a
là a
6
6
= 21;
= 21;
21= 21
21= 21
Vậy số cần tìm là i = 6.
10987654321i
3331302221
9
6542A
3331302221 2221
66
21
9
5 8
30
6
21
21212121

Mô phỏng thuật toán tìm kiếm nhị phân
Mô phỏng thuật toán tìm kiếm nhị phân






Với k = 25 và dãy A gồm 10 số hạng như sau:
Với k = 25 và dãy A gồm 10 số hạng như sau:
10987654321i
3331302221
9
6542A
3331302221 2221
66
21
Lượt thứ nhất
: a
: a
giữa
giữa
là a
là a
5
5
= 9; 9 <
= 9; 9 < 25




vùng tìm kiếm thu hẹp trong phạm vi từ a
vùng tìm kiếm thu hẹp trong phạm vi từ a
6
6


a
a
10
10
;
;
Lượt thứ hai
Lượt thứ hai
: a
: a
giữa
giữa
là a
là a
8
8
= 30; 30 >
= 30; 30 > 25


vùng tìm kiếm thu hẹp trong phạm vi từ a
vùng tìm kiếm thu hẹp trong phạm vi từ a
6
6


a
a
7
7
;
;
Lượt thứ ba
Lượt thứ ba
: a
: a
giữa
giữa
là a
là a
6
6
= 21;
= 21;
21<25
21<25

vùng tìm kiếm thu hẹp trong phạm vi từ a
vùng tìm kiếm thu hẹp trong phạm vi từ a
6
6


a
a
7
7
;
;
Lượt thứ t
Lượt thứ t
: a
: a
giữa
giữa
là a
là a
7
7
= 22;
= 22;
22<25
22<25

vùng tìm kiếm thu hẹp trong phạm vi u =7,cu i=7
vùng tìm kiếm thu hẹp trong phạm vi u =7,cu i=7
Kt lun trong dóy khụng cú s hng no cú giỏ tr l 25 c.
Kt lun trong dóy khụng cú s hng no cú giỏ tr l 25 c.
Lượt thứ n m
Lượt thứ n m
:
:
vùng tìm kiếm thu hẹp trong phạm vi
vùng tìm kiếm thu hẹp trong phạm vi
u =8,cu i=7
u =8,cu i=7
iu ny vụ lý.
iu ny vụ lý.
8
3021
6 7
22

Xem chi tiết: Tin hoc 10: Bai 4 Thuat toan tim kiem