Chương 2 TÌM kím M & S P X P

Tham khảo tài liệu chương 2 tìm kím m & s p x p, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Chương 2 TÌM kím M & S P X P Chương 2 TÌM Ki M & S P X P 2.1. Các gi i thu t tìm ki m 2.1.1. Bài toán tìm ki m 2.1.2. Gi i thu t tìm ki m tuy n tính 2.1.3. Gi i thu t Tìm ki m nh phân 2.2. Các gi i thu t s p x p 2.2.1. Bài toán s p x p 3.2.1 Gi i thu t ñ i ch tr c ti p –Interchange Sort 3.2.2 Gi i thu t ch n tr c ti p-Selection Sort 3.2.3 Gi i thu t chèn tr c ti p-Insert Sort 3.2.4 Gi i thu t n i b t – Bubble Sort 3.2.5 Gi i thu t nhanh – Quick Sort 2.3. Bài t p1 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com 2.1 Các Gi i Thu t Tìm Ki m 2.1.1. Bài toán tìm ki m 2.1.2. Gi i thu t tìm ki m tuy n tính 2.1.3. Gi i thu t Tìm ki m nh phân2 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com 2.1.1 Bài Toán Tìm Ki m Trong th c t , khi thao tác, khai thác d li u h u như lúc nào cũng ph i th c hi n thao tác tìm ki m. K t qu c a vi c tìm ki m có th là không tìm th y ho c tìm th y. N u k t qu là tìm th y thì nhi u khi còn ph i xác ñ nh xem v trí c a ph n t tìm th y là ñâu? Vi c tìm ki m nhanh hay ch m tùy thu c vào tr ng thái và tr t t c a d li u trên ñó. Có 2 thu t toán chính: Tìm ki m tuy n tính & Tìm ki m nh phân3 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com Gi s chúng ta có m t m ng M g m N ph n t . V n ñ ñ t ra là có hay không ph n t có giá tr b ng X trong m ng M? N u có thì ph n t có giá tr b ng X là ph n t th m y trong m ng M?4 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com 2.1.2. Gi i Thu t Tìm Ki m Tuy n Tính Ý Tư ng: Ti n hành so sánh x 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. Ưu ñi m: Thu t toán này có th cho ta th c hi n tìm ki m khi các ph n t trong m ng chưa ñư c s p x p. Như c ñi m: S m t r t nhi u th i gian n u như không có ph n t chúng ta c n tìm.5 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com Minh H a Chưa VD:Tìm x = 14 Tìm th y t i ht v trí th 5 m ng 14 14 12 3 5 1 9 0 10 2 7 1 2 3 4 5 6 7 8 9 10 H tChưa m ng VD:Tìm x = 30 ht không tìm m ng th y 30 12 3 5 1 14 9 0 10 2 7 1 2 3 4 5 6 7 8 9 106 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com Gi i thu t: 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 ; // Th c hi n bư c 3. Bư ...