Xem mẫu
- CHƯƠNG 4
CÁC THUẬT TOÁN TÌM
KIẾM
- I. KHÁI NIỆM TÌM KIẾM
CHÌA KHÓA
1. Đặt vấn đề CỦA TA ĐÂU?
2/37
- I. KHÁI NIỆM TÌM KIẾM
2. Khái niệm
Tìm kiếm là việc kiểm tra xem có hay không
một đối tượng có một số thông tin cho trước
(đối tượng cần tìm) trong một tập các đối
tượng cho trước (không gian tìm kiếm)
Ví dụ: Tìm một chùm chìa khóa trong một
gian phòng
Ta có hình ảnh của chùm chìa khóa
Gian phòng gồm nhiều đồ đạc
3/37
- 3. BÀI TOÁN TÌM KIẾM
- Dãy a, có n đối tượng, mỗi đối tượng có một
Dữ liệu vào: “khóa tìm kiếm”
- Khóa của đối tượng cần tìm (Key)
Dữ liệu ra: - Nếu tìm thấy đối tượng có khóa ‘Key’ trong
dãy a trả lại giá trị 1, ngược lại trả lại giá trị 0.
a0 a1 a2 a3 a4
Dữ liệu vào:
5 1 6 8 2
Ví dụ: Số x=6
Dữ liệu ra: 1 (Tìm thấy x trong mảng a)
4/37
- II. CÁC THUẬT TOÁN TÌM KIẾM
Tìm kiếm tuần tự
Tìm kiếm nhị phân
Tìm kiếm trên cây nhị phân tìm kiếm
5/37
- II. CÁC THUẬT TOÁN TÌM KIẾM
Tùy theo dữ liệu vào ta có thể phân chia bài
toán tìm kiếm thành hại loại
Tìm kiếm trên dãy chưa sắp: dãy tìm kiếm
chưa được sắp xếp theo thứ tự khóa tìm
kiếm
Tìm kiếm trên dãy đã sắp: dãy tìm kiếm đã
sắp theo thứ tự tăng dần của khóa tìm kiếm
6/37
- 1. TÌM KIẾM TRÊN DÃY CHƯA SẮP
Với một dãy chưa được sắp xếp thì cách
tìm kiếm đơn giản nhất là tìm kiếm tuần tự
Tìm kiếm tuần tự là một phương pháp tìm
kiếm khá phổ biến và hết sức đơn giản
?
7/37
- 1.1.TÌM KIẾM TUẦN TỰ
a. Ý tưởng :
So sánh khóa của đối tượng cần tìm với khóa của
đối tượng đầu tiên trong dãy.
Nếu bằng nhau, kết thúc tìm kiếm (thành công)
Nếu không bằng, chuyển sang đối tượng kế tiếp
Lặp lại công việc trên cho đến khi gặp một đối tượng
có khóa bằng với khóa cần tìm (thành công) hoặc đã
hết các đối tượng trong dãy (không thành công)
8/37
- 1.1TÌM KIẾM TUẦN TỰ
b. Minh họa a0 a1 a2 a3 a4
Ví dụ 1: Cho dãy số 5 1 6 8 2
Tìm số x=6 trong dãy
x
6
Tìm thấy x
i=0 i=1 i=2
5 1 6 8 2
9/37
- 1.1.TÌM KIẾM TUẦN TỰ
Việc tìm kiếm có thể minh họa như sau
i=0; a0=5 x=6; i=i+1;
Chuyển sang đối tượng kế tiếp
i=1; a1=1 x=6; i=i+1;
Chuyển sang đối tượng kế tiếp
i=2; a2=6 = x; Tìm thấy x
Tìm kiếm kết thúc thành công
10/37
- TÌM KIẾM TUẦN TỰ
Ví
Ví dụ
dụ 2
- Cho dãy số
a0 a1 a2 a3 a4 a5 a6 a7
3 48 11 36 25 23 42 7
- Minh họa việc tìm số x1=42 và số x2=43 trong
dãy bằng phương pháp tìm kiếm tuần tự
11/37
- TÌM KIẾM TUẦN TỰ
begin
Giải thuật
i=0
No
(i
- TÌM KIẾM TUẦN TỰ
int tktt(int x, int a[], int n)
{ int i=0;
while(i
- TÌM KIẾM TUẦN TỰ CẢI TIẾN
Nhận xét : mỗi lần so sánh đều phải kiểm tra xem
dãy đã hết chưa (i
- TÌM KIẾM TUẦN TỰ CẢI TIẾN
begin
Giải thuật i=0; a[n]=x
No
(x!= a[i])
Yes No
(i
- TÌM KIẾM TUẦN TỰ CẢI TIẾN
int tktt2(int x, int a[], int n)
{ int i=0; a[n]=x;
while(a[i]!=x) i++;
if (i
- TÌM KIẾM TRÊN DÃY ĐÃ SẮP
Với một dãy đã sắp xếp theo theo thứ tự của
khóa tìm kiếm thì việc tìm kiếm về cơ bản sẽ
nhanh hơn
Việc tìm kiếm có thể thực hiện bằng một trong
hai phương pháp
Tìm kiếm tuần tự hoặc
Tìm kiếm nhị phân
17/37
- TÌM KIẾM TUẦN TỰ TRÊN DÃY ĐÃ SẮP
Việc tìm kiếm giống như tìm kiếm trên dãy chưa sắp
Quá trình tìm kiếm kết thúc khi gặp một trong 3 điều
kiện
Gặp đối tượng có khóa bằng với khóa của đối tượng
cần tìm (tìm kiếm thành công)
Gặp đối tượng có khóa “lớn hơn” khóa của đối tượng
cần tìm (tìm kiếm không thành)
Đã duyệt hết dãy (tìm kiếm không thành)
18/37
- TÌM KIẾM TUẦN TỰ TRÊN DÃY ĐÃ SẮP
Ví dụ: a1 a1 a2 a3 a4
Cho dãy số được 1 2 5 6 8
sắp tăng
Tìm số x=4 trong dãy
x
4
i=0 i=1 i=2 Không tìm thấy x
1 2 5 6 8
19/37
- TÌM KIẾM TUẦN TỰ TRÊN DÃY ĐÃ SẮP
begin
Giải thuật
i=0; a[n]=x
No
( a[i]
nguon tai.lieu . vn
