Thuat toan tim kiem tuan tu

(Tiết PPCT :13)

1
5
4
3
2
6
Ví dụ 1: Cho 6 quả cầu có khối lượng khác nhau. Hãy tìm vị
trí quả cầu có khối lượng bằng 2kg.
1 kg1,5 kg1,65 kg2,5 kg2 kg
Vậy quả cầu có khối
lượng bằng 2kg ở vị trí thứ 5

54321i
5125118924175A


Mô phỏng tìm kiếm trong một dãy số nguyên
Mô phỏng tìm kiếm trong một dãy số nguyên
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
K
5
K

Bài toán : Cho dãy A gồm N số nguyên khác nhau
a
1
,a
2
, ,a
n
và số nguyên K cho trước. Hãy xác định
thuật toán tìm chỉ số i mà a
i
= k.
Ví dụ 3 :Thuật toán tìm kiếm tuần tự

Xác định bài toán:
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 A bằng k.

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

Đưa ra i
rồi kết thúc
Nhập N:5,1,9,7,6
và k=4
i 1
a
i
= k?
Đ
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
B1
B2
B3
B4
B5
B6
Cách 2
Vẽ sơ đồ khối

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
67415
N
Nhập N, 5, 1,4,7,6

và k=4
i=1
i 1
5 =
4 ?
i 1
K=4
i 2
i=2
2 >
5 ?
i 1
Nhập N, 5,1,4,7,6

và 4
i 2
a
i
=
k ?
Đưa ra i
rồi kếtthú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
1 =
4 ?
i 3
i=3
3 >
5 ?
Nhập N,5,1,4,7,6
và 4
i 3
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
4 =
4 ?
Chỉ số i
cần tìm là i=3
32

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
7915
N
Nhập N, 5, 1,4,7,6

và k=4
i=1
i 1
5 =
4 ?
i 1
K=4
i 2
i=2
2 >
5 ?
i 1
Nhập N, 5,1,4,7,6

và 4
i 2
a
i
=
k ?
Đưa ra i
rồi kếtthú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
1 =
4 ?
i 3
i=3
3 >
5 ?
Nhập N,5,1,4,7,6
và 4
i 3
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
9 =
4 ?
32
i 4
4 >
5 ?
6
Nhập N:5,1,9,7,6
và k=4
i 4
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
i=4
4
7 =
4 ?
i 5
5>
5 ?
Nhập N:5,1,9,7,6
và k=4
i 5
a
i
= k?
Đ
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
i=5
6=4?
5
i 6
6> 5?
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

Các tính chất của thuật toán:

Tính dừng

Tính xác định

Tính đúng đắn

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


10987654321i
3331302221
9
6542A
Với k = 21 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 < 21




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
;
;
3331302221
Lượt thứ hai
Lượt thứ hai
: a
: a
giữa
giữa
là a
là a
8
8
= 30; 30 >
= 30; 30 > 21


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.
2221
66
21



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
Bước 7: Nếu Đầu


Cuối thì thông báo dãy A không có
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.

Xem chi tiết: Thuat toan tim kiem tuan tu