Bài tập Cấu trúc dữ liệu và giải thuật: Kinh nghiệm giải, bài tập hay

Bài t p c u trúc d li u và gi i thu tậ ấ ữ ệ ả ậ

Trang 1

Chương 1

T ng quan v c u trúc d li u và gi i thu tổ ề ấ ữ ệ ả ậ

Vi t ch ng trình hoàn ch nh cho các bài toán sau đâyế ươ ỉ

(các bài t p v ôn t p, các bài t p v rèn luy n cách l a ch n m t c u trúcậ ề ậ ậ ề ệ ự ọ ộ ấ

d li u thích h p; m t thu t toán thích h p cho v n đ bài toán)ữ ệ ợ ộ ậ ợ ấ ề

BT1-1. Cho n s nguyên d ng aố ươ 0,a1,a2,...,an-1.

a.Chèn ph n t x vào v trí k c a dãy.ầ ử ị ủ

b.Xóa t t c các s nguyên t trong dãy.ấ ả ố ố

BT1-2. Cho ma tr n vuông n dòng n c t; m i ph n t c a ma tr n là m t phân sậ ộ ỗ ầ ử ủ ậ ộ ố

(gi thi t r ng t s và m u s c a các phân s này là các s nguyên). Hãy th cả ế ằ ử ố ẫ ố ủ ố ố ự

hi n các yêu c u sau:ệ ầ

a.Tìm phân s có giá tr nh nh t n m trong kho ng.(0;1).ố ị ỏ ấ ằ ả

b.Đm s l ng phân s n m trong ma tr n tam giác trên có giá tr n mế ố ượ ố ằ ậ ị ằ

trong kho ng (0,1)ả

c.S p x p các phân s trong ma tr n tăng d n t trái qua ph i và t trênắ ế ố ậ ầ ừ ả ừ

xu ng d i.ố ướ

BT1-3.Vi t ch ng trình t o m t t p tin văn b n ế ươ ạ ộ ậ ả có tên là “DAYSO.INP” có c uấ

trúc nh sau:ư

-Dòng đu tiên ghi n (n là s nguyên d ng nh p t bàn phím).ầ ố ươ ậ ừ

-Trong các dòng ti p theo ghi n s nguyên ng u nhiên trong ph m vi t 1ế ố ẫ ạ ừ

đn 10000, m i dòng 10 s (các s cách nhau ít nh t m t d u cách).ế ỗ ố ố ấ ộ ấ

Hãy th c hi n các công vi c sau đây: ự ệ ệ

a.Tìm giá tr l n nh t c a các s trong t p tin DAYSO.INP.ị ớ ấ ủ ố ậ

b.Đm s l ng s ch n, s l ng s l trong t p tin DAYSO.INP.ế ố ượ ố ẵ ố ượ ố ẻ ậ

c.Hãy đm s l ng s nguyên t , s chính ph ng, s hoàn h o, sế ố ượ ố ố ố ươ ố ả ố

Amstrong trong t p tin DAYSO.INP.ậ

Hãy ghi k t qu c a các câu a,b,c trên vào t p tin văn b n có tên làế ả ủ ậ ả

“DAYSO.OUT”.

Bài t p c u trúc d li u và gi i thu tậ ấ ữ ệ ả ậ

Trang 2

BT1-4.Vi t ch ng trìnhế ươ t o t p tin văn b n có tên là “BANGSO.INP” có c uạ ậ ả ấ

trúc nh sau:ư

-Dòng đu tiên ghi hai s m và n (m, n là các s nguyên d ng nh p t bànầ ố ố ươ ậ ừ

phím)

-Trong m dòng ti p theo m i dòng ghi n s nguyên ng u nhiên trong ph mế ỗ ố ẫ ạ

vi t 0 đn 1000 (các s cách nhau ít nh t m t d u cách)ừ ế ố ấ ộ ấ

Hãy th c hi n các công vi c sau: ự ệ ệ

a.Hãy cho bi t ch s các dòng có ch a s nguyên t (gi thi t các dòngế ỉ ố ứ ố ố ả ế

trong t p tin văn b n đc đánh s t 0 đn m-1).ậ ả ượ ố ừ ế

b.Xoay vòng các c t qua ph i m t v trí (c t 0 s qua c t 1, c t 1 qua c tộ ả ộ ị ộ ẽ ộ ộ ộ

2,... c t n-1 v c t 0).ộ ề ộ

c.S p x p các ph n t tăng d n trên t ng c t.ắ ế ầ ử ầ ừ ộ

Hãy ghi các k t qu trên vào file văn b n có tên là “BANGSO.OUT”.ế ả ả

BT1-5. Cho m ng m t chi u g m n t a đ đi m (gi s hoành đ và tung đả ộ ề ồ ọ ộ ể ả ử ộ ộ

c a các đi m là các s nguyên).ủ ể ố

a.Hãy tìm m t đi m trong m ng xa g c t a đ nh t.ộ ể ả ố ọ ộ ấ

b.Hãy tìm t a đ hai đi m g n nhau nh t.ọ ộ ể ầ ấ

c.Hãy xác đnh t a đ c a hình ch nh t nh nh t bao h t c n đi m trênị ọ ộ ủ ữ ậ ỏ ấ ế ả ể

(t a đ góc trên bên trái và t a đ góc d i bên ph i c a hình ch nh t).ọ ộ ọ ộ ướ ả ủ ữ ậ

Ví d n = 5 và t a đ 5 đi m là: (0,0); (0,3); (3,3); (4,1); (4,4).ụ ọ ộ ể

Thì k t qu câu a là đi m (4,4), k t qu câu b là (3,3) và (4,4), k t qu câuế ả ể ế ả ế ả

c là (0,4); 4(,0).

BT1-6.Cho dãy n s nguyên ốa0,a1,...,an-1. Hãy chuy n k ph n t đu tiên c a dãyể ầ ử ầ ủ

v cu i dãy.ề ố

BT1-7.Gi s n ả ử 1 và x là s th c. Hãy vi t hàm tính giá tr c a bi u th c sauố ự ế ị ủ ể ứ

đây (v i đ ph c t p tuy n tính):ớ ộ ứ ạ ế

xxxx

xnS

...

)1(...

),(











BT1.8.Tìm s h ng th n c a dãy Fibonasci (gi i quy t khi n là m t s l n – khiố ạ ứ ủ ả ế ộ ố ớ

đó ta không th s d ng đ quy và cũng không th s d ng m ng đ l u tr ).ể ử ụ ệ ể ử ụ ả ể ư ữ

Bài t p c u trúc d li u và gi i thu tậ ấ ữ ệ ả ậ

Trang 3

BT1-9. Gi s n ả ử  0 và x là s th c.Hãy tính giá tr c a bi u th c sau đây.ố ự ị ủ ể ứ

S(n,x) =

...

!3!2!1

xxxx n



BT1-10.a.Cho dãy n s nguyên aố0,a1,...,an-1.Hãy tìm dãy con liên ti p tăng dài nh t.ế ấ

b.Cho dãy n s nguyên aố0,a1,...,an-1.Hãy tìm đo n con dài nh t ch a toàn sạ ấ ứ ố

c.Cho dãy n s nguyên aố0,a1,...,an-1.Hãy tìm dãy con tăng ch a nhi u sứ ề ố

nguyên t nh t.ố ấ

BT1-11.a.C ng hai s nguyên l n a và b, trong đó s a có m ch s và s b có n ộ ố ớ ố ữ ố ố

ch s .ữ ố

S nguyên l n đây là s có th có đn vài trăm ch s . Đ l u tr các số ớ ở ố ể ế ữ ố ể ư ữ ố

nguyên l n này ta có th dùng chu i (m i ký t c a chu i là m t ch s ) ho cớ ể ỗ ỗ ự ủ ỗ ộ ữ ố ặ

dùng m ng m t chi u (m i ph n t c a m ng m t chi u là m t ch s ). Tuyả ộ ề ỗ ầ ử ủ ả ộ ề ộ ữ ố

nhiên trong hai ph ng án này thì ph ng án dùng m ng m t chi u đ l u tr sươ ươ ả ộ ề ể ư ữ ẽ

có thu t toán t t h n.ậ ố ơ

b.Th c hi n phép tr hai s nguyên l n.ự ệ ừ ố ớ

c.Th c hi n phép nhân hai s nguyên l n.ự ệ ố ớ

d.Th c hi n phép chia hai s nguyên l n.ự ệ ố ớ

BT1-12.Cho dãy n s nguyên {aối, đây gi s i=1..n} Dãy con liên ti p là dãy màở ả ử ế

thành ph n c a nó là các thành ph n liên ti p nhau trong {a}, ta g i t ng c a dãyầ ủ ầ ế ọ ổ ủ

con là t ng t t c các thành ph n c a nó. Tìm t ng l n nh t trong t t c cácổ ấ ả ầ ủ ổ ớ ấ ấ ả

t ng c a các dãy con c a {a}.ổ ủ ủ

Ví d n u n = 7;ụ ế

4 –5 6 –4 2 3 -7

Thì k t qu t ng là 7.ế ả ổ

Ph n g i ý:ầ ợ

BT1.9.

Algorithms1: O(N2)

float s=1;

Bài t p c u trúc d li u và gi i thu tậ ấ ữ ệ ả ậ

Trang 4

for (int i=1;i<=n;i++)

s=s+pow(x,i)/giaithua(i);// giaithua(i) = i!=1.2.3….i

Đ ph c t p theo cách này là ộ ứ ạ O(N2), tuy nhiên ch ng trình không th th cươ ể ự

hi n đc khi n l n; ch ng h n n =100 - do phép tính giai th a c a n không thệ ượ ớ ẳ ạ ừ ủ ể

th c hi n..ự ệ

Algorithms2: O(N2)

float s=1,p;

for (int i=1; i<=n;i++)

{

p=1;

for (int j=1; j<=i;j++)

p=p*x/j;

s=s+p;

}

Đ ph c t p theo cách này v n là là ộ ứ ạ ẫ O(N2), tuy nhiên ch ng trình đã ươ

không c n tính giai th a c a n.ầ ừ ủ

Algorithms3: O(N) – đ ph c t p tuy n tínhộ ứ ạ ế

float s=1,p=1;

for (int i=1;i<=n;i++)

{

p=p*x/i;

s=s+p;

}

BT1-11.a.

Nh p m ch s c a s a, l u vào m ng m t chi u a.ậ ữ ố ủ ố ư ả ộ ề

Nh p n ch s c a s b, l u vào m ng m t chi u b. ậ ữ ố ủ ố ư ả ộ ề

Gi s ta có hai s a=97895 và b = 6478ả ử ố

i 0 1 2 3 4

a[i] 9 7 8 9 5

Bài t p c u trúc d li u và gi i thu tậ ấ ữ ệ ả ậ

Trang 5

B[i] 6 4 7 8

L u ý n u khi nh p mà không gi ng hàng bên ph i thì k t qu s sai, ta cóư ế ậ ố ả ế ả ẽ

th ti n hành nh p hai s a,b theo cách sau đ kh c ph c tình tr ng này:ể ế ậ ố ể ắ ụ ạ

Đt max là s l n nh t trong hai giá tr m và n.ặ ố ớ ấ ị

Vi c nh p hai s a ,b đc ti n hành nh sau:ệ ậ ố ượ ế ư

for i=max-m+1;i<=max;i++

cin>>a[i];

for i=max-n+1;i<=max;i++

cin>>b[i];

Sau đó th c hi n phép c ng nh cách thông th ng:ự ệ ộ ư ườ

remember=0;

for (i=max; i >=1;i--)

{

c[i]=(a[i]+b[i]+remember)%10;

remember=(a[i]+b[i]+remember)/10;

}

c[0]=remember;

m ng c[i] chính là t ng c a hai s a và b.ả ổ ủ ố

L u ý là giá tr c[0] này ch xu t ra khi nó khác 0.ư ị ỉ ấ

Đo n ch ng trình xu t k t qu nh sau:ạ ươ ấ ế ả ư

if (c[0]!=0) cout<<c[0];

for (i=1;i<=max;i++)

cout<<c[i];

D li u th :ữ ệ ử

m =5; n = 4;

a = 97895, b = 6478

Giá tr c a các ph n t c a hai m ng a và b là:ị ủ ầ ử ủ ả

a[1] = 9, a[2]=7; a[3]=8; a[4]=9. a[5]=5.

b[2] = 6, b[3]=4; b[4]=7; b[5]=8

Bài tập Cấu trúc dữ liệu và giải thuật

Chủ đề:

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi