Bài giảng Chương 4: Các thuật toán tìm kiếm
lượt xem 4
download
Nội dung bài giảng trình bày khái niệm tìm kiếm; bài toán tìm kiếm; các thuật toán tìm kiếm; tìm kiếm trên dãy chưa sắp; tìm kiếm tuần tự; tìm kiếm tuần tự cải tiến; tìm kiếm tuần tự trên dãy đã sắp... Để nắm chắc kiến thức mời các bạn cùng tham khảo bài giảng "Chương 4: Các thuật toán tìm kiếm".
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Chương 4: Các thuật toán tìm kiếm
- 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]
CÓ THỂ BẠN MUỐN DOWNLOAD
-
BÀI GIẢNG " CHƯƠNG 4 TẠO CÁC ĐỐI TƯỢNG 3D TỪ ĐỐI TƯỢNG 2D"
10 p | 920 | 280
-
BÀI GIẢNG " CHUONG 2 VẼ CÁC ĐỐI TƯỢNG 2D"
8 p | 748 | 261
-
Bài giảng Đồ họa kỹ thuật 2 - Vẽ kỹ thuật xây dựng với Autocad: Chương 4 - Hướng dẫn sử dụng AutoCad
20 p | 369 | 50
-
Bài giảng Chương trình tin học lớp 10 - Bài 4: Bài toán và thuật toán
22 p | 151 | 20
-
Bài giảng Tính toán song song (Parallel computing): Chương 4 - TS. Ngô Văn Thanh
50 p | 122 | 15
-
Bài giảng Chương 4: Các kỹ thuật kiểm tra tính đúng đắn và tính an toàn của chương trình phần mềm - TS. Vũ Thị Hương Giang
128 p | 293 | 15
-
Bài giảng Mạng máy tính: Chương 4 - Phạm Văn Nam
38 p | 94 | 7
-
Bài giảng Nhập môn chương trình dịch: Chương 4 (tt) - Hoàng Anh Việt
47 p | 48 | 7
-
Bài giảng Chương 4 - Khai phá luật kết hợp
73 p | 110 | 6
-
Bài giảng Kỹ thuật lập trình – Chương 4: Kỹ thuật viết mã nguồn hiệu quả
50 p | 24 | 6
-
Bài giảng Lập trình cơ bản: Chương 4 - Giải thuật xử lý thông tin và ngôn ngữ lập trình
36 p | 100 | 5
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Bùi Tiến Lên
50 p | 35 | 5
-
Bài giảng Học máy (IT 4862): Chương 4.6 - Nguyễn Nhật Quang
11 p | 41 | 5
-
Bài giảng Kỹ thuật lập trình - Chương 4: Các kiểu dữ liệu có cấu trúc
45 p | 30 | 3
-
Bài giảng Kỹ thuật lập trình - Chương 4: Kỹ thuật viết mã nguồn hiệu quả (Trường Đại học Bách khoa Hà Nội)
48 p | 17 | 3
-
Bài giảng Lập trình hướng đối tượng: Chương 4 - Các kỹ thuật xây dựng hàm, sử dụng biến, hằng trong lập trình hướng đối tượng
29 p | 18 | 3
-
Bài giảng Cơ sở kỹ thuật lập trình: Chương 4 - Cấu trúc mảng và con trỏ
44 p | 66 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn