thuật toán tìm kiếm
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (817.5 KB, 16 trang )
1
2
Kiểm tra bài cũ
Cho dãy số 6 5 7 1 7 2. Sử dụng thuật toán
sắp xếp hãy mô tả quá trình sắp xếp của
dãy số
3
Tiết 13
Chương I Một số khái niệm cơ bản
của tin học
4
5 6 8 2 4 7
>< >
>
>
>
<
<
<
THÀNH CÔNG!
Ví dụ
Hãy tìm vị trí
của phần tử
có giá trị là 7
1
2 3 4 5 6
Tìm thấy phần tử có giá
trị là 7 ở vị trí thứ 5
5
Ví dụ:
TÌM 1 QUYỂN SÁCH
TRONG 50 QUYỂN???
6
Ví dụ:
CÒN 10.000 QUYỂN
THÌ SAO
7
Một số công việc tìm kiếm
Tìm một quyển sách trên kệ
sách;
Tìm 1 từ trong cuốn từ điển;
Tìm 1 học sinh trong danh
sách lớp nào đó;
…
8
Ví dụ 3: Bài toán tìm kiếm
9 - 41 8- 3 2 6
Với i = 5 thì a
5
= 9
9
5 63 71 2 4
A
i
k
Cho dãy A gồm N số nguyên khác nhau:
a
1
,a
2
, ,a
N
và số nguyên k. Cần biết có hay
không chỉ số i (1 ≤ i ≤ N) mà ai = k. Nếu có
hãy cho biết chỉ số đó.(k được gọi là khóa tìm
kiếm)
Ví dụ: Với N = 7
k
7
Không có số hạng nào, không có i
9
Xác định bài toán:
Dãy A gồm N số nguyên khác
nhau: a
1
,a
2
, ,a
N
và số nguyên
k;
Chỉ số i sao cho 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.
Ý TƯỞNG
Tìm kiếm tuần tự được
thực hiện lần lượt từ số
hạng thứ 1 đến số hạng
thứ i;
So sánh giá trị số hạng
đang xét với khóa k nếu
a
i
=k thì đưa ra chỉ số i rồi
kết thúc thuật toán hoặc
i>N thì kết thúc thuật toán;
LIỆT KÊ
B1: Nhập N, các số hạng a
1
, a
2
,
a
3
,…, a
N
và khóa k;
B2: i ← 1;
B3: Nếu a
i
= k thì thông báo chỉ
số i rồi kết thúc;
B4: i ← i+1;
B5: Nếu i >N, dãy A không có số
hạng nào có giá trị bằng k, kết
thúc;
B6: Quay lại bước 3;
Thuật toán tìm kiếm tuần tự
LIỆT KÊ
B1: Nhập N, số hạng
a
1
, ,a
N
và khóa k;
B2: i ← 1;
B3: Nếu a
i
=k, thông báo
chỉ số i rồi kết thúc;
B4: i ← i+1;
B5: Nếu i >N, dãy A không
có số hạng nào có
giá trị bằng k, kết thúc;
B6: Quay lại bước 3;
Thuật toán tìm kiếm tuần tự
SƠ ĐỒ KHỐI
Sai
Đúng
Sai
Nhập N và a
1
, a
2
,…,a
N
; k
i
1
a
i
= k
Đưa ra i và kết thúc
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
Đún
g
12
Mô phỏng việc thực hiện thuật toán
A 9 6 12 7
i 1 2 3 4
K = 12, N = 4
Với i = 1 thì a
i
(a
1
) = ?
Với i = 2 thì a
i
(a
2
) = ?
Với i = 3 thì a
i
(a
3
)= ?
Vậy với chỉ số i = 3 ta tìm được số hạng a
i
có giá trị bằng K (k=12)
ai (a
1
) = 9
ai(a
2
) = 6
ai (a
3
)= 12
A 9 6 12 7
i 1 2 3 4 5
K = 8, N = 4
Với mọi i từ 1 đến 4 không có a
i
có giá trị bằng 8
Với i = 1 thì a
i
(a
1
) = ?
Với i = 2 thì a
i
(a
2
) = ?
Với i = 3 thì a
i
(a
3
) = ?
Với i = 4 thì a
i
(a
4
) = ?
Với i = 5 thì ai (a
5
) = ?
a
i
(a
1
) = 9
a
i
(a
2
) = 6
a
i
(a
3
)= 12
a
i
(a
5
)=
a
i
(a
4
)= 12
9 6 12
5
n
i
12
K
=
Mô phỏng việc thực hiện thuật toán
Đ
Ai = K ?
Nhập n và A1,A2,…
An; K
i 1
i i+1
i > n?
Thông báo dãy A
ko có giá trị =K rồi
kết thúc
Đưa ra i, rồi
kết thúc
S
Đ
S
Đ
Ai = K ?
Ai = K ?
Nhập n và A1,A2,
…An; K
Nhập n và A1,A2,
…An; K
i 1
i 1
i i+1
i i+1
i > n?
i > n?
Đưa ra i, rồi
kết thúc
Đưa ra i, rồi
kết thúc
S
Đ
S
9=12 ?
6=12 ?
12=12 ?
2>4 ?
3>4 ?
i = 3
1 2 3 4
Ví dụ thực tế:
4.500.00
0
2.600.000
4.000.000
5.000.00
0
4
3
2
1
Trong trường hợp này K = ?
Chỉ số i = ?
Giá trị a
i
(c n tìm)ầ
= ?
K = 4000.000
i = 3
a
i
= 4000.000
Cô muốn mua một máy điện thoại với giá 4.000.000
Nhập N và a
1
, a
2
, a
3
, , a
N
; k
Thử tài nhanh nhẹn
SƠ ĐỒ KHỐI
Sai
Đúng
Sai
Đún
g
a
i
= k
i 1
i i + 1
i > N
Đưa ra i rồi kết thúc
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
1
2
3
4
5
6
7
a
b
c
d
e
f
g
1
2
3
4
5
6
7
16
Qua bài học này các em cần nắm được những vấn đề sau:
-
Xác định chính xác dữ liệu vào (Input) và dữ liệu ra(Output)
của bài toán tìm kiếm tuần tự
-
Tìm ra được ý tưởng để viết thuật toán
-
Trình bày được thuật toán bằng 2 cách (Liệt kê và sơ đồ
khối)
Bài tập về nhà:
-
Về nhà làm bài tập số 7 trong SGK
-
Trong thuật toán tìm kiếm tuần tự có thể chuyển điều kiện
i>n (bước 5) lên sau bước 2 được không? Nếu được cần thay
đổi lại cách liệt kê và sơ đồ khối như thế nào?
