BÀI TẬP CÔNG NGHỆ THÔNG TIN TRƯỜNG ITC_3

Chia sẻ: Trần Ngọc Mai | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

160
lượt xem 10
download

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

Tham khảo tài liệu 'bài tập công nghệ thông tin trường itc_3', 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ả

Chủ đề:

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

Lưu

Nội dung Text: BÀI TẬP CÔNG NGHỆ THÔNG TIN TRƯỜNG ITC_3

Minh H a Cho dãy có 8 ph n t S p x p theo vi trí tăng d n i=1; j=3 L R X=2 1 2 3 5 7 9 10 15 i j L=1 R=3 ðo n c n s px p 71 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 Cho dãy có 8 ph n t S p x p theo vi trí tăng d n 1 2 3 5 7 9 10 15 Không còn ño n nào c n s p x p ðo n c n s px p 72 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
10 5 7 3 9 2 15 1 ðo n [1- 8] 7 9 5 15 10 ðo n [4- 8] 9 7 15 10 ðo n [5- 8] 9 10 15 ðo n [6- 8] ðo n [6- 7] 9 10 5 7 ðo n [4- 5] ðo n [1- 3] 1 2 3 73 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ư c 2: j=N; Trong khi (j>i) th c hi n: N u a[j]N-1: H t dãy, d ng Ngư c l i: L p l i Bư c 2 74 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
void QuickSort(int M[], int First, int Last) Cài ð t { int i, j, tam, x; x = M[(First+Last)/2]; i = First; j = Last; do { while (M[i] X) j--; if (i
ðánh giá gi i thu t: + Trư ng h p t t nh t, khi m ng M có th t tăng: S phép gán: Gmin = N-1 S phép so sánh: Smin = N×Log2(N)/2 S phép hoán v : Hmin = 0 + Trư ng h p x u nh t, khi ph n t X ñư c ch n gi a dãy con là giá tr l n nh t: S phép gán: Gmax = N×(N-1)/2 S phép so sánh: Smax = (N-1)×(N-1) S phép hoán v : Hmax = N×(N-1)/2 + Trung bình: S phép gán: Gavg = (N-1)×(N+2)/4 S phép so sánh: Savg = N×[Log2(N)+2N–2]/4 S phép hoán v : Havg = N×(N-1)/4 76 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
Chi phí trung bình O(n*log2n) Chi phí cho trư ng h p x u nh t O(n2) Chi phí này ph thu c vào cách ch n ph n t tr c: - N u ch n ñư c ph n t có giá tr trung bình ta s chia thành 2 dãy b ng nhau - N u ch n nh m ph n t nh nh t (hay l n O(n2) nh t) 77 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.3 Bài T p 1. Trình bày tư tư ng và minh h a gi i thu t tìm ki m tuy n tính, tìm ki m nh phân 2. Cài ñ t thu t toán tìm tuy n tính b ng cách: - S d ng vòng l p for - S d ng vòng l p while 3. Trong trư ng h p các ph n t c a dãy ñã có th t tăng (ho c gi m) hãy cài ñ t l i thu t toán tìm nh phân 78 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
1. Trình bày tư tư ng và minh h a 5 gi i thu t s p x p 2. Cài ñ t 5 gi i thu t s p x p theo các trư ng h p và ñi n k t qu s l n th c hi n các phép toán vào b ng sau: 79 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com