zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Kỹ thuật tìm kiếm

Chia sẻ: Nguyen Ha | Ngày: | Loại File: PDF | Số trang:25

Báo xấu

86
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong ngành khoa học máy tính, một giải thuật tìm kiếm là một thuật toán lấy đầu vào là một bài toán và trả về kết quả là một lời giải cho bài toán đó, thường là sau khi cân nhắc giữa một loạt các lời giải có thể. Hầu hết các thuật toán được nghiên cứu bởi các nhà khoa học máy tính để giải quyết các bài toán đều là các thuật toán tìm kiếm.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Kỹ thuật tìm kiếm

Bài 2: K Thu t Tìm Ki m (Searching) GV: Nguy n H u Th Khoa CNTT – i H c C u Long 1
N I DUNG 1 1. Tìm ki m tuy n tính 2 2. Tìm ki m nh phân 5 2 CTDL1- Nguy n H u Th
1. Tìm ki m tuy n tính (sequential search) Gi i thu t − Thu t toán ti n hành so sánh x l n lư t v i ph n t th nh t, th hai, ... c a m ng a cho n khi g p ư c ph n t có khóa c n tìm, ho c ã tìm h t m ng mà không th y x. − Các bư c ti n hành như sau : Bư c 1: i = 1; // b t u t ph n t u tiên c a dãy Bư c 2: So sánh a[i] v i x, có 2 kh năng : a[i] = x : Tìm th y. D ng a[i] != x : Sang Bư c 3. Bư c 3 : i = i+1; // xét ti p ph n t k trong m ng N u i >N: H t m ng,không tìm th y.D ng Ngư c l i: L p l i Bư c 2. 3 CTDL1- Nguy n H u Th
1. Tìm ki m tuy n tính (sequential search) int LinearSearch(int a[], int n, int x) { int i=0; while(i
1. Tìm ki m tuy n tính (sequential search) int LinearSearch(int a[], int n, int x) { for(int i=0;i
1. Tìm ki m tuy n tính (sequential search) − Ví d : Cho dãy s a 12 2 8 5 1 6 4 15 − Giá tr c n tìm: 8 i=0 i=1 i=2 6 CTDL1- Nguy n H u Th
1. Tìm ki m tuy n tính (sequential search) 5 V trí = 2 Khóa tìm 0 1 2 3 4 5 6 7 7 13 5 21 6 2 8 15 Tìm thành công S l n so sánh: 3 7 CTDL1- Nguy n H u Th
1. Tìm ki m tuy n tính (sequential search) 9 Khóa tìm 0 1 2 3 4 5 6 7 7 13 5 21 6 2 8 15 Không tìm th y S l n so sánh: 8 8 CTDL1- Nguy n H u Th
1. Tìm ki m tuy n tính (sequential search) − C i ti n cài t: dùng phương pháp “lính canh” t thêm m t ph n t có giá tr x vào cu i m ng B o m luôn tìm th y x trong m ng Sau ó d a vào v trí tìm th y k t lu n. 9 CTDL1- Nguy n H u Th
1. Tìm ki m tuy n tính – pp “lính canh” int LinearSearch(int a[], int n, int x) { int i=0; // m ng g m N ph n t t a[0]..a[N-1] a[n] = x; // thêm lính canh vào cu i dãy (pt th n+1) while(a[i]!=x) i++; if (i
1. Tìm ki m tuy n tính (sequential search) − ánh giá gi i thu t: − V y gi i thu t tìm tu n t có ph c t p tính toán c p n: T(n) = O(n) 11 CTDL1- Nguy n H u Th
1. Tìm ki m tuy n tính (sequential search) Nh n xét: Gi i thu t tìm tuy n tính không ph thu c vào th t c a các ph n t trong danh sách. 12 CTDL1- Nguy n H u Th
2. Tìm ki m nh phân − i v i nh ng dãy ã có th t (gi s th t tăng ), các ph n t trong dãy có quan h a[i-1] ≤ a[i] ≤ a[i+1] − N u x > a[i] thì x ch có th xu t hi n trong o n [a[i+1] ,a[N]] c a dãy − N u x < a[i] thì x ch có th xu t hi n trong o n [a[0] ,a[i-1]] c a dãy . 13 CTDL1- Nguy n H u Th
2. Tìm ki m nh phân − Ý tư ng: T i m i bư c ti n hành so sánh x v i ph n t n m v trí gi a c a dãy tìm ki m hi n hành. D a vào k t qu so sánh này quy t nh gi i h n dãy tìm ki m bư c k ti p là n a trên hay n a dư i c a dãy tìm ki m hi n hành 14 CTDL1- Nguy n H u Th
2. Tìm ki m nh phân Bư c 1: left = 1; right = N; Bư c 2: mid = (left+right)/2; So sánh a[mid] v i x, có 3 kh năng : • a[mid] = x: Tìm th y. D ng • a[mid] > x: //tìm ti p x trong dãy con aleft .. amid -1 : right =mid - 1; • a[mid] < x: //tìm ti p x trong dãy con amid +1 .. aright : left = mid + 1; Bư c 3: N u left ≤ right //còn ph n t chưa xét L p l i Bư c 2. Ngư c l i: D ng; //Ðã xét h t t t c các ph n t . 15 CTDL1- Nguy n H u Th
2. Tìm ki m nh phân int BinarySearch(int a[],int n,int x ) { int left =0, right = n-1, mid; while (left
2. Tìm ki m nh phân 10 Khóa tìm 0 1 2 3 4 5 6 7 8 9 2 8 5 10 12 13 15 18 21 24 left mid right 17 CTDL1- Nguy n H u Th
2. Tìm ki m nh phân 10 Khóa tìm 0 1 2 3 4 5 6 7 8 9 2 8 5 10 12 13 15 18 21 24 left mid right 18 CTDL1- Nguy n H u Th
2. Tìm ki m nh phân 10 Khóa tìm 0 1 2 3 4 5 6 7 8 9 2 8 5 10 12 13 15 18 21 24 left right mid 19 CTDL1- Nguy n H u Th
2. Tìm ki m nh phân 10 Khóa tìm 0 1 2 3 4 5 6 7 8 9 2 8 5 10 12 13 15 18 21 24 left right mid 20 CTDL1- Nguy n H u Th

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

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

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.