Bài tập Kỹ thuật lập trình | Trường Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh

1. K thu t l quy 1.1. a. c s chung l n nh t c a 2 s b. Chuy
i m t s n trong h m th p phân thành s trong h b c. S=1+2+3+...+n d. S=12+22+32+...+n2 1.2. a. Cho bi u th c ; bi u th c này có n d t
quy tính S(n). Ví d n=5 thì k t qu là 1.99759. b. Vi ính t ng
c. Dãy Geometric: G(n) = a × rn v i a là s u tiên trong dãy và là t s c nh. Hãy vi quy tính G(n). 1.3. Dãy s xn x1=1; x2=1; xn=xn-1 + (n-1) xn-2 v i n 3 a. Tính x7.
b. Vi t hàm tính xn b ng cách s d quy.
c. Vi t hàm tính xn b ng cách không s d quy.
1.4. Cho m ng m t chi u g m n s nguyên. S d quy vi t các hàm sau: a. Tính t ng các ph n t b. Tìm giá tr l n nh t c. m s nguyên t trong m ng
1.5. H s nh th c (còn g i là s t h p) nh =1, =1 v i m i n 0; = + v i 0a. Hãy vi quy tính h s nh th c
Ví d : khi n=4, k=2 thì k t qu là 6;
khi n=5, k=3 thì k t qu là 10. b. Hãy vi
ng h s nh th c v i chi u cao h v i c nh p t bàn phím. Ví d :
Khi h=6, ta có b ng g m các dòng t n 6. 1 // 1 1 // 1 2 1 // 1 3 3 1 // 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1.6. Cho hai dãy s {xn},{yn ; và n u n xn},{yn c cho theo quy lu t sau: a. Hãy tính x3 và y3
b. Vi t hàm tính xn,yn b ng cách s d qui.
c. Vi t hàm tính xn,yn b ng cách không s d d ng bi n m ng. Yêu c u thu ph c t p là O(n).
1.7. Cho f1=1; f2=1; và fn=fn-1+ fn-2 v i m i n > 2. Hãy tính: (v i n là s a. Hãy tính S5
b. Vi t hàm tính Sn b ng cách s d qui (fn c vi qui).
c. Vi t hàm tính Sn b ng cách không s d n m ng (fn c vi t không s d n m ng). 1.8. Dãy xn a. Tính x7.
b. Vi t hàm tính giá tr c a xn. 1.9. Dãy s xn a. Tính x7.
b. Vi t hàm tính giá tr c a xn. Thu tr 1.10. Bài toán tìm c m g n nhau nh t Trong m t ph ng t OXY cho n m th i có t (xi,yi) v i i=1..n.
Trình bày thu t toán tìm m t c m g n nhau nh t và cho bi ph c t p c a thu t toán Minh h a thu xu t qua ví d sau: n=10
(3;5), (2;2), (0; 5), (1; 1), (1;1), ( 1;1), ( 2;3), ( 1; 2), (3, 4), (3;0) Thu t toán quay lui 1.11.
Cho m ng hai chi u n dòng n c t ch a các s nguyên. Hãy ch n ra n s th u ki n n s
này không cùng dòng, không cùng c t và có t ng là l n nh t. 1.12.
Cho dãy g m n s nguyên. Hãy tìm t t c các t p con có t ng b ng S. 1.13.
Cho dãy g m n s nguyên. Hãy tìm t t c các t p con ch a k s . 1.14.
t thu t toán quay lui gi i bài toán TSP.