Bài 6/1999 - Giao đi m các đ ng th ngể ườ ẳ
(Dành cho h c sinh THPTọ)
Trên m t ph ng cho tr c n đ ng th ng. Hãy tính s giao đi m c a các đ ng th ng này. Yêu c u tínhặ ẳ ướ ườ ẳ ố ể ủ ườ ẳ ầ
càng chính xác càng t t.ố
Các đ ng th ng trên m t ph ng đ c cho b i 3 s th c A, B, C v i ph ng trình Ax + By + C = 0, ườ ẳ ặ ẳ ượ ở ố ự ớ ươ ở
đây các s A, B không đ ng th i b ng 0.ố ồ ờ ằ
D li u vào c a bài toán cho trong t p B6.INP có d ng sau:ữ ệ ủ ệ ạ
- Dòng đ u tiên ghi s nầ ố
- n dòng ti p theo, m i dòng ghi 3 s th c A, B, C cách nhau b i d u cách.ế ỗ ố ự ở ấ
K t qu c a bài toán th hi n trên màn hình.ế ả ủ ể ệ
Bài 7/1999 - Mi n m t ph ng chia b i các đ ng th ngề ặ ẳ ở ườ ẳ
(Dành cho h c sinh THPTọ)
Xét bài toán t ng t nh bài 6/1999 nh ng yêu c u tính s mi n m t ph ng đ c chia b i n đ ngươ ự ư ư ầ ố ề ặ ẳ ượ ở ườ
th ng này:ẳ
Trên m t ph ng cho tr c n đ ng th ng. Hãy tính s mi n m t ph ng đ c chia b i các đ ng th ngặ ẳ ướ ườ ẳ ố ề ặ ẳ ượ ở ườ ẳ
này. Yêu c u tính càng chính xác càng t t.ầ ố
Các đ ng th ng trên m t ph ng đ c cho b i 3 s th c A, B, C v i ph ng trình Ax + By + C = 0, ườ ẳ ặ ẳ ượ ở ố ự ớ ươ ở
đây các s A, B không đ ng th i b ng 0.ố ồ ờ ằ
D li u vào c a bài toán cho trong t p B7.INP có d ng sau:ữ ệ ủ ệ ạ
- Dòng đ u tiên ghi s nầ ố
- n dòng ti p theo, m i dòng ghi 3 s th c A, B, C cách nhau b i d u cách.ế ỗ ố ự ở ấ
K t qu c a bài toán th hi n trên màn hình.ế ả ủ ể ệ
Bài 10/1999 - Dãy s nguyênố
(Dành cho h c sinh THCSọ)
Dãy các s t nhiên đ c vi t ra thành m t dãy vô h n trên đ ng th ng:ố ự ượ ế ộ ạ ườ ẳ
1234567891011121314..... (1)
H i s v trí th 1000 trong dãy trên là s nào?ỏ ố ở ị ứ ố
Em hãy làm bài này theo hai cách: Cách 1 dùng suy lu n logic và cách 2 vi t ch ng trình đ tính toán vàậ ế ươ ể
so sánh hai k t qu v i nhau.ế ả ớ
T ng quát bài toán trên: Ch ng trình yêu c u nh p s K t bàn phím và in ra trên màn hình k t qu là sổ ươ ầ ậ ố ừ ế ả ố
n m v trì th K trong dãy (1) trên. Yêu c u ch ng trình ch y càng nhanh càng t t.ằ ở ị ứ ầ ươ ạ ố
Bài 11/1999 - Dãy s Fibonaci ố
(Dành cho h c sinh THCSọ)
Nh các b n đã bi t dãy s Fibonaci là dãy 1, 1, 2, 3, 5, 8, .... Dãy này cho b i công th c đ qui sau:ư ạ ế ố ở ứ ệ
F1 = 1, F2 =1, Fn = Fn-1 + Fn-2 v i n > 2ớ
1. Ch ng minh kh ng đ nh sau:ứ ẳ ị
M i s t nhiên N đ u có th bi u di n duy nh t d i d ng t ng c a m t s s trong dãy s Fibonaci.ọ ố ự ề ể ể ễ ấ ướ ạ ổ ủ ộ ố ố ố
N = akFk + ak-1Fk-1 + .... a1F1
V i bi u di n nh trên ta nói N có bi u di n Fibonaci là aớ ể ễ ư ể ễ kak-1...a2a1.
2. Cho tr c s t nhiên N, hãy tìm bi u di n Fibonaci c a s N.ướ ố ự ể ễ ủ ố
Input:
T p văn b n P11.INP bao g m nhi u dòng. M i dòng ghi m t s t nhiên.ệ ả ồ ề ỗ ộ ố ự
Output:
Lê Th Hi uị ế 2
T p P11.OUT ghi k t qu c a ch ng trình: trên m i dòng ghi l i bi u di n Fibonaci c a các s tệ ế ả ủ ươ ỗ ạ ể ễ ủ ố ự
nhiên t ng ng trong t p P11.INP.ươ ứ ệ
Bài 12/1999 - N-mino
(Dành cho h c sinh THPTọ)
N-mino là hình thu đ c t N hình vuông 1ượ ừ ×1 ghép l i (c nh k c nh). Hai n-mino đ c g i là đ ngạ ạ ề ạ ượ ọ ồ
nh t n u chúng có th đ t ch ng khít lên nhau.ấ ế ể ặ ồ
B n hãy l p ch ng trình tính và v ra t t c các N-mino trên màn hình. S n nh p t bàn phím.ạ ậ ươ ẽ ấ ả ố ậ ừ
Ví d : V i N=3 ch có hai lo i N-mino sau đây:ụ ớ ỉ ạ
3-mino th ng 3-mino hình th c thẳ ướ ợ
Chú ý: G i Mn là s các n-mino khác nhau thì ta có Mọ ố 1=1, M2=1, M3=2, M4=5, M5=12, M6=35,...
Yêu c u bài gi i đúng và trình bày đ p.ầ ả ẹ
Bài 13/1999 - Phân ho ch hình ch nh tạ ữ ậ
(Dành cho h c sinh THPTọ)
M t hình vuông có th chia thành nhi u hình ch nh t có các c nh song song v i c nh hình vuông (xemộ ể ề ữ ậ ạ ớ ạ
Hình v ). Xây d ng c u trúc d li u và l p ch ng trình mô t phép chia đó. Tính xem có bao nhiêu cáchẽ ự ấ ữ ệ ậ ươ ả
chia nh v y. ư ậ
Input
D li u nh p vào t t p P13.INP bao g m hai s t nhiên là n, m - kích th cữ ệ ậ ừ ệ ồ ố ự ướ
hình ch nh t.ữ ậ
Output
D li u ra n m trong t p P13.OUT có d ng sau:ữ ệ ằ ệ ạ
- Dòng đ u tiên ghi s K là t ng s các phép phân ho ch.ầ ố ổ ố ạ
- Ti p theo là K nhóm, m i nhóm cách nhau b ng m t dòng tr ng.ế ỗ ằ ộ ố
- M i nhóm d li u bao g m các c p t a đ c a các hình ch nh t n m trongỗ ữ ệ ồ ặ ọ ộ ủ ữ ậ ằ
phân ho ch.ạ
Bài 16/2000 - Chia số
(Dành cho h c sinh THCSọ)
B n hãy chia Nạ2 s 1, 2, 3, ...., Nố2-1, N2 thành N nhóm sao cho m i nhóm có s các s h ng nh nhau vàỗ ố ố ạ ư
có t ng các s này cũng b ng nhau.ổ ố ằ
Bài 17/2000 - S nguyên t t ng đ ngố ố ươ ươ
(Dành cho h c sinh THCSọ)
Hai s t nhiên đ c g i là ố ự ượ ọ Nguyên t t ng đ ngố ươ ươ n u chúng có chung các c s nguyên t . Ví dế ướ ố ố ụ
các s 75 và 15 là nguyên t t ng đ ng vì cùng có các c nguyên t là 3 và 5. Cho tr c hai s tố ố ươ ươ ướ ố ướ ố ự
nhiên N, M. Hãy vi t ch ng trình ki m tra xem các s này có là nguyên t t ng đ ng v i nhau hayế ươ ể ố ố ươ ươ ớ
không.
Tin h c & Nhà tr ngọ ườ 100 Đ Toán - Tin h cề ọ
Lê Th Hi uị ế 3
Bài 18/2000 - Sên bò
(Dành cho h c sinh THCS và THPTọ)
Trên l i ô vuông m t con sên xu t phát t đ nh (0,0) c n ph i đi đ n đi m k t thúc t i (N,0) (N là s tướ ộ ấ ừ ỉ ầ ả ế ể ế ạ ố ự
nhiên cho tr c). ướ
Qui t c đi: M i b c (xắ ỗ ướ 1, y1) --> (x2, y2) tho mãn đi u ki n (sên bò): ả ề ệ
- x2 x1+1,
- y1 -1 <= y2 <= y1+1
Tìm m t cách đi sao cho trong quá trình đi nó có th lên cao nh t trên tr c tung (t c là t a đ y đ t c cộ ể ấ ụ ứ ọ ộ ạ ự
đ i). Ch c n đ a ra m t nghi m.ạ ỉ ầ ư ộ ệ
Input
S N đ c nh p t bàn phím.ố ượ ậ ừ
Output
Output ra file P5.OUT có d ng:ạ
- Dòng đ u tiên ghi 2 s : m, h. Trong đó m là s các b c đi c a con sên đ đ n đ c v trí đích, h ghi l iầ ố ố ướ ủ ể ế ượ ị ạ
đ cao c c đ i đ t đ c c a con sên.ộ ự ạ ạ ượ ủ
- m dòng ti p theo, m i dòng ghi ra l n l t các t a đ (x,y) là các b c đi c a sên trên l i.ế ỗ ầ ượ ọ ộ ướ ủ ướ
Yêu c u k thu tầ ỹ ậ
Các b n có th mô t các b c đi c a con sên trên màn hình đ h a. Đ đ t đ c m c đích đó s N c nạ ể ả ướ ủ ồ ọ ể ạ ượ ụ ố ầ
đ c ch n không v t quá 50. M c dù không yêu c u nh ng nh ng l i gi i có mô ph ng đ h a s cóượ ọ ượ ặ ầ ư ữ ờ ả ỏ ồ ọ ẽ
đi m cao h n n u không mô ph ng đ h a.ể ơ ế ỏ ồ ọ
Bài 19/2000 - Đa giác
(Dành cho h c sinh THPTọ)
Hãy tìm đi u ki n c n và đ đ N s th c d ng a1, a2, ..., aN t o thành các c nh liên ti p c a m t đaề ệ ầ ủ ể ố ự ươ ạ ạ ế ủ ộ
giác N c nh trên m t ph ng. Gi s cho tr c N s a1, a2, ..., aN th a mãn đi u ki n là các c nhạ ặ ẳ ả ử ướ ố ỏ ề ệ ạ
c a đa giác, b n hãy l p ch ng trình bi u di n và v đa giác trên.ủ ạ ậ ươ ể ễ ẽ
Input
Input c a bài toán là t p P6.INP bao g m 2 dòng, dòng đ u tiên ghi s N, dòng th hai ghi N s th c cáchủ ệ ồ ầ ố ứ ố ự
nhau b i d u cách.ở ấ
Output
Đ u ra c a bài toán th hi n trên màn hình.ầ ủ ể ệ
Chú ý: Ph n lý thuy t c a bài toán c n đ c ch ng minh m t cách ch t ch .ầ ế ủ ầ ượ ứ ộ ặ ẽ
Bài 23/2000 - Quay Rubic
(Dành cho h c sinh THPTọ)
Rubic là m t kh i l p ph ng g m 3ộ ố ậ ươ ồ ×3×3 = 27 kh i l p ph ng con. M i m t rubic g m 3ố ậ ươ ỗ ặ ồ ×3 = 9 m tặ
c a m t l p 9 kh i l p ph ng con. tr ng thái ban đ u, m i m t rubic đ c tô m t màu. Các m t khácủ ộ ớ ố ậ ươ ở ạ ầ ỗ ặ ượ ộ ặ
nhau đ c tô các màu khác nhau. Gi s ta đang nhìn vào m t m t tr c c a rubic. Có th kí hi u màuượ ả ử ộ ặ ướ ủ ể ệ
các m t nh sau: F: màu m t tr c là m t ta đang nhìn; U: màu m t trên; R: màu m t ph i; B: màu m tặ ư ặ ướ ặ ặ ặ ả ặ
sau; L: màu m t bên trái; D: màu m t d i.ặ ặ ướ
M t l p g m 3ộ ớ ồ ×3 kh i l p ph ng con có th quay 90 đ nhi u l n, tr c quay đi qua tâm và vuông gócố ậ ươ ể ộ ề ầ ụ
v i m t đang xét. K t qu sau khi quay là kh i l p ph ng 3ớ ặ ế ả ố ậ ươ ×3×3 v i các màu m t đã b đ i khác.ớ ặ ị ổ
Tin h c & Nhà tr ngọ ườ 100 Đ Toán - Tin h cề ọ
Lê Th Hi uị ế 4
M t xâu vòng quay liên ti p rubic có th mô t b ng xâu các ch cái c a U, R, F, D, B, L, trong đó m iộ ế ể ả ằ ữ ủ ỗ
ch cái là kí hi u m t vòng quay c s : quay m t t ng ng 90 đ theo chi u kim đ ng h . Hãy vi tữ ệ ộ ơ ở ặ ươ ứ ộ ề ồ ồ ế
ch ng trình gi i 3 bài toán d i đây:ươ ả ướ
1. Cho 2 xâu INPUT khác nhau, ki m tra xem li u n u áp d ng v i tr ng thái đ u có cho cùng m t k tể ệ ế ụ ớ ạ ầ ộ ế
qu hay không?ả
2. Cho m t xâu vào, hãy xác đ nh s l n c n áp d ng xâu vào đó cho tr ng thái đ u rubic đ l i nh nộ ị ố ầ ầ ụ ạ ầ ể ạ ậ
đ c tr ng thái đ u đó.ượ ạ ầ
Bài 25/2000 - Xây d ng sự ố
(Dành cho h c sinh THCSọ)
Cho các s sau: 1, 2, 3, 5, 7ố
Ch dùng phép toán c ng hãy dùng dãy trên đ t o ra s : 43, 52.ỉ ộ ể ạ ố
Ví d đ t o s 130 b n có th làm nh sau: 123 + 7 = 130. ụ ể ạ ố ạ ể ư
Bài 26/2000 - Tô màu
(Dành cho h c sinh THCSọ)
Cho l i ô vuông 4x4, c n ph i tô màu các ô c a l i. Đ c phép dùng 3 màu: Xanh, đ , vàng. Đi uướ ầ ả ủ ướ ượ ỏ ề
ki n tô màu là ba ô b t kỳ li n nhau theo chi u d c và ngang ph i khác màu nhau. H i có bao nhiêuệ ấ ề ề ọ ả ỏ
cách nh v y, hãy li t kê t t c các cách.ư ậ ệ ấ ả
Bài 27/2000 - Bàn c ờ
(Dành cho h c sinh THPTọ)
Cho m t bàn c vuông 8x8, trên đó cho tr c m t s quân c . Ví d hình v sau là m t bàn c nh v y:ộ ờ ướ ộ ố ờ ụ ẽ ộ ờ ư ậ
× × ×
× × × ×
× × × ×
× ×
×
× × ×
× × ×
× × ×
D li u nh p đ c ghi trên t p BANCO.TXT bao g m 8 dòng, m i dòng là m t sâu nh phân có đ dàiữ ệ ậ ượ ệ ồ ỗ ộ ị ộ
b ng 8. V trí các quân c ng v i s 1, các ô tr ng ng v i s 0. Ví d t p BANCO.TXT ng v i bànằ ị ờ ứ ớ ố ố ứ ớ ố ụ ệ ứ ớ
c trên:ờ
01010100
10011001
10100011
00010100
00100000
01010001
10011000
01000110
Tin h c & Nhà tr ngọ ườ 100 Đ Toán - Tin h cề ọ
Lê Th Hi uị ế 5
Hãy vi t ch ng trình tính s quân c liên t c l n nh t n m trên m t đ ng th ng trên bàn c . Đ ngế ươ ố ờ ụ ớ ấ ằ ộ ườ ẳ ờ ườ
th ng đây có th là đ ng th ng đ ng. đ ng n m ngang ho c đ ng chéo. K t qu th hi n trênẳ ở ể ườ ẳ ứ ườ ằ ặ ườ ế ả ể ệ
màn hình.
V i ví d nêu trên, ch ng trình ph i in trên màn hình k t qu là 4.ớ ụ ươ ả ế ả
Bài 29/2000 - Ch n b n ọ ạ
(Dành cho h c sinh THCSọ)
Trong m t tr i hè ng i ta tình c ch n ra m t nhóm 6 h c sinh. Ch ng minh r ng s tìm đ c 3 trongộ ạ ườ ờ ọ ộ ọ ứ ằ ẽ ượ
s 6 b n đó sao cho 3 b n này ho c đã quen nhau (đôi m t) t tr c ho c ch a h quen nhau. Em hãy chố ạ ạ ặ ộ ừ ướ ặ ư ề ỉ
ra cách tìm 3 b n đó.ạ
Bài 30/2000 - Ph n t yên ng a ầ ử ự
(Dành cho h c sinh THCSọ)
Cho b ng A kích th c MxN. Ph n t Aij đ c g i là ph n t yên ng a n u nó là ph n t nh nh tả ướ ầ ử ượ ọ ầ ử ự ế ầ ử ỏ ấ
trong hàng c a nó đ ng th i là ph n t l n nh t trong c t c a nó. Ví d trong b ng s sau đây:ủ ồ ờ ầ ử ớ ấ ộ ủ ụ ả ố
15 3 9
55 4 6
76 1 2
thì ph n t A22 chính là ph n t yên ng a.ầ ử ầ ử ự
B n hãy l p ch ng trình nh p t bàn phím m t b ng s kích th c MxN và ki m tra xem nó có ph nạ ậ ươ ậ ừ ộ ả ố ướ ể ầ
t yên ng a hay không?ử ự
Bài 31/2000 - Bi u di n phân s ể ễ ố
(Dành cho h c sinh PTTHọ)
M t phân s luôn luôn có th đ c vi t d i s th p phân h u h n ho c vô h n tu n hoàn. Ví d :ộ ố ể ượ ế ướ ố ậ ữ ạ ặ ạ ầ ụ
23/5 = 4.6
3/8 = 0.375
1/3 = 0.(3)
45/56 = 0.803(571428)
....
Trong các ví d trên thì các ch s đ t trong d u ngo c ch ph n tu n hoàn c a s th p phân.ụ ữ ố ặ ấ ặ ỉ ầ ầ ủ ố ậ
Nhi m v c a b n là vi t m t ch ng trình nh p t s (N) và nh p m u s (D), sau đó đ a ra k t quệ ụ ủ ạ ế ộ ươ ậ ử ố ậ ẫ ố ư ế ả
là d ng th p phân c a phân s N/D. ạ ậ ủ ố
Ví d ch y ch ng trình:ụ ạ ươ
Nhap N, D:1 7
1/7 = 0.(142857)_
Bài 33/2000 - Mã hoá văn b n ả
(Dành cho h c sinh THCSọ)
Bài toán sau mô t m t thu t toán mã hoá đ n gi n (đ ti n ta l y ví d ti ng Anh, các b n có th mả ộ ậ ơ ả ể ệ ấ ụ ế ạ ể ở
r ng cho ti ng Vi t):ộ ế ệ
T p h p các ch cái ti ng Anh bao g m 26 ch cái đ c đánh sô th t t 0 đ n 25 nh sau:ậ ợ ữ ế ồ ữ ượ ứ ự ừ ế ư
01234567891 1 12131 151 1 1 19202122232425
Tin h c & Nhà tr ngọ ườ 100 Đ Toán - Tin h cề ọ