Ạ Ọ

Ẵ

TR

Ạ Ọ

ƯỜ KHOA CÔNG NGH THÔNG TIN

Đ I H C ĐÀ N NG NG Đ I H C BÁCH KHOA Ệ

BÁO CÁO:

TH C U TRÚC D LI U

Ữ Ệ

Ấ

ng L u

ườ

ư

1. Lê Hoàng Long 2. Nguy n Tr ễ 07B 09T4

Nhóm h c ph n: ầ ọ L p:ớ

Thành viên nhóm:

Đà N ng, 04/2011

ẵ

N I DUNG BÁO CÁO

Ộ

Yêu c u bài toán: ầ Đ 1: Vi ế

ề ơ ự ắ ươ ị ươ l n nh t trong m ng theo ph ng pháp đ qui t chu ng trình th c hi n các công vi c sau: ệ ầ d theo ph ấ 1. S p x p m ng tăng d n theo ph ả ế 2. Hãy tìm ph n t ầ ử 3. Tìm ph n t ầ ử ớ ệ ng pháp ch n tr c ti p ự ế ọ ng pháp tìm ki m nh phân ế ệ ươ ả

Gi

i quy t yêu c u:

ả

ế

ầ

ư

ế

ả

ấ i quy t trong m ng, do đó, đ không m t

ể

ả ầ ầ tính t ng quát, ta s nh p vào m t m ng ng u nhiên.

ả

ẫ

ổ

Hàm nh p m ng ng u nhiên ả

ậ

ẽ ậ ẫ

void nhap(int n) {

srand(unsigned) time(0)); for(i=0;i

a[i]=rand()%n +10;

}

ị ủ

ự

ệ

ả

ấ

ả

ầ

Sau khi th c hi n, ta c n ph i xu t giá tr c a m ng ra màn hình theo hàm ấ

xu t sau: void xuat() { for(i=0;i

M đ u: ở ầ Bài toán đ a ra yêu c u c n gi ộ

1. S p x p m ng theo ph

ả

ươ

ng pháp ch n tr c ti p ự ế ọ

Ph

ắ ế a. Thu t toán ậ ươ

ng pháp ch n tr c ti p: ọ

ự ế

•

Gi

i thu t ả ậ

a ứ ự ộ ậ ự ế ầ ử i luôn là min(ai, ai+1, ., an-1). Ý ữ ỏ ầ ử ầ ử ỏ ấ ả ự ế ọ : ch n ph n t ọ ầ ề ị ệ ỉ

ng thu t toán là th c hi n N-1 ặ ạ . Dãy ban đ u có N ph n t ầ ầ ử ậ ệ ắ đ u dãy. Các Ta th y r ng, n u m ng có th t , ph n t ấ ằ ế ế ự ng c a thu t toán ch n tr c ti p mô ph ng m t trong nh ng cách s p x p t ủ ắ ban đ u, đ a nh nh t trong N ph n t ư ấ ầ này v v trí đúng là đ u dãy hi n hành; sau đó không quan tâm đ n nó ế ệ v trí th c a dãy ban đ u, b t đ u t ứ ắ ầ ừ ị ầ ầ ử ủ ầ i quá trình trên cho dãy hi n hành... đ n khi dãy hi n hành ch còn 1 ph n ỉ ệ ế t ý t ưở nh nh t trong dãy hi n hành v v trí đúng ệ ệ , v y tóm t ấ ự ở ầ ầ ử ỏ ậ ề ị t ưở nhiên nh t trong th c t ph n t ầ ử n a, xem dãy hi n hành ch còn N-1 ph n t ữ 2; l p l t ử l ượ b ướ t vi c đ a ph n t c ti n hành nh sau : ư ệ ư ế

• B c 1 ướ • B c 2 ướ

• B c 3 : ướ • B c 4 ướ Ng

: i = 1; : Tìm ph n t a[min] nh nh t trong dãy hi n hành t ầ ử ệ ấ ỏ ừ a[i] đ nế a[N] ị

•

đã n m đúng v trí. Hoán v a[min] và a[i] : N uế i < N-1 thì i = i+1; L p l i: D ng. //N-1 ph n t ầ ử ừ c l ượ ạ i B c 2 ặ ạ ướ ằ ị

S đ kh i ơ ồ ố

•

Cài đ t ặ

Cài đ t thu t toán s p x p ch n tr c ti p thành hàm sapxep() ọ ự ế ế ặ ậ ắ

//hoan vi a[min] va a[i]

void sapxep() //bang phuong phap chon truc tiep { int j,tam,min; for (i=0;ia[j]){ tam= a[min]; a[min]=a[j]; a[j]=tam;}} }

2. Ph

ng pháp tìm ki m nh phân

ươ

ế

ị

• Gi ả

i thu t ậ

i thì x ch có th xu t hi n trong đo n [a ấ

1 ,ai- ớ ạ i h n ng c a ủ ưở v trí gi a c a ữ ủ i h n dãy ớ ạ ệ

(gi tăng), các ph n t ố ố ớ c n u x > a đó k t lu n đ ừ s th t ả ử ứ ự ậ ượ ế Ð i v i nh ng dãy s đã có th t ứ ự ế trong dãy ầ ử ấ i thì x ch có th xu t ỉ ể ệ i n u x < a c l ể ệ ạ ụ ớ ủ ạ i thu t là t ậ ả ỗ ướ ế ữ có quan hệ ai -1 � ai � ai+1, t hi n trong đo n ạ [ai+1 ,aN] c a dãy , ng ượ ạ ế ủ 1] c a dãy . Gi ể ậ ị ph m vi tìm ki m sau m i l n so sánh x v i m t ph n t trong dãy. Ý t ầ ử ỗ ầ c ti n hành so sánh x v i ph n t gi n m ầ ử ằ ở ị ế 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 ể ả ế ự tìm ki m ỉ i thu t tìm nh phân áp d ng nh n xét trên đây đ tìm cách gi ậ ả ộ ế i m i 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. b ế ở ướ ế ế ế ị ế ử ướ ủ ử

• B c 1:

s dãy tìm ki m hi n hành bao g m các ph n t ầ ử aleft .. aright , các b ế ệ ồ ướ ế c ti n ả ử Gi hành nh sau : ư

• B c 2:

ướ left = 1; right = N; // tìm ki mế trên t ấ ả ầ t c các ph n ử t

ướ

left .. amid -1 :

• mid = (left+right)/2; // l y m c so sánh • So sánh a[mid] v i x, có ớ o a[mid] = x: Tìm th y. D ng o a[mid] > x: //tìm ti p x trong dãy con a right =midle - 1;

ố ấ 3 kh năng : ả ừ ấ ế

o a[mid] < x: //tìm ti p x trong dãy con amid +1 .. aright :

ế

left = mid + 1; • B c 3: ướ

• N u left ế

• Ng

ch a xét ầ ử ư ? tìm ti p. ế L p l ? right //còn ph n t i B c 2. ặ ạ ướ

• Cài đ t ặ

i: D ng; //Ðã xét h t t t c các ph n t c l ượ ạ ế ấ ả . ầ ử ừ

int tim(int d, int dau, int cuoi) // ham tim kiem bang pp nhi phan { int giua; if (d>a[cuoi] ||d

Thu t toán tìm nh phân có th đ c cài đ t thành hàm BinarySearch: ể ượ ậ ị ặ

4. Tìm ph n t ng pháp đ qui ầ ử ớ l n nh t theo ph ấ ươ ệ

i thu t: ậ đ u tiên c a m ng là b= a[0] ả ế i: n u a[i]>max, gán b = a[i] ế • Gi ả B1: gán ph n t ủ ầ ử ầ B2: n u i++ == N thì return b c l Ng ượ ạ Return max(b,i);

• Cài đ t: ặ

int max(int b,int i)

{ if(i++==N) return b; else { if(a[i]>b) b=a[i]; return max(b,i); } }

K t qu ch y ch ng trình: ả ạ ế ươ