Xem mẫu
- Minh H a
Tìm giá tr X = 85 (Tìm th y)
Mid = 5
M[mid]= 46
M
F L
1 12 23 34 46 69 77 85 90
7 59
X
X > M[mid]
11
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
Tìm giá tr X = 85 (Tìm th y)
Mid = 8
M[mid] = 77
F M L
7 12 23 34 46 69 77 85 90
59
X
X > M[mid]
12
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
Tìm giá tr X = 85 (Tìm th y)
Mid = 9
M[mid] = 85
M
F L
7 12 23 34 46 59 69 77 85 90
ðã tìm
X th y t i
v trí 9
X = M[mid]
13
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
Gi s dãy M g m 10 ph n t có khóa như sau (N = 10).
2 3 4 5 8 15 17 22 25 30
Tìm ki m ph n t có giá tr X = 5 (tìm th y):
Ln First>L X= X< X>
First Last Mid M[Mid]
lp ast M[Mid] M[Mid] M[Mid]
B.ñ u 1 10 False 5 8 False True False
1 1 4 False 2 3 False False True
2 3 4 False 3 4 False False True
3 4 4 False 4 5 True
14
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
Gi s dãy M g m 10 ph n t có khóa như sau (N=10).
1 3 4 5 8 15 17 22 25 30
Tìm ki m ph n t có giá tr X = 7 (không tìm th y)
Ln First> X= X< X>
First Last Mid M[Mid]
lp Last M[Mid] M[Mid] M[Mid]
B.ñ u 1 10 False 5 8 False True False
1 1 4 False 2 3 False False True
2 3 4 False 3 4 False False True
3 4 4 False 4 5 False False True
4 5 4 True
15
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:
B1: First = 1
B2: Last = N
B3: IF (First > Last)
B3.1: Không tìm th y
B3.2: Th c hi n Bkt
B4: Mid = (First + Last)/ 2
B5: IF (X = M[Mid])
B5.1: Tìm th y t i v trí Mid
B5.2: Th c hi n Bkt
B6: IF (X < M[Mid])
B6.1: Last = Mid – 1
B6.2: L p l i B3
B7: IF (X > M[Mid])
B7.1: First = Mid + 1
B7.2: L p l i B3
Bkt: K t thúc
16
This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM
© Dương Thành Ph t-www.thayphet.net
www.adultpdf.com
- Cài ð t
int Timnhiphan(int M[ ], int N, int X){
int First = 1; int Last = N;
while (First
- 2.2 Các gi i thu t s p x p
2.2.1. Bài toán s p x p
2.2.2. Gi i thu t ñ i ch tr c ti p –Interchange Sort
2.2.3. Gi i thu t ch n tr c ti p-Selection Sort
2.2.4. Gi i thu t chèn tr c ti p-Insert Sort
2.2.5. Gi i thu t n i b t – Bubble Sort
2.2.6. Gi i thu t nhanh – Quick Sort
18
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.2.1. Bài Toán S p X p
ð thu n ti n và gi m thi u th i gian thao tác mà ñ c
bi t là ñ tìm ki m. Do v y s p x p d li u là m t trong
nh ng thao tác c n thi t và thư ng g p trong quá trình
lưu tr , qu n lý d li u.
S p x p là quá trình x lý m t danh sách các ph n t
ñ ñ t chúng theo m t th t tăng ho c gi m d a trên
n i dung lưu tr trên m i ph n t .
Có r t nhi u thu t toán s p x p song chúng ta ch
quan tâm ñ n 5 gi i thu t s p x p thư ng s d ng.
19
This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM
© Dương Thành Ph t-www.thayphet.net
www.adultpdf.com
- Khái ni m v ngh ch th :
a1 a2 a3 .......... an-1 an
Gi s m ng có th t tăng d n, n u iaj thì
g i là ngh ch th
M c tiêu c a s p x p là kh các ngh ch th (b ng
cách hoán v các ph n t )
20
This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM
© Dương Thành Ph t-www.thayphet.net
www.adultpdf.com
nguon tai.lieu . vn