//
you're reading...
Bài tập huấn luyện, Dùng cho cấp THCS

Đề tham khảo 401 – 500

401. Bµi to¸n n vßng trßn

Trªn mÆt ph¼ng cho tr­ưíc n vßng trßn.

1) TÝnh sè giao ®iÓm cña chóng.

2) TÝnh sè miÒn cña mÆt ph¼ng ®­ưîc chia bëi chóng.

402. LÞch trùc nhËt

Mét líp häc cã N häc sinh cho tr­ưíc. Mçi ngµy cÇn mét ®éi trùc nhËt chØ gåm p1, p2, …, pk ng­ưêi.

Hái sau Ýt nhÊt bao nhiªu ngµy th× mçi ng­ưêi sÏ ®­ưîc trùc mét sè ngµy nh­ư nhau. LËp lÞch trùc cho sè ngµy ®ã.

403. TÝnh ngµy trong tuÇn

BiÕt r»ng ngµy 1-11-1991 lµ thø s¸u. LËp ch­¬ng tr×nh tÝnh:

– Ngµy 1-1-1900 lµ thø mÊy.

– TÝnh xem trong thÕ kû 20 (tõ 1-1-1900 ®Õn 31-12-1999) cã bao nhiªu ngµy thø s¸u r¬i vµo ngµy mång 1 cña th¸ng. BiÕt r»ng n¨m nhuËn lµ n¨m cã 29 ngµy trong th¸ng 2 vµ lµ n¨m cã sè n¨m hoÆc chia hÕt cho 400 hoÆc chia hÕt cho 4 nh­ng kh«ng chia hÕt cho 100.

404. T×m ng­ưêi ra ®Ò

Mét líp häc cã m x n chç gåm m hµng ghÕ, mçi ghÕ cã n häc sinh. ®Ó chuÈn bÞ cho kú thi häc sinh giái tin häc, mét sè c¸n sù tin häc mçi ngư­êi s¸ng t¸c mét ®Ò sau ®ã sao thµnh mét sè b¶n ®­ưa cho ngưêi bªn c¹nh (tr¸i, ph¶i, bµn tr­ưíc, bµn sau mçi ng­ưêi ®óng mét b¶n; sè ng­ưêi nµy cã thÓ lµ 2, 3, 4 tïy theo vÞ trÝ cña ng­ưêi ®­ưa). Sau ®ã tÊt c¶ mäi ng­ưêi th«ng b¸o sè ®Ò m×nh ®· nhËn ®­ưîc. LËp chư¬ng tr×nh x¸c ®Þnh vÞ trÝ cña nh÷ng ng­ưêi trong ban c¸n sù. L­ưu ý r»ng cã thÓ cã nhiÒu lêi gi¶i. Trong b¶ng lµ mét vÝ dô víi m = n = 6 (xem h×nh 404).

405. * Bµi to¸n “Trß ch¬i ®o¸n sè”

Hai ®èi thñ A,B ch¬i trß ®o¸n sè nh­ư sau: ®èi thñ A tù nghÜ ra mét sè tù nhiªn cã 8 ch÷ sè vµ B ph¶i ®o¸n ra ®­ưîc ch÷ nµy. B cã quyÒn sau: ®­ưa ra mét sè cã 8 ch÷ sè. A ph¶i tr¶ lêi b»ng 2 sè: cã bao nhiªu ch÷ sè gièng nh­ư trong sè ®· ®o¸n vµ cã bao nhiªu ch÷ sè trïng khÝt víi sè ®· ®o¸n. Trß ch¬i tiÕp tôc cho ®Õn khi B ®o¸n ra ®­îc sè (®iÒu kiÖn lµ c¸c sè cña A ®­a ra ph¶i lµ c¸c sè cã c¸c ch÷ sè kh¸c nhau tõng ®«i mét).

1) LËp ch­ư¬ng tr×nh cho phÝa A: m¸y tù nghÜ ra mét sè, ng­ưêi sö dông ph¶i ®o¸n sè vµ t×m sè.

2) T×m vµ diÔn gi¶i thuËt to¸n cho B sao cho sau Ýt b­ưíc nhÊt t×m ra ®­ưîc sè ®· cho.

3) LËp tr×nh cho phÝa B. Ng­ưêi sö dông tù nghÜ ra sè vµ tr¶ lêi m¸y nh­ư A tr¶ lêi B. Sau mét sè b­ưíc theo thuËt to¸n ë phÇn (2), m¸y sÏ t×m ra sè mµ b¹n nghÜ ra.

406. 4 c¹nh cña tø gi¸c

Cho 4 sè thùc d­ư¬ng a,b,c,d. KiÓm tra xem 4 sè trªn cã lµ 4 c¹nh cña mét tø gi¸c ®­ưîc kh«ng.

407. TÝnh diÖn tÝch phñ ch÷ nhËt

Trªn mÆt ph¼ng cho n h×nh ch÷ nhËt cã c¸c c¹nh song song víi c¸c trôc täa ®é vµ cho bëi c¸c cÆp täa ®é tr¸i trªn vµ ph¶i d­ưíi: ((x1,y1), (z1,t1)), …, ((xn,yn), (zn,tn)).

TÝnh diÖn tÝch phÇn mÆt ph¼ng phñ bëi c¸c h×nh ch÷ nhËt trªn.

408. Hai h×nh ch÷ nhËt lång nhau

Cho hai cÆp sè thùc d­ư¬ng (a1,b1), (a2,b2). H·y kiÓm tra xem h×nh ch÷ nhËt cã c¹nh (a1, b1) cã thÓ n»m trong h×nh ch÷ nhËt c¹nh (a2,b2) ®­îc kh«ng.

409. DiÖn tÝch phñ h×nh trßn

Trªn mÆt ph¼ng cho n vßng trßn trªn mÆt ph¼ng víi t©m vµ b¸n kÝnh lµ:((x1,y1),R1)), ….,((xn,yn),Rn)).TÝnh diÖn tÝch phÇn mÆt ph¼ng phñ bëi c¸c vßng trßn trªn.

410. Bµi to¸n n ®iÓm trªn mÆt ph¼ng

Trªn mÆt ph¼ng cho n ®iÓm p1,p2,…,pn víi to¹ ®é: (x1,y1), (x2,y2), …, (xn,yn).

1) KiÓm tra xem n ®iÓm p1,p2,…,pn cã kh¸c nhau tõng ®«i mét hay kh«ng.

2) Gi¶ sö kh¼ng ®Þnh cña c©u (1) lµ ®óng. KiÓm tra xem ®­ưêng gÊp khóc p1.p2…pn.p1 cã kh«ng tù c¾t hay kh«ng.

3) Gi¶ sö kh¼ng ®Þnh c©u (2) lµ ®óng. KiÓm tra xem ®a gi¸c p1p2…pn cã lµ låi hay kh«ng.

411. Bao låi

Trªn mÆt ph¼ng cho n ®iÓm p1,p2,…,pn. H·y chØ ra c¸ch x©y dùng bao låi nhá nhÊt chøa n ®iÓm trªn.

412. Ma trËn nèi vµ ma trËn liªn kÕt

Lư­íi theo ®Þnh nghÜa lµ mét tËp hîp ®iÓm, gi÷a c¸c ®iÓm cã thÓ cã (hoÆc kh«ng cã) c¸c ®­ưêng nèi ®Þnh h­ưíng (1 chiÒu). Mçi l­ưíi sÏ ®­ưîc x¸c ®Þnh bëi hai ma trËn bËc n: ma trËn Nối vµ ma trËn Liªn kÕt.

Ma trËn Nèi A = (aij), trong ®ã: aij = 1 khi vµ chØ khi tõ ®Ønh i cã ®­ưêng nèi h­íng ®Ønh j.

Ma trËn Liªn kÕt B = (bij) trong ®ã: bij = 1 khi vµ chØ khi tõ ®Ønh i cã thÓ ®i tíi ®­ưîc ®Ønh j theo c¸c ®­ưêng ®· ®Þnh h­ưíng.

Cho tr­ưíc ma trËn Nèi A cña mét l­ưíi. H·y x¸c ®Þnh ma trËn Liªn kÕt B cña nã.

413. §å thÞ ®¬n liªn

Đå thÞ gåm n ®Ønh vµ c¸c ®­ưêng cong nèi gi÷a c¸c ®Ønh trªn. ®å thÞ ®­ưîc gäi lµ “®¬n liªn” nÕu cã thÓ
vÏ l¹i ®å thÞ b»ng bót ch× theo mét nÐt, nghÜa lµ kh«ng nhÊc bót vµ kh«ng cã c¹nh nµo ®­îc vÏ b»ng 2 nÐt.

Kh¼ng ®Þnh sau coi nh­ư ®· biÕt: ®å thÞ lµ “®¬n liªn” khi vµ chØ khi sè c¸c ®Ønh mµ tõ ®ã xuÊt ph¸t sè lÎ c¹nh, kh«ng lín h¬n 2. Mçi ®å thÞ n ®Ønh øng víi ma trËn Nèi cña chóng.

A = (aij) ë ®©y aij = 1 khi ®Ønh i vµ j cã c¹nh nèi.Cho tr­íc ma trËn Nèi cña mét ®å thÞ.

1) X¸c ®Þnh xem ®å thÞ cã lµ “®¬n liªn” hay kh«ng.

2) NÕu ®å thÞ lµ “®¬n liªn” th× h·y chØ ra mét c¸ch vÏ mét nÐt cho ®å thÞ trªn.

414. C¸c sè tù nhiªn Amstrong

Sè tù nhiªn n gäi lµ Amstrong nÕu n biÓu diÔn bëi k ch÷ sè vµ n b»ng tæng c¸c k mò c¸c ch÷ sè cña nã.VÝ dô: (153 = 13 + 53 + 33).

T×m tÊt c¶ c¸c sè Amstrong cã: 2 ch÷ sè, 3 ch÷ sè, 4 ch÷ sè.

415. C¸c sè tù nhiªn ®èi xøng

Sè tù nhiªn n gäi lµ ®èi xøng nÕu trong c¸ch viÕt thËp ph©n cña nã c¸c ch÷ sè lµ ®èi xøng. VÝ dô (575, 4224). Ký hiÖu An lµ sè thu ®­ưîc tõ n b»ng c¸ch viÕt c¸c ch÷ sè theo thø tù ng­ưîc l¹i
(VËy n ®èi xøng khi n = An).

1) LËp ch­ư¬ng tr×nh liÖt kª 100 sè ®èi xøng ®Çu tiªn.

2) Víi mçi sè tù nhiªn n xÐt thuËt to¸n sau:

B­ưíc 1: NÕu n ®èi xøng th× dõng l¹i.

B­ưíc 2: NÕu n kh«ng lµ ®èi xøng n = n + An.

B­ưíc 3: Quay l¹i b­íc 1.

H·y chØ ra r»ng víi mäi sè tù nhiªn n qu¸ tr×nh trªn sÏ dõng l¹i.

416. VÒ mét khai triÓn “tùa tam ph©n”

Chøng minh r»ng mäi sè tù nhiªn P cã khai triÓn duy nhÊt d­ưíi d¹ng:

417. Khai triÓn giai thõa

Chøng minh r»ng mäi sè tù nhiªn n cã khai triÓn duy nhÊt d­ưíi d¹ng:

n = dk.(k+1)! + dk-1.k! + … + d1.2! + d0, víi 0 <= di <= i+1, i = 0,1,2,….,k, dk <>0.

418. Ba d·y sè

Cho tr­ưíc 3n sè tù nhiªn: a1, a2, .., an; b1, b2, .., bn; c1, c2, .., cn. H·y t×m tÊt c¶ c¸c cÆp chØ sè
(i,j) sao cho ai <= aj, bi <= bj, ci<= cj . ThuËt to¸n kh«ng cho phÐp dïng qu¸ n2 phÐp to¸n.

419.

Cho n sè tù nhiªn kh¸c nhau tõng ®«i mét a1, a2, .., an. XÐt tÊt c¶ c¸c tæng d¹ng:

ai1+ ai2+ … + aik (*), víi ai1, ai2, .., aik kh¸c nhau tõng ®«i mét vµ k<= n.

H·y lËp ch­ư¬ng tr×nh tÝnh tÊt c¶ c¸c sè kh¸c nhau tõ c¸c tæng trªn.

420. VÒ c¸c sè tù nhiªn “tèt”

Cho 2 sè p,q – nguyªn tè cïng nhau. Sè tù nhiªn n gäi lµ “Tèt” nÕu n biÓu diÔn ®­ưîc d­ưíi d¹ng n =
xp + yq víi x,y nguyªn, kh«ng ©m. Tr­ưêng hîp ng­îc l¹i n gäi lµ “XÊu”.

§Æt c = pq-p-q. Chøng minh mÖnh ®Ò: nÕu z lµ “Tèt” th× c-z sÏ lµ “XÊu”.

421. C¸c tæng con kh¸c nhau

Cho tr­ưíc n sè nguyªn a1, a2, .., an.LËp ch­ư¬ng tr×nh tÝnh xem trong sè c¸c tæng con:

ai1+ai2+…+aik, k<=n; i1, i2, …, ik kh¸c nhau tõng ®«i mét. Cã bao nhiªu sè kh¸c nhau vµ in ra tÊt c¶ c¸c tæng nh­ư vËy.

422. D·y nhÞ ph©n “Gän”

D·y nhÞ ph©n ®­ưîc gäi lµ “Gän” nÕu kh«ng cã hai sè 0 nµo ®øng c¹nh nhau.LËp ch­ư¬ng tr×nh in ra tÊt c¶ c¸c d·y nhÞ ph©n “Gän” ®é dµi n.

423. D·y nhÞ ph©n gän chøa ®óng m sè 1

LËp ch­ư¬ng tr×nh in ra tÊt c¶ c¸c d·y nhÞ ph©n “Gän”, ®é dµi n vµ chøa ®óng m sè 1.

424. D·y nhÞ ph©n gän bËc k

D·y nhÞ ph©n ®­ưîc gäi lµ “Gän” bËc k bÊt kú nÕu kh«ng cã k sè 0 nµo ®øng c¹nh nhau. LËp ch­ư¬ng
tr×nh in ra tÊt c¶ c¸c d·y nhÞ ph©n “Gän” bËc k ®é dµi n. LËp ch­ư¬ng tr×nh in ra tÊt c¶ c¸c d·y nhÞ ph©n “Gän” bËc k, ®é dµi n vµ chøa ®óng m sè 1.

425. BiÓu diÔn thµnh tæng cña k sè nguyªn d­ư¬ng

Chøng minh r»ng sè c¸ch biÓu diÔn cña sè n thµnh tæng cña m sè nguyªn d­ư¬ng b»ng sè c¸ch biÓu diÔn cña sè n-m thµnh tæng c¸c sè h¹ng <= m.

(VÝ dô: n=8, m=3,

8 = 1+1+6 = 1+2+5 = 1+3+4 =
2+2+4 = 2+3+3

8-3 =1+1+1+1+1 = 1+1+1+2 =
1+1+3 = 1+2+2 = 2+3).

426. BiÓu diÔn thµnh tæng d­ư¬ng kh¸c nhau cña k sè nguyªn

Chøng minh r»ng sè c¸ch biÓu diÔn cña sè n thµnh tæng cña m sè nguyªn d­ư¬ng kh¸c nhau tõng ®«i mét b»ng sè c¸ch biÓu diÔn cña sè n – m(m+1)/2 thµnh tæng cña c¸c sè <=m.

427. BiÓu diÔn thµnh tæng cña c¸c sè nguyªn kh¸c nhau

Chøng minh r»ng sè c¸ch biÓu diÔn cña sè n thµnh tæng cña c¸c sè h¹ng kh¸c nhau tõng ®«i mét b»ng sè c¸ch biÓu diÔn cña n thµnh tæng cña c¸c sè nguyªn dư­¬ng lÎ.

428. BiÓu diÔn thµnh tæng c¸c sè nguyªn d­ư¬ng

Chøng minh r»ng sè c¸ch biÓu diÔn cña sè n thµnh tæng c¸c sè nguyªn d­ư¬ng mµ mçi sè h¹ng kh«ng lÆp l¹i qu¸ k-1 lÇn sÏ b»ng sè c¸ch biÓu diÔn cña sè n thµnh tæng c¸c sè nguyªn d­ư¬ng mµ kh«ng mét sè h¹ng nµo trong chóng chia hÕt cho k.

429. §Õm sè chøa sè 1

H·y tÝnh xem trong d·y sè 1,2,3,…,1000000 cã bao nhiªu sè mµ trong c¸ch viÕt cña chóng chøa ch÷ sè 1.

430. §Õm sè – tæng qu¸t

D·y sè 1,2,3,…,1111111 xÕp thµnh mét hµng ngang. TÝnh xem trong hµng ngang ®ã cã bao nhiªu ch÷ sè 0, 1, 2, …, 9.

431. D·y cã ­ưíc nguyªn tè 2, 3,5

D·y c¸c sè tù nhiªn chØ cã ­ưíc nguyªn tè lµ 2, 3, 5:

2 3 4 5 6 8 10 12 15 16 18 20 24 25 27 30 32 36 40 …

LËp ch­ư¬ng tr×nh in ra n sè h¹ng ®Çu tiªn cña d·y nµy.

432. “D·y 153”

XÐt d·y sè U1, U2,… ®­ưîc x©y dùng nh­ư sau:

U1 lµ 1 sè bÊt kú chia hÕt cho 3

Un = tæng lËp ph­ư¬ng c¸c ch÷ sè cña Un-1

Chøng minh r»ng d·y trªn dõng l¹i t¹i sè 153.

433. “D·y” 6174

D·y sè U1, U2,… ®­ưîc x©y dùng nh­ư sau:

U1 lµ 1 sè cã 4 ch÷ sè bÊt kú.

 S¾p xÕp l¹i c¸c sè a, b, c, d theo thø tù t¨ng dÇn a1b1c1d1.

Khi ®ã: Chøng minh r»ng d·y trªn dõng l¹i t¹i 6174.

434. ThuËt to¸n t×m d·y con cã ®é dµi cùc ®¹i

Cho d·y sè thùc a1, a2, …., an. “D·y con” lµ d·y ai1, ai2, …., aik víi ®iÒu kiÖn: i1 < i2 < …. < ik vµ
ai1 <= ai2 <= …. <=aik.  H·y lËp ch­ư¬ng tr×nh t×m “d·y con” cã ®é dµi cùc ®¹i.

Yªu cÇu ®é phøc t¹p thuËt to¸n lµ n.ln(n).

435. T×m tæng con cã gi¸ trÞ cùc ®¹i

H·y t×m tæng con cã gi¸ trÞ cùc ®¹i cña d·y trªn. §ßi hái ®é phøc t¹p thuËt to¸n lµ n.

436. XÕp ®éi ngò

Mét líp häc nä cã 3n ng­ưêi. CÇn tæ chøc c¸c cuéc duyÖt ®éi ngò, xÕp thµnh n hµng, mçi hµng 3 ngưêi. Hái cã bao nhiªu c¸ch xÕp nh­ư vËy vµ lËp ch­ư¬ng tr×nh in ra tÊt c¶ c¸c c¸ch xÕp ®ã. Hai c¸ch xÕp ®­ưîc coi lµ trïng nhau nÕu trong hai c¸ch xÕp ®ã cã hai b¹n lu«n ë cïng hµng víi nhau.

437. * Bµi to¸n c¾t chia c¸c h×nh ch÷ nhËt

Trªn mÆt ph¼ng cho tr­ưíc n h×nh ch÷ nhËt víi tæng diÖn tÝch b»ng mét sè chÝnh ph­ư¬ng A2 nµo ®ã. Mçi h×nh ch÷ nhËt cã thÓ c¾t thµnh nhiÒu h×nh ch÷ nhËt con b»ng c¸ch c¾t mét ®­ưêng song song víi mét c¹nh. C¸c sè ®o ®Òu lµ nguyªn.

Hái ph¶i cÇn Ýt nhÊt bao nhiªu nh¸t c¾t ®Ó xÕp c¸c h×nh ch÷ nhËt trªn thµnh mét h×nh vu«ng c¹nh A.

438. Qui luËt chuyÓn ®éng con xóc x¾c

ViÕt ch­ư¬ng tr×nh m« t¶ qui luËt chuyÓn ®éng cña con xóc x¾c trªn mÆt ph¼ng. T¹i mçi vÞ trÝ ph¶i chØ ra c¶ s¸u mÆt cña chóng.

439. Chia nhãm cã tæng b»ng nhau

Cho tr­ưíc n sè tù nhiªn a1, a2, .., an.T×m ra sè cùc ®¹i k sao cho tËp trªn cã thÓ chia thµnh k nhãm cã tæng nh­ư nhau.

440.

XÐt n2 cÆp sè (i,j) víi 1<=i, j<= n; n2 cÆp nµy cã thÓ s¾p thø tù theo hai c¸ch sau:

– Theo thø tù hµng tr­ưíc, cét sau.

– Theo thø tù cét tr­ưíc, hµng sau.

Gäi S(n) lµ sè c¸c cÆp sè mµ thø tù cña chóng nh­ư nhau trong c¶ hai c¸ch xÕp trªn. TÝnh S(n).

441. * Bµi to¸n hai ®èng sái – tæng qu¸t

(Bµi to¸n hai ®èng sái tæng qu¸t)

Cã hai ®èng sái. Mçi ng­ưêi cã quyÒn bèc mét trong 2 c¸ch sau:

– LÊy tõ mét ®èng mét sè sái bÊt kú.

– LÊy tõ mét ®èng sè sái k>0 vµ ®èng kia sè sái l >0 sao cho |k-l|<a kh«ng ®æi cho tr­ưíc.

Ng­ưêi th¾ng cuéc lµ ng­ưêi ®­ưîc quyÒn bèc lÇn cuèi cïng. T×m thuËt to¸n tèi ­ưu cho c¸c ng­ưêi ch¬i.

442. X©u nhÞ ph©n t­ư¬ng ®­ư¬ng bËc k

XÐt tËp c¸c x©u nhÞ ph©n ®é dµi n, trªn ®ã xÐt c¸c phÐp biÕn ®æi sau: LÊy ra mét x©u con ®é dµi k (2 <= k <= n cho tr­íc) vµ ®æi ng­ưîc l¹i thø tù cña x©u con nµy.

1) NhËp vµo tõ bµn phÝm hai x©u S1, S2 ®é dµi n. KiÓm tra tÝnh ®óng ®¾n cña d÷ liÖu.

2) KiÓm tra xem tõ x©u S1 sau h÷u h¹n c¸c phÐp biÕn ®æi trªn cã thÓ thu ®­îc x©u S2 kh«ng. NÕu ®ưîc, liÖt kª lªn mµn h×nh lÇn l­ưît c¸c phÐp biÕn ®æi ®ã. Khi ®ã ta gäi hai x©u nµy lµ t­ư¬ng ®­ư¬ng.

3) Tèi ­ưu hãa c©u (2) theo nghÜa sè phÐp biÕn ®æi lµ Ýt nhÊt.

4) In ra tËp hîp lín nhÊt c¸c x©u nhÞ ph©n kh«ng t­ư¬ng ®­ư¬ng víi ®é dµi n.

443. §Õm sè tam gi¸c

Cho n ®­ưêng th¼ng trªn mÆt ph¼ng. TÝnh xem trong c¸c phÇn mÆt ph¼ng bÞ chia bëi c¸c ®­ưêng th¼ng trªn cã bao nhiªu tam gi¸c. VÏ trªn mµn h×nh ®å thÞ vµ t« mµu c¸c tam gi¸c ®ã.

444. Chia l­ưíi

Cho l­ưíi m x n « vu«ng, trong mçi « cho tr­ưíc mét sè tù nhiªn. H·y t×m c¸ch chia l­ưíi trªn lµm hai phÇn (chia theo c¹nh l­ưíi) sao cho trÞ tuyÖt ®èi hiÖu sè cña tæng c¸c sè trong mçi phÇn cã gi¸ trÞ nhá nhÊt (h×nh 444).

445. §­ưêng ®i tèi ­ưu trªn l­ưíi

Cho l­íi m x n « vu«ng, trong mçi « cho tr­ưíc mét sè tù nhiªn. Víi hai « A, B cho tr­ưíc t×m mét ®ưêng ®i tõ A ®Õn B (®i qua c¸c « vµ kh«ng tù c¾t) sao cho tæng c¸c trÞ sè trªn ®­ưêng ®i lµ nhá nhÊt.

446. ThiÕt lËp ®­ưêng ®i tèi ­ưu trªn l­ưíi

Cho l­ưíi « vu«ng kÝch th­ưíc (m x n), trong ®ã ®¸nh dÊu k ®iÓm A1, A2, …, Ak.

1) CÇn nèi c¸c ®­ưêng ®i gi÷a c¸c ®iÓm A1, A2, …, Ak sao cho c¸c ®­ưêng ®i theo c¹nh cña l­ưíi vµ tõ ®iÓm bÊt kú Ai cã thÓ ®i ®Õn ®­ưîc ®iÓm bÊt kú Aj.

a. H·y chØ ra mét c¸ch nèi c¸c ®­ưêng ®i sao cho tæng kho¶ng c¸ch ®­ưêng lµ nhá nhÊt. Gäi sè nµy lµ Smin.

b. Víi sè S >= Smin chØ ra tÊt c¶ c¸c c¸ch nèi ®­ưêng ®i theo qui t¾c trªn sao cho tæng kho¶ng c¸ch ®­ưêng <= S.

2) Cho tr­íc gi¸ trÞ nguyªn S. H·y chØ ra gi¸ trÞ lín nhÊt k sao cho cã thÓ ®¸nh dÊu k thµnh phè vµ kÎ ®­ưîc c¸c ®­ưêng nèi víi tæng chiÒu dµi lµ S.

447. * Ph©n ho¹ch phñ

Cho tr­ưíc h×nh vu«ng H kÝch th­ưíc (n x n). Ta gäi mét “Ph©n ho¹ch” lµ mét c¸ch chia H thµnh c¸c
h×nh ch÷ nhËt con cã täa ®é nguyªn vµ c¸c c¹nh song song víi W= (A1, A2, …, Ak).

TËp con Ws =(Ai1, Ai2, …, Ais) ®­ưîc gäi lµ:

a. Phñ: nÕu h×nh chiÕu cña c¸c phÇn tö cña Ws lªn mét c¹nh nµo ®ã cña h×nh vu«ng phñ kÝn c¹nh nµy.

b. Phñ ®¬n: nÕu h×nh chiÕu cña c¸c phÇn tö cña Ws lªn mét c¹nh nµo ®ã cña h×nh vu«ng t¹o thµnh mét phñ kh«ng giao nhau cña c¹nh nµy.

1) NhËp tõ bµn phÝm täa ®é cña k h×nh ch÷ nhËt vµ kiÓm tra xem chóng cã lËp thµnh mét ph©n ho¹ch cña h×nh vu«ng H hay kh«ng.

2) Cho tr­ưíc mét phÇn tö A cña ph©n ho¹ch W. H·y chØ ra mét phñ nhá nhÊt chøa A.

3) Cho tr­ưíc 2 phÇn tö A, B. H·y chØ ra mét phñ ®¬n chøa A,B.

4) H·y chØ ra mét phñ nhá nhÊt cña ph©n ho¹ch W.

5) ViÕt ch­ư¬ng tr×nh sinh ngÉu nhiªn ph©n ho¹ch W víi k phÇn tö cho tr­ưíc. KÕt qu¶ thÓ hiÖn trªn mµn h×nh.

448. BiÓu diÔn ®­ưêng gÊp khóc

L­ưíi theo ®Þnh nghÜa lµ mét b¶ng vu«ng m x n « kÝch th­ưíc 1 x 1. VËy tæng chiÒu dµi l­ưíi lµ:

m(n+1) + n(m+1) = m + n + 2m. Tr­ưêng hîp m=n th× sè trªn b»ng 2n^2 + 2n = 2n(n+1).

H·y t×m c¸ch biÓu diÔn l­ưíi thµnh hîp cña c¸c ®­ưêng gÊp khóc (kh«ng giao nhau). T×m sè nhá nhÊt c¸c ®­ưêng gÊp khóc.

449. T« mµu ®Ønh ®a gi¸c

Cho tr­ưíc n,k víi k<n. CÇn t« mµu k ®Ønh cña mét ®a gi¸c ®Òu n ®Ønh cho tr­íc. C¸ch t« mµu gäi lµ chÊp nhËn ®­ưîc nÕu:

Víi mäi m <= n, tån t¹i hai bé m ®Ønh liªn tiÕp, trong ®ã sè c¸c ®Ønh ®­ưîc ®¸nh dÊu sÏ chªnh nhau kh«ng qu¸ 1. X©y dùng c¸ch t« mµu chÊp nhËn ®­ưîc víi n, k cho tr­ưíc.

450. LÞch söa ch÷a « t«

Mét nhµ m¸y cÇn söa ch÷a n « t«, ký hiÖu lµ X1, X2, …,Xn. ®Ó söa ch÷a « t« ký hiÖu Xi, nhµ m¸y cÇn kho¶ng thêi gian lµ ti (i = 1,2,…,n).Nhµ m¸y trong mét thêi ®iÓm chØ söa ch÷a ®­îc 1 « t«, söa xong chiÕc nµy b¾t tay ngay vµo söa chiÕc kh¸c. Gi¶ sö thêi ®iÓm b¾t ®Çu cña ®ît söa ch÷a lµ 0, « t« Xi ®ưîc gäi lµ söa ®óng h¹n nÕu nã ®­ưîc b¾t ®Çu söa ch÷a kh«ng sím h¬n thêi ®iÓm Ti vµ kÕt thóc söa xong kh«ng muén h¬n thêi ®iÓm Di.

C¸c thêi ®iÓm Ti vµ Di (i=1,2,…,n) lµ c¸c sè nguyªn d­ư¬ng cho tr­ưíc. H·y t×m mét thø tù söa ch÷a c¸c « t« sao cho sè l­ưîng c¸c xe bÞ söa qu¸ h¹n (nghÜa lµ kh«ng ®óng h¹n) lµ Ýt nhÊt.

451. T¹o ma trËn sè

Cho tr­íc sè nguyªn d­¬ng N bÊt
kú. H·y viÕt thuËt to¸n vµ ch­¬ng tr×nh ®Ó t¹o lËp b¶ng N x N phÇn tö nguyªn
d­¬ng theo quy luËt ®­îc cho trong vÝ dô sau:

1 2 3 4 5 6

2 4 6 8 10 12

3 6 9 12 2 4

4 8 12 2 4 6

5 10 2 4 6 8

6 12 4 6 8 10

Thùc hiÖn ch­¬ng tr×nh ®ã trªn
m¸y víi N=12, ®­a ra mµn h×nh ma trËn kÕt qu¶ (cã d¹ng nh­ trong vÝ dô).

452. X©y dùng mét phñ c¸c h×nh
ch÷ nhËt

Cè ®Þnh mét hÖ to¹ ®é vu«ng gãc
trªn mÆt ph¼ng. ®Ó x¸c ®Þnh mét h×nh ch÷ nhËt cã c¸c c¹nh song song víi c¸c
trôc täa ®é, ta chØ cÇn x¸c ®Þnh täa ®é cña hai ®Ønh ®èi t©m. VÝ dô, víi h×nh
ch÷ nhËt ABCD (H×nh 452) th× A vµ C lµ ®èi t©m, B vµ D lµ ®èi t©m. Khi ®ã mét
h×nh ch÷ nhËt ®­îc cho bëi 4 sè a, b, c, d (víi a ¹ c vµ b ¹ d) trong ®ã (a,b)
vµ (c,d) lµ täa ®é cña hai ®Ønh ®èi t©m.

Cho n (40>=n>=30) h×nh
ch÷ nhËt víi c¸c täa ®é nguyªn, h×nh thø i ®­îc cho bëi c¸c täa ®é nguyªn ai,
bi , ci vµ di.

H·y chØ ra:

1) Trong n h×nh ch÷ nhËt, mét
bé nhiÒu nhÊt c¸c h×nh ch÷ nhËt rêi nhau (hai h×nh ch÷ nhËt trong bé kh«ng cã
®iÓm chung trõ nhiÒu nhÊt mét ®Ønh), chØ ra thø

tù vµ täa ®é cña mçi h×nh ch÷
nhËt trong bé.

2) Cho h×nh ch÷ nhËt D qua täa
®é (a,b,c,d). Mét bé c¸c h×nh ch÷ nhËt trong n h×nh ch÷ nhËt trªn ®­îc gäi lµ “phñ” D nÕu mäi ®iÓm cña D
thuéc vµo Ýt nhÊt mét h×nh ch÷ nhËt trong bé. H·y chØ ra mét bé phñ D mµ sè
l­îng h×nh ch÷ nhËt tham gia bé ®ã cµng Ýt cµng tèt.

Yªu cÇu bµi to¸n:

– D÷ liÖu vµo ®Æt trong File
Text DATA1: dßng ®Çu chøa sè n, mçi dßng tiÕp theo (dßng thø i) chøa 4 sè cho
h×nh ch÷ nhËt thø i-1. Dßng cuèi cïng chøa täa ®é h×nh ch÷ nhËt D.

– KÕt qu¶ ra File Text DATA2
chøa c¸c th«ng tin: in l¹i täa ®é n h×nh ch÷ nhËt nhËp vµo; sè h×nh ch÷ nhËt
trong bé h×nh ch÷ nhËt, täa ®é c¸c h×nh ch÷ nhËt tham gia bé nµy (cho c©u hái
(a)); sè h×nh ch÷ nhËt cña phñ vµ täa ®é c¸c h×nh ch÷ nhËt ®ã (cho c©u hái
(b)).

453. §Õm vµ ph©n lo¹i tõ

Cho File Text DATA1 gåm c¸c
dßng TEXT tiÕng ViÖt, trªn mçi dßng lµ c¸c tõ tiÕng ViÖt kh«ng dÊu (mçi tõ cã
kh«ng qu¸ 7 ch÷ c¸i), hai tõ c¸ch nhau Ýt nhÊt mét dÊu c¸ch. H·y t¹o File Text
DATA2 gåm tÊt c¶ c¸c tõ cña file Text DATA1:

– C¸c tõ trong DATA2 ph¶i xÕp
theo thø tù tõ ®iÓn (thø tù c¸c tõ nh­
PASCAL qui ®Þnh).

– Trªn mçi dßng: hai tõ c¸ch
nhau chØ mét dÊu c¸ch; tr­íc tõ ®Çu tiªn kh«ng cã dÊu c¸ch.

454. C¸c ®­êng ®i trªn l­íi

Cho b¶ng vu«ng 2n x 2n «, trªn
mçi dßng vµ mçi cét cã ®óng hai « ®­îc ®¸nh dÊu. Nèi c¸c vÞ trÝ ®¸nh dÊu theo
dßng vµ theo cét ta ®­îc c¸c ®­êng ®i. H·y lËp tr×nh:

1) – ®­a vµo tõ bµn phÝm b¶ng
vu«ng tháa m·n ®Çu bµi.

– T¹o ra ngÉu nhiªn mét b¶ng
vu«ng tháa m·n ®Çu bµi.

2) T×m tÊt c¶ c¸c ®­êng ®i.

3) T×m tÊt c¶ c¸c h×nh ch÷ nhËt
do c¸c ®­êng ®i t¹o thµnh vµ h×nh ch÷ nhËt cã diÖn tÝch lín nhÊt.

455. §­êng ®i ®Þa h×nh

Cho l­íi A kÝch th­íc m x n «
(m <= 10, n <= 30), gi¸ trÞ aij ë « (i,j) thÓ hiÖn ®Þa h×nh trung b×nh
trong «. Tõ mét « cã thÓ chuyÓn sang « cã c¹nh chung. ®o¹n nèi hai « kÒ nhau
gäi lµ ®i lªn nÕu gi¸ trÞ « thø hai lín h¬n gi¸ trÞ « ®Çu, gäi lµ ®i xuèng nÕu
gi¸ trÞ « sau bÐ h¬n gi¸ trÞ « ®Çu vµ gäi lµ ph¼ng nÕu hai gi¸ trÞ b»ng nhau.
®­êng nèi hai « bÊt kú ®­îc gäi lµ ph¼ng nÕu chØ chøa c¸c ®o¹n ph¼ng, ®­îc gäi
lµ ®i lªn nÕu kh«ng ph¶i lµ ph¼ng vµ chØ chøa c¸c ®o¹n ph¼ng hoÆc ®i lªn, ®­îc
gäi lµ ®i xuèng nÕu kh«ng ph¶i lµ ph¼ng vµ chØ chøa c¸c ®o¹n ph¼ng hoÆc ®i
xuèng. Trong tr­êng hîp cßn l¹i ®­êng gäi lµ mÊp m«.

LËp tr×nh thùc hiÖn c¸c c«ng
viÖc sau:

1) NhËp tõ bµn phÝm hoÆc tõ
File gi¸ trÞ m,n vµ c¸c gi¸ trÞ aij.

2) NhËp tõ bµn phÝm hai cÆp
(i1,j1) vµ (i2,j2). T×m ®­êng ph¼ng hoÆc ®i lªn hay ®i xuèng nèi (i1,j1) víi
(i2,j2). ®­a ra mµn h×nh täa ®é c¸c « cÇn chuyÓn lÇn l­ît tõ (i1,j1) tíi
(i2,j2). NÕu kh«ng cã ®­êng theo yªu cÇu th× th«ng b¸o lµ kh«ng cã.

3) Gi¶i quyÕt c©u (2) víi yªu
cÇu bæ sung: sè « ph¶i chuyÓn qua lµ Ýt nhÊt.

4) NÕu gi÷a hai « (i1,j1) vµ
(i2,j2) kh«ng cã ®­êng tháa m·n c©u (2) th× ®­îc phÐp “san lÊp” mét sè «: thay gi¸ trÞ mét « b»ng gi¸ trÞ míi
nhá h¬n. Chi phÝ san lÊp tÝnh b»ng hiÖu gi¸ trÞ cò vµ míi. T×m con ®­êng nèi
hai « cã tæng chi phÝ san lÊp lµ nhá nhÊt. ®­a th«ng tin ra mµn h×nh nh­ ë c©u
(2) vµ cho biÕt tæng chi phÝ san lÊp.

5) T×m ®­êng ®i xuèng dµi nhÊt
trong l­íi.

456. T×m qui luËt b¶ng

Cho sè N nguyªn d­¬ng (N>7).

1) H·y x©y dùng c«ng thøc ®Ó
tÝnh c¸c phÇn tö cña b¶ng cã kÝch th­íc N x N, dùa theo quy luËt ®­îc nhËn biÕt
tõ c¸ch biÓu diÔn cô thÓ víi N = 5, 6, 7 sau:

(N =5) (N = 6)

9 7 5 3 1 11 9 7 5 3 1

7 5 3 1 2 9 7 5 3 1 2

5 3 1 2 4 7 5 3 1 2 4

3 1 2 4 6 5 3 1 2 4 6

1 2 4 6 8 3 1 2 4 6 8

1 2 4 6 8 10

(N = 7)

13 11 9 7 5 3 1

11 9 7 5 3 1 2

9 7 5 3 1 2 4

7 5 3 1 2 4 6

5 3 1 2 4 6 8

3 1 2 4 6 8 10

1 2 4 6 8 10 12

2) ®­a ra mµn h×nh theo khu«n
d¹ng trªn víi N cô thÓ tïy chän.

3) Lµm tèt ch­¬ng tr×nh theo
nghÜa sè lÇn dïng phÐp so s¸nh lµ Ýt nhÊt.

457. C¸c thuËt to¸n vÒ n ®iÓm

Trªn mÆt ph¼ng Oxy cho n ®iÓm
trong ®ã kh«ng cã 3 ®iÓm nµo th¼ng hµng. Täa ®é cña chóng chøa trong file d¹ng
Text DA_GIAC.SL cã cÊu tróc sau:

dßng thø 1: n

dßng thø 2: x1 y1

. . . . . .

dßng thø n+1: xn yn

(gi÷a hai gi¸ trÞ cã Ýt nhÊt
mét dÊu c¸ch)

1) T×m h×nh ch÷ nhËt nhá nhÊt
(vÒ diÖn tÝch) cã c¸c c¹nh song song víi c¸c trôc Ox, Oy vµ chøa n ®iÓm nãi
trªn. In ra mµn h×nh diÖn tÝch vµ täa ®é c¸c ®Ønh cña h×nh ch÷ nhËt t×m ®­îc.

2) T×m mét ®iÓm (trong sè c¸c
®iÓm nãi trªn) sao cho tæng kho¶ng c¸ch tõ ®iÓm ®ã ®Õn c¸c ®iÓm cßn l¹i lµ nhá
nhÊt. In ra mµn h×nh täa ®é cña ®iÓm t×m ®­îc vµ tæng kho¶ng c¸ch t­¬ng øng.

3) T×m tam gi¸c cã diÖn tÝch
lín nhÊt trong sè c¸c tam gi¸c cã ®Ønh thuéc tËp hîp n ®iÓm nãi trªn sao cho
bªn trong nã kh«ng chøa bÊt kú ®iÓm nµo trong sè c¸c ®iÓm cßn l¹i. In ra mµn
h×nh diÖn tÝch tam gi¸c ®ã vµ täa ®é c¸c ®Ønh cña nã.

458. Chia bi

Cho N viªn bi cïng lo¹i, cÇn
chia cho M ng­êi sao cho mçi ng­êi nhËn kh«ng Ýt h¬n K vµ kh«ng nhiÒu h¬n L
viªn bi (trong ®ã K<= N/M <= L). H·y cho biÕt cã bao nhiªu c¸ch chia vµ
chØ ra tõng c¸ch chia ®ã.

459. N hßn bi

Cho täa ®é (trong hÖ vu«ng gãc)
cña N hßn ®¶o ®1, ®2,…, ®n lµ (X1,Y1), (X2,Y2),

…, (XN,YN).

Gi¶ thiÕt mäi thiÕt bÞ chøa
x¨ng cña can« chØ ®ñ chøa sè x¨ng ®Ó ®i qu·ng ®­êng dµi kh«ng qu¸ M km cho
tr­íc.

Trªn mçi ®¶o ®Òu cã x¨ng dù tr÷
®Ó can« cã thÓ n¹p ®Çy cho c¸c thiÕt bÞ chøa x¨ng. T×m mäi ®­êng ®i cã thÓ ®­îc
cña can« xuÊt ph¸t tõ ®¶o ®i(Xi,Yi) tíi ®¶o ®j(Xj,Yj). ChØ ra mét ®­êng ®i cña
can« mµ sè lÇn ph¶i ghÐ vµo ®¶o ®Ó lÊy x¨ng lµ Ýt nhÊt (®­îc gäi lµ ®­êng ®i
tèi ­u).

460. M« pháng phÐp nh©n

Ta biÕt r»ng c¸ch nh©n tay hai
sè tù nhiªn ®­îc thÓ hiÖn qua vÝ dô sau:

M« pháng c¸ch nh©n tay hai sè
tù nhiªn bÊt kú lªn mµn h×nh m¸y vi tÝnh.

461. B¶ng phÐp nh©n

Cho b¶ng ch÷ c¸i M = {a,b,c,d}.
Trªn b¶ng nµy phÐp nh©n ®­îc x¸c ®Þnh bëi b¶ng sau:

Trong ®ã giao cña dßng x vµ cét
y lµ tÝch xy, ch¼ng h¹n ac=b, bc=c, …

Cho x©u ký tù bÊt kú x =
x1x2…xn gåm c¸c ký tù cña b¶ng. Ta cã thÓ ®­a vµo x©u c¸c dÊu ngoÆc ®Ó biÕn
nã thµnh biÓu thøc tÝnh mét gi¸ trÞ nµo ®ã.

Ch¼ng h¹n víi x = aacb th×:

(aa)(cb) = b

a(a(cb)) = c

Cho tr­íc b¶ng nh©n vµ x©u ký
tù x = x1 x2…xn.

xi Î M, i = 1, …, n. H·y lËp
ch­¬ng tr×nh:

1) Cho biÕt cã thÓ ®­a vµo x©u
c¸c dÊu ngoÆc ®Ó biÕn nã thµnh biÓu thøc cã gi¸ trÞ lµ a ®­îc kh«ng?

2) NÕu cã, cho biÕt mét biÓu
thøc ®ã (ch¼ng h¹n, víi x = aacb th× cã biÓu thøc lµ (a(ac))b).

3) NÕu cã, cho biÕt tÊt c¶ c¸c
biÓu thøc cã gi¸ trÞ lµ a.

462. VÒ hai x©u ký tù

Thùc hiÖn c¸c yªu cÇu sau:

1) NhËp tõ bµn phÝm hai x©u ký
tù S vµ M cã chiÒu dµi tèi ®a lµ 255.

2) H·y kiÓm tra xem cã thÓ nhËn
®­îc M tõ S b»ng c¸ch xo¸ ®i mét sè ký tù cña S hay kh«ng?. NÕu ®­îc, h·y hiÓn
thÞ sè thø tù cña c¸c ký tù ®­îc gi÷ l¹i trong S.

3) Thùc hiÖn c©u (2) víi ®iÒu
kiÖn bæ sung: HiÖu cña sè thø tù ký tù cuèi cïng vµ sè thø tù cña ký tù ®Çu
tiªn ®­îc gi÷ l¹i trong S kh«ng v­ît qu¸ p (p nhËp tõ bµn phÝm).

4) Thùc hiÖn c©u (2) víi ®iÒu
kiÖn bæ sung: HiÖu cña sè thø tù cña hai ký tù ®­îc gi÷ l¹i liªn tiÕp bÊt kú
trong S kh«ng v­ît qu¸ q (q ®­îc nhËp tõ bµn phÝm).

463. LÞch thi ®Êu cê c«ng b»ng

Trong mét gi¶i cê cã hai ®éi
tham gia, mçi ®éi cã n ®Êu thñ (2 <=n<= 20, n nhËp tõ bµn phÝm). Mçi ®Êu
thñ cña ®éi nµy ph¶i thi ®Êu víi tÊt c¶ c¸c ®Êu thñ cña ®éi kia. Trong mçi vßng
®Êu, mçi ®Êu thñ ph¶i thi ®Êu ®óng mét trËn víi mét ®èi thñ vµ cã thÓ cÇm qu©n
tr¾ng hoÆc ®en (trong bµn cê chØ cã hai lo¹i qu©n tr¾ng hoÆc ®en).

Yªu cÇu:

1) LËp lÞch thi ®Êu tháa m·n
®iÒu kiÖn sau: trong toµn gi¶i, mçi ®Êu thñ cña mçi ®éi cã sè lÇn cÇm qu©n
tr¾ng vµ sè lÇn cÇm qu©n ®en lµ nh­ nhau. Cã thÓ lµm ®­îc ®iÒu ®ã hay kh«ng?
NÕu ®­îc h·y hiÓn thÞ lªn mµn h×nh lÞch lËp ®­îc.

Trong lÞch cÇn chØ râ: vßng
nµo, ®Êu thñ nµo, ë ®éi nµo, cÇm qu©n mµu g×, ®Êu víi ai.

2) Thùc hiÖn c©u (1) víi ®iÒu
kiÖn bæ sung: trong mçi vßng ®Êu sè l­îng c¸c ®Êu thñ ®­îc cÇm qu©n tr¾ng ë mçi
®éi lµ nh­ nhau trong mçi tr­êng hîp:

a) n = 4 x k (1 <= k <=
5)

b) 2 <= n <= 20

464. Xo¸ sè theo qui ®Þnh

Cho d·y sè nguyªn A =
(a1,a2,…, an), n<=80. Ng­êi ta quyÕt ®Þnh xo¸ khái d·y mét vµi sè theo quy
t¾c sau: nÕu xãa hai sè x vµ y th× b¾t buéc ph¶i xãa lu«n c¸c sè b»ng tæng x+y.

1) NhËp tõ bµn phÝm sè tù nhiªn
n vµ d·y sè nguyªn A = (a1,a2,…,an).

2) NhËp sè nguyªn m tõ bµn phÝm
vµ cho biÕt cã thÓ xo¸ khái d·y A ®óng m sè theo quy t¾c ®· nªu hay kh«ng? NÕu
®­îc th× h·y ®­a ra mµn h×nh sè thø tù cña c¸c phÇn tö bÞ xãa (n»m trong d·y A
ban ®Çu).

3) Trong tr­êng hîp xo¸ ®­îc,
h·y chØ ra c¸ch xo¸ sao cho tæng c¸c sè cßn l¹i lµ lín nhÊt. ®­a ra mµn h×nh
gi¸ trÞ tæng ®ã.

Gi¶i quyÕt c¸c yªu cÇu (1),
(2), (3) trong c¸c tr­êng hîp:

a) D·y A lµ d·y c¸c sè nguyªn
d­¬ng kh¸c nhau ®«i mét.

b) D·y A lµ d·y c¸c sè nguyªn
bÊt kú.

465. Ph­¬ng ¸n thuª thî tèi ­u

Cho N c«ng viÖc vµ M nhãm thî
(0<N, M<100). Víi mçi nhãm thî, biÕt c¸c th«ng tin sau:

– Sè ng­êi trong nhãm.

– Danh s¸ch c«ng viÖc mµ nhãm
thùc hiÖn ®­îc.

Mét ph­¬ng ¸n thuª thî lµ mét
c¸ch chØ ra thuª nh÷ng nhãm thî nµo trong sè M nhãm ®· cho ®Ó toµn bé N c«ng
viÖc ®­îc thùc hiÖn.

1) NhËp th«ng tin ®· cho tõ bµn
phÝm.

2) T×m ph­¬ng ¸n thuª thî tèt
nhÊt (theo nghÜa sè ng­êi ®­îc thuª lµ Ýt nhÊt).

HiÓn thÞ trªn mµn h×nh ph­¬ng
¸n thuª thî t×m ®­îc vµ tæng sè ng­êi cña ph­¬ng ¸n ®ã. NÕu lêi gi¶i lµ kh«ng
duy nhÊt h·y hiÓn thÞ tÊt c¶ c¸c ph­¬ng ¸n t×m ®­îc.

466. §å thÞ liªn th«ng ®¬n

Cho b¶n ®å giao th«ng A biÓu
diÔn b»ng N ®iÓm A1, A2,…, AN vµ c¸c cung nèi chóng. Nãi r»ng A lµ liªn th«ng
®¬n nÕu víi mçi cÆp ®iÓm (Ai,Aj) bÊt kú cã ®óng mét ®­êng ®i nèi chóng. Gi¶ sö
c¸c cung ®Òu cã ®é dµi nh­ nhau. Nãi r»ng cung (Ai,Aj) lµ cung ®éc ®¹o nÕu tÊt
c¸c ®­êng ®i dµi nhÊt trong A ®Òu chøa nã.

1) NhËp tõ bµn phÝm th«ng tin
x¸c ®Þnh b¶n ®å A.

3) KiÓm tra xem A cã lµ “Liªn th«ng ®¬n” hay kh«ng?.
NÕu kh«ng, h·y thªm hoÆc bít mét sè cung thÝch hîp ®Ó A trë thµnh “Liªn
th«ng ®¬n”. Th«ng b¸o vÒ c¸c söa ®æi.

3) Cho A lµ b¶n ®å “Liªn
th«ng ®¬n”, h·y t×m vµ chiÕu lªn mµn h×nh th«ng tin vÒ c¸c cung ®éc ®¹o cña
nã (nÕu cã).

467. Ma trËn nhÞ ph©n ®Æc biÖt

Cho ma trËn nhÞ ph©n B kÝch
th­íc m x n (1<=n<=10, 1<=m <=1024) tho¶ m·n 2 tÝnh chÊt sau:

1. B chøa Ýt nhÊt mét dßng toµn
c¸c sè 1.

2. NÕu x = (x1, x2, …, xn) vµ
y = (y1, y2, … , yn) lµ 2 dßng bÊt kú cña B th× tÝch x.y = (x1.y1, x2.y2,
…, xn.yn) còng lµ mét dßng cña B.

Víi mçi cÆp dßng u = (u1, u2,
…, un) vµ v = (v1, v1,…,vn) cña ma trËn A, víi ui vµ vi lµ nh÷ng sè tù
nhiªn ta x©y dùng phÐp biÕn ®æi E(u,v) thµnh mét dßng

t = E(u,v) = (t1, t2, …, tn)
nh­ sau:

Tõ A ta x©y dùng ma trËn E(A)
chøa toµn bé c¸c dßng E(u,v) víi mäi u, v thuéc A.

1) NhËp tõ bµn phÝm mét ma trËn
nhÞ ph©n kÝch th­íc m x n.

2) KiÓm tra xem ma trËn ®· nhËn
cã tho¶ m·n c¸c tÝnh chÊt (1) vµ (2) hay kh«ng? NÕu kh«ng h·y bæ sung cho nã
mét sè Ýt nhÊt c¸c dßng ®Ó hai tÝnh chÊt nãi trªn ®­îc tho¶ m·n.

3) Tõ ma trËn B thu ®­îc ë c©u
(2) h·y x©y dùng ma trËn A ®Ó E(A)=B.

468. Bµi to¸n hÖ thèng ®­êng

Cho N thµnh phè vµ mét sè ®­êng
®i hai chiÒu gi÷a c¸c thµnh phè trªn. Mçi ®­êng ®i ®­îc g¸n 2 sè nguyªn d­¬ng
t, k; t lµ sè tiÒn mµ mçi ph­¬ng tiÖn ®i l¹i trªn ®­êng ph¶i tr¶ (cho mçi lÇn
®i), k lµ ®é dµi cña ®o¹n ®­êng.

HÖ thèng ®­êng ®­îc gäi lµ
“Liªn th«ng” nÕu tõ bÊt kú thµnh phè nµo ®Òu cã thÓ ®i ®Õn bÊt kú
thµnh phè kh¸c vµ ng­îc l¹i.

HÖ thèng ®­êng ®­îc gäi lµ
“Tèi ­u” nÕu nã lµ Liªn th«ng vµ nÕu lo¹i bá mét ®­êng bÊt kú th× nã
trë nªn kh«ng Liªn th«ng.

HÖ thèng ®­êng ®­îc gäi lµ
“Hoµn h¶o” nÕu nã lµ Liªn th«ng vµ tháa m·n thªm ®iÒu kiÖn sau:

NÕu cã ®­êng ®i A ® B, B ® C vµ
A ® C víi c¸c th«ng sè t­¬ng øng tab, tbc, tac
vµ kab, kbc vµ kac th× ph¶i tháa m·n

tab + tbc
<= tac

kab + kbc
>= kac

XÐt c¸c bµi to¸n sau:

A) Cho tr­íc hÖ thèng thµnh phè
vµ ®­êng ®i. NÕu nã kh«ng lµ Liªn th«ng h·y bæ sung mét sè tèi thiÓu c¸c ®­êng
®i ®Ó trë thµnh Liªn th«ng. H·y ®iÒn c¸c th«ng sè t­¬ng øng sao cho hÖ thèng
trë nªn Hoµn h¶o.

B) NÕu hÖ thèng kh«ng lµ Tèi
­u, h·y lo¹i bít ®i mét sè ®­êng ®i sao cho nã trë nªn Tèi ­u. C¸ch lo¹i ®i
ph¶i ®¹t ®­îc mét trong ba môc ®Ých sau:

1. Sè ®­êng bÞ lo¹i lµ nhá
nhÊt.

2. Tæng sè kho¶ng c¸ch ®­êng bÞ
lo¹i lµ nhiÒu nhÊt.

3. Tæng sè tiÒn cña c¸c ®­êng
bÞ lo¹i lµ nhiÒu nhÊt.

C) NÕu hÖ thèng kh«ng lµ Hoµn
h¶o h·y ®iÒu chØnh sè tiÒn vµ ®é dµi cña c¸c ®­êng sao cho nã trë nªn Hoµn h¶o.
Sè c¸c sè ph¶i chØnh lµ nhá nhÊt.

D) Cho tr­íc hai thµnh phè X,
Y. H·y t×m mét ®­êng ®i tèi ­u tõ X ®Õn Y theo nghÜa: Mäi con ®­êng kh¸c ®Òu cã
hoÆc sè tiÒn ph¶i tr¶ nhiÒu h¬n hoÆc cã ®é dµi lín h¬n.

Yªu cÇu bµi lµm:

C©u 1:

NhËp d÷ liÖu bµi to¸n tõ tÖp
v¨n b¶n DATA.TRS víi c¸c ®iÒu kiÖn sau:

Dßng ®Çu tiªn ghi sè N c¸c
thµnh phè.

Tõ dßng thø hai lµ c¸c th«ng sè
vÒ c¸c ®­êng ®i, vÝ dô dßng sè sau:

1 3 25 320

cã ý nghÜa: ®­êng ®i tõ thµnh
phè 1 ®Õn thµnh phè 3 cã ®é dµi 320 km vµ sè tiÒn ph¶i tr¶ cho mçi lÇn ®i lµ 25
®ång.

H·y kiÓm tra tÝnh ®óng ®¾n cña
d÷ liÖu.

KiÓm tra tÝnh Liªn th«ng, tÝnh
Tèi ­u vµ Hoµn h¶o cña hÖ thèng ®­êng trªn.

C©u 2:

Gi¶i quyÕt c¸c bµi to¸n (A),
(B), (C), (D) cho hÖ thèng ®­êng trªn.

KÕt qu¶ ghi l¹i vµo c¸c tÖp v¨n
b¶n cã tªn A.KQ, B.KQ, C.KQ. Riªng bµi to¸n (B) ph¶i cã ®ñ c¶ 3 ph­¬ng ¸n.

Bµi to¸n (D) kh«ng cÇn ®­a kÕt
qu¶ ra tÖp v¨n b¶n.

Chó ý:

KÕt qu¶ cã thÓ võa ®­a ra mµn
h×nh võa ghi l¹i trªn ®Üa nh­ ®· nªu trªn.

H¹n chÕ sè N <= 20.

469. M« pháng ho¹t ®éng cña
Rubic

Rubic lµ mét khèi lËp ph­¬ng
gåm (3 x 3 x 3) khèi lËp ph­¬ng con. Khëi ®Ç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.

Mçi mÆt Rubic gåm 3 x 3 mÆt cña
mét líp 9 khèi lËp ph­¬ng con.

H·y h×nh dung ta ®ang nh×n vµo
mét mÆt bÊt kú trong 6 mÆt cña Rubic. Mét líp gåm 3 x 3 khèi lËp ph­¬ng con cã
thÓ quay 90o 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 quay lµ mét khèi lËp ph­¬ng (3 x 3x 3) kh¸c (mµu cña 4
mÆt liÒn kÒ cã sù thay ®æi).

Cã thÓ ký hiÖu mµu c¸c mÆt nh­
sau:

U: mµu mÆt trªn; R: mµu mÆt
ph¶i; F: mµu mÆt tr­íc; B: mµu mÆt sau; L: mµu mÆt bªn tr¸i; D: mµu mÆt d­íi.

Mét 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,B,L,D}. Trong ®ã mçi ch÷ c¸i thÓ
hiÖn mét phÐp quay c¬ së: quay 90o theo chiÒu kim ®ång hå cña mÆt
t­¬ng øng. H·y viÕt ch­¬ng tr×nh cho phÐp ng­êi dïng gi¶i nhiÒu lÇn 3 bµi to¸n
d­íi ®©y:

1) Cho x©u vßng quay liªn tiÕp,
biÕn ®æi x©u ®ã thµnh x©u sao cho kh«ng cã mét phÐp quay c¬ së nµo xuÊt hiÖn
qu¸ 3 lÇn. Ch­¬ng tr×nh cÇn ph¸t hiÖn c¸c x©u Input kh«ng chuÈn.

2) Cho hai 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?

3) 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 ®ã.

470. T« mµu l­íi « vu«ng

Cho l­íi « vu«ng A h×nh ch÷
nhËt m hµng, n cét (trong ®ã 10<=m, n<=100). Mçi « vu«ng ®­îc ®¸nh sè bëi
mét trong 6 mµu: Xanh, ®á, TÝm, Vµng, ®en, Tr¾ng. BiÕt r»ng mçi mµu ®­îc dïng
Ýt nhÊt hai lÇn.

1) NhËp d÷ liÖu cña A tõ bµn
phÝm.

2) X¸c ®Þnh trong mçi mµu, cã
bao nhiªu lÇn mµu ®ã xuÊt hiÖn trong A? ChiÕu kÕt qu¶ lªn mµn h×nh.

3) S¾p xÕp l¹i m¶ng A sao cho
víi mçi « vu«ng bÊt kú ®Òu t×m thÊy mét « vu«ng kh¸c hoÆc cïng hµng hoÆc cïng
cét ®­îc ®¸nh dÊu cïng mét mµu víi nã.

471. ThuËt to¸n t¹o d·y con ®¬n
®iÖu

Cho d·y n sè nguyªn x1, x2,
…, xn, trong ®ã 1<=n<=1000 vµ 1<=xi<=200.

1) NhËp d÷ liÖu vµo tõ bµn
phÝm.

2) T×m c¸ch g¹ch bá mét sè Ýt
nhÊt c¸c phÇn tö cña d·y sao cho c¸c phÇn tö cßn l¹i (gi÷ nguyªn thø tù cña
chóng) t¹o thµnh d·y con kh«ng gi¶m. In ra c¸c d·y con t×m ®­îc vµ sè thø tù
cña c¸c phÇn tö ®ã.

472. LÞch tr×nh bay ng¾n nhÊt

Cã n s©n bay ®­îc ®¸nh sè tõ 1
®Õn n t¹o thµnh r tuyÕn bay: M1, M2, …, Mr. Mçi tuyÕn bay ®­îc x¸c ®Þnh bëi
d·y c¸c s©n bay ®­a ®ãn kh¸ch cña nã:

M1 = (i1,1, i1,2,
…, i1,m1),

M2 = (i2,1, i2,2,
…, i2,m2),

……………………….

Mr = (ir,1, ir,2,
…, ir,mr).

Víi mäi j = 1,2, …, r vµ víi
mäi p,k = 1,2,.., mj mµ p ¹ k th× ij,p ¹ ij,k
(1<=ij,p,

ij,k <=n ).

1) NhËp tõ bµn phÝm n, r vµ c¸c
d·y Mi (i = 1,…,r).

2) Gi¶ thiÕt thêi gian bay gi÷a
hai s©n bay liÒn kÒ trong mäi tuyÕn bay ®Òu nh­ nhau vµ b»ng 1/2 thêi gian ®ç
l¹i t¹i mçi s©n bay vµ b»ng 1/3 thêi gian ®Ó ®æi tuyÕn bay. Cho sè hiÖu hai s©n
bay bÊt kú i vµ j. H·y x¸c ®Þnh lÞch tr×nh nhanh nhÊt bay tõ i tíi j. ChiÕu lªn
mµn h×nh thêi gian cÇn thiÕt Ýt nhÊt ®ã vµ tÊt c¶ c¸c lÞch tr×nh t×m ®­îc.

473. Ma trËn th­a

Ma trËn th­a lµ ma trËn cã sè
c¸c phÇn tö kh¸c 0 kh¸ Ýt. Do vËy, ®Ó biÓu diÔn mét ma trËn th­a M nµo ®ã cã k
phÇn tö kh¸c 0 ng­êi ta dïng 3 m¶ng mét chiÒu A, C, D bËc k. C¸c m¶ng A, C, D
®­îc x¸c ®Þnh nh­ sau: NÕu Mi,j lµ phÇn tö kh¸c 0 thø p cña M (tÝnh
lÇn l­ît tõ trªn xuèng d­íi vµ tõ tr¸i sang ph¶i) th×:

Ap = Mi,j;
Cp = j; Dp = i (p = 1,2,…,k).

1) NhËp hai ma trËn th­a M vµ
M’ cïng bËc n x n tõ bµn phÝm. T¹o vµ in lªn mµn h×nh c¸c m¶ng A, C, D vµ At,
Ct, Dt lµ biÓu diÔn t­¬ng øng cña hai ma trËn th­a Êy.

2) Sö dông c¸ch biÓu diÔn nªu
trªn:

– In lªn mµn h×nh c¸c m¶ng At,
Ct, Dt lµ biÓu diÔn t­¬ng øng cña ma trËn Mt
lµ ma trËn chuyÓn vÞ cña ma trËn M.

– In lªn mµn h×nh c¸c m¶ng A+,
C+, D+ vµ A*, C*, D* biÓu diÔn t­¬ng øng cña tæng vµ tÝch
hai ma trËn th­a M vµ M’ Êy.

Yªu cÇu b¾t buéc: kh«ng dïng
c¸c m¶ng hai chiÒu.

474. NhËn hÕt c©u lÖnh

1) NhËp mét x©u ký tù tõ bµn
phÝm. KiÓm tra xem ®ã cã ph¶i lµ c©u lÖnh ®æi tªn file (cña MS-DOS) hay kh«ng?

2) Gi¶ sö x©u ký tù ®­îc nhËp
lµ c©u lÖnh ®æi tªn File. H·y ph©n tÝch xem c©u lÖnh ®ã ®­îc viÕt ®óng hay sai?
NÕu sai th× chØ ra lçi xuÊt hiÖn ë vÞ trÝ nµo ®Çu tiªn?

Chó thÝch: M¸y cã 3 æ ®Üa A, B,
C. Mäi tªn file hoÆc tªn th­ môc hîp lÖ ®Òu ®­îc coi lµ cã trªn ®Üa.

475. n x©u ký tù

Cho tÖp v¨n b¶n (file kiÓu
TEXT) cã tªn DULIEU.INP chøa n dßng S1, . . ., Sn víi n>=3, mçi dßng ®Òu
kh«ng trèng. Nãi r»ng x©u P lµ thµnh phÇn cña dßng Si vµ ký hiÖu lµ P<Si,
nÕu P cã ®é dµi lín h¬n 1 vµ cã thÓ nhËn ®­îc tõ Si b»ng c¸ch xo¸ mét sè ký tù
cña Si.

Nãi P lµ thµnh phÇn chung cña
c¸c dßng S1, S2,…,Sn nÕu P<Si víi mäi i = 1,2,…,n.

1) H·y cho biÕt file ®· cho cã
bao nhiªu dßng vµ t×m mét thµnh phÇn chung P cña tÊt c¶ c¸c dßng Si ®· cho
trong file.

2) T×m thµnh phÇn chung Q cã ®é
dµi lín nhÊt cña S1, S2,…, Sn.

Yªu cÇu: Víi hai c©u trªn (1)
vµ (2) h·y hiÓn thÞ:

– Víi mçi i=1,2,..,n hiÖn tÊt
c¶ c¸c vÞ trÝ lÇn l­ît bÞ xo¸ trong dßng Si.

– P, Q vµ ®é dµi cña chóng.

– NÕu P vµ Q kh«ng tån t¹i: h·y
th«ng b¸o ®iÒu ®ã.

3) T×m k lín nhÊt tho¶ m·n: Q
< Sm1< Sm2< …< Smk.

Trong ®ã Smj (j =
1,2,…,k) lµ nh÷ng dßng trong tÖp ®· cho. HiÓn thÞ k vµ c¸c mj theo trËt tù
nãi trªn.

4) Víi i,j bÊt kú nhËp tõ bµn
phÝm h·y t×m c¸ch biÕn ®æi dßng Si thµnh Sj b»ng c¸ch sö dông Ýt nhÊt cã thÓ
®­îc c¸c phÐp biÕn ®æi, ®èi víi tõng tr­êng hîp sau:

a. ChØ sö dông hai lo¹i phÐp
to¸n: chÌn mét ký tù, xãa mét ký tù.

b. ChØ sö dông ba lo¹i phÐp
to¸n: chÌn mét ký tù, xo¸ mét ký tù vµ thay mét ký tù trong x©u b»ng mét ký tù
kh¸c tïy ý. H·y hiÓn thÞ lÇn l­ît vÞ trÝ vµ phÐp to¸n ®· ®­îc sö dông, tæng sè
c¸c phÐp biÕn ®æi mçi lo¹i.

Yªu cÇu: Ch­¬ng tr×nh ph¶i cã
kh¶ n¨ng thùc hiÖn ®éc lËp tõng yªu cÇu ®· nªu.

476. X©u ký tù thuÇn nhÊt

X©u ký tù thuÇn nhÊt (®­îc ®Þnh
nghÜa) lµ x©u chØ bao gåm c¸c ch÷ c¸i tiÕng Anh. Mét x©u thuÇn nhÊt cã thÓ ®­îc
viÕt d­íi d¹ng thu gän, bao gåm c¸c nhãm ký tù cã thÓ kÌm theo sè lÇn xuÊt hiÖn
liªn tiÕp cña nhãm ®ã.

VÝ dô:

x©u:

‘XCAABAABAABCCADADCAABAABAABCCADADY’

cã thÓ viÕt d­íi d¹ng thu gän:

‘X(C(A2B)3C2(A1D)2)2Y’.

Cho mét file kiÓu TEXT cã tªn
‘XAU’ gåm c¸c dßng ký tù, mçi dßng lµ mét x©u. 1) H·y ®äc lÇn l­ît tõng x©u cña
file ®· cho, th«ng b¸o x©u ®ã thuéc nh÷ng d¹ng nµo trong sè 3 d¹ng d­íi ®©y:

– D¹ng thuÇn nhÊt.

– D¹ng thu gän cña d¹ng thuÇn
nhÊt.

– D¹ng sai: x©u kh«ng ph¶i lµ
d¹ng thuÇn nhÊt vµ còng kh«ng ph¶i lµ d¹ng thu gän.

2) NÕu x©u ®äc ®­îc thuéc d¹ng
thuÇn nhÊt, h·y biÕn ®æi nã vÒ d¹ng thu gän cã chiÒu dµi ng¾n nhÊt cã thÓ ®­îc.
NÕu x©u ®äc ®­îc thuéc d¹ng thu gän, h·y biÕn ®æi nã trë l¹i d¹ng thuÇn nhÊt
t­¬ng øng. ®èi víi mçi x©u ®äc ®­îc h·y hiÓn thÞ:

– ChÝnh x©u ®ã.

– Lo¹i x©u.

– X©u ®· ®­îc biÕn ®æi.

– ®èi víi x©u sai, h·y chØ ra
mét nguyªn nh©n dÉn ®Õn sai.

477. Xoay c¸c khèi lËp ph­¬ng

Trªn l­íi « vu«ng kÝch th­íc
m×n (m£8, n£15) xÕp mçi « mét khèi lËp ph­¬ng (H×nh 477.1). Mçi mÆt cña khèi
lËp ph­¬ng ®­îc ®¸nh sè theo mét trong hai c¸ch sau ®©y:

– C¸ch a: Mçi mÆt cña khèi lËp
ph­¬ng ®­îc ghi mét trong ba sè 1,2,3. C¸c mÆt ®èi nhau cã sè nh­ nhau. Trªn
mçi khèi lËp ph­¬ng ®Òu xuÊt hiÖn ®Çy ®ñ c¶ ba sè nãi trªn.

– C¸ch b: Mçi mÆt cña khèi lËp
ph­¬ng ®­îc ghi mét trong s¸u sè 1,2,3,4,5,6 sao cho tæng hai sè trªn hai mÆt ®èi
diÖn ®Òu b»ng 7. C¸c sè ë c¸c mÆt kh¸c nhau lµ kh¸c nhau.

Víi mçi c¸ch ®¸nh sè nãi trªn,
mçi khèi lËp ph­¬ng ®­îc ®Æc tr­ng b»ng mét bé ba gi¸ trÞ (a, b, c), trong ®ã a
– sè ë mÆt trªn, b – sè ë mÆt tr­íc, c – sè ë mÆt ph¶i (H×nh 477.2).

C¸c khèi lËp ph­¬ng cã thÓ quay
quanh trôc X hoÆc trôc Y. ®­îc phÐp ¸p dông c¸c phÐp xoay sau: Xi+, Xi-, Yj+,
Yj-.

Trong ®ã:

– Xi+ (hay Xi-) xoay toµn bé
c¸c khèi lËp ph­¬ng ë hµng thø i mét gãc 90o quanh trôc X ng­îc (hay
cïng) chiÒu kim ®ång hå (H×nh 477.2).

– Yj+ (hay Yj-)
xoay toµn bé c¸c khèi lËp ph­¬ng ë cét thø j mét gãc 90o quanh trôc
Y ng­îc (hay cïng) chiÒu kim ®ång hå (H×nh 477.2).

Cho file d÷ liÖu kiÓu TEXT cã
tªn lµ ‘XOAY’, trong ®ã dßng ®Çu ghi c¸c gi¸ trÞ m vµ n, mçi dßng tiÕp theo ghi
gi¸ trÞ bé ba a,b,c t­¬ng øng cña tõng khèi lËp ph­¬ng tõ tr¸i qua ph¶i lÇn
l­ît theo tõng hµng.

Yªu cÇu:

1) NhËp tõ bµn phÝm mét sè vµ
¸p dông c¸c quy t¾c ®· nªu ®Ó ®­a tÊt c¶ c¸c khèi lËp ph­¬ng vÒ h×nh tr¹ng cã
sè ë mÆt trªn nh­ sè ®· nhËp. Sau mçi lÇn xoay h·y hiÓn thÞ ®ång thêi trªn cïng
mét trang mµn h×nh trong kho¶ng thêi gian kh«ng Ýt h¬n 0.5 gi©y:

– C¸c bé gi¸ trÞ a,b,c cña tõng
khèi lËp ph­¬ng tr­íc khi xoay.

– L­íi m×n c¸c sè ë mÆt trªn
cña khèi tr­íc khi xoay.

– PhÐp xoay ®­îc sö dông.

– L­íi m×n c¸c sè ë mÆt trªn
cña khèi sau khi xoay.

2) Sö dông c¸c phÐp xoay nãi
trªn ®Ó biÕn ®æi h×nh tr¹ng ®­îc thÓ hiÖn ë file ‘XOAY’ vÒ h×nh tr¹ng cã c¸c sè
ë mÆt trªn cña m x n khèi lËp ph­¬ng ®­îc ®­a tõ bµn phÝm tõ tr¸i qua ph¶i vµ
lÇn l­ît theo tõng hµng.

Gi¶i quyÕt c¸c yªu cÇu (1) vµ
(2) víi tõng c¸ch ®¸nh sè (a) vµ (b) nªu trªn.

Yªu cÇu: Ch­¬ng tr×nh ph¶i cã
kh¶ n¨ng thùc hiÖn c¸c yªu cÇu mét c¸ch ®éc lËp.

478. S – d·y

(§Ò thi Olimpic quèc tÕ 1991)

Ta gäi mét “S-d·y” lµ
x©u bao gåm ký tù S vµ c¸c dÊu ®ãng më ngoÆc ®­îc ®Þnh nghÜa ®Ö qui nh­ sau:

– S lµ S-d·y.

– NÕu M,N lµ S-d·y th× (MN)
còng lµ S-d·y.

Sau ®©y lµ vÝ dô cña mét S-d·y:
((((SS)(SS))S)(SS)).

C¸c dÊu ngoÆc ph¶i kh«ng mang
thªm th«ng tin míi nµo do vËy cã thÓ bá chóng ®i ®­îc, nghÜa lµ cã thÓ viÕt (MN
thay cho (MN). Trong thÝ dô trªn cã thÓ viÕt:

((((SS(SSS(SS .

1) ViÕt thñ tôc
“Gensterm” sinh c¸c S-d·y: Thñ tôc cÇn ph¶i t¹o ra n file Text, c¸c
file nµy sÏ chøa tÊt c¶ c¸c S-d·y ®é dµi lÇn l­ît lµ 1,2,..n (®é dµi ë ®©y hiÓu
lµ sè c¸c ký tù S). Mçi S-d·y n»m trªn mét dßng. ViÕt ch­¬ng tr×nh nhËp tõ bµn
phÝm sè tù nhiªn n (n<=10). Sö dông thñ tôc trªn ®Ó sinh ra vµ hiÖn lªn mµn
h×nh tÊt c¶ c¸c S-d·y t­¬ng øng.

XÐt phÐp biÕn ®æi sau trªn c¸c
S-d·y. C¸c phÐp biÕn ®æi nµy ®­îc gäi lµ S-bd:

Mét d·y con cña S-d·y cã d¹ng
(((SA)B)C) cã thÓ viÕt l¹i d­íi d¹ng ((AC)(BC)) (ë ®©y A,B,C lµ c¸c S-d·y).

VÝ dô:

Context1(((SA)B)C)Context2 ®
Context1((AC)(BC)) Context2.

ViÖc ¸p dông c¸c phÐp biÕn ®æi
trªn ®èi víi S-d·y còng ®­îc gäi lµ c¸c phÐp “Rót gän”.

Cã rÊt nhiÒu c¸ch ¸p dông c¸c
phÐp S-bd trªn c¸c S-d·y. Qu¸ tr×nh biÕn ®æi mét S-d·y cho ®Õn khi kh«ng thÓ
biÕn ®æi ®­îc n÷a gäi lµ qu¸ tr×nh chuÈn ho¸ cña S-d·y.

Sau ®©y lµ vÝ dô cña mét chuçi
rót gän nh­ vËy:

((((SS)(SS))S)(SS)) ®
(((SS)((SS)S))(SS)) ®

((S(SS))(((SS)S)(SS))) ®
((S(SS))((S(SS))(S(SS))))

2) H·y t×m mét cÊu tróc d÷ liÖu
hîp lý ®Ó biÓu diÔn c¸c S-d·y vµ c¸c phÐp biÕn ®æi S-bd trªn c¸c d·y nµy.

ViÕt hai thñ tôc:

“Readterm” dïng ®Ó
biÕn ®æi S-d·y tõ d¹ng sinh ra bëi Gensterm vÒ d¹ng d÷ liÖu hîp lý cña b¹n.

“Printterm” dïng ®Ó
biÕn ®æi S-d·y tõ d¹ng hîp lý cña b¹n vÒ d¹ng ®­îc sinh bëi Gensterm.

Ch­¬ng tr×nh ph¶i biÓu diÔn
®­îc c¸c biÕn ®æi trªn.

3) ViÕt thñ tôc
“Reduce” dïng ®Ó biÓu diÔn mét b­íc rót gän tu©n theo qui luËt S-bd.

4) ViÕt thñ tôc
“Normalize”: cho tr­íc mét S-d·y, cÇn ¸p dông mét chuçi c¸c S-d trªn
S-d·y nµy cho ®Õn khi kh«ng thÓ biÕn ®æi ®­îc n÷a hoÆc cho ®Õn khi sè c¸c phÐp
biÕn ®æi v­ît qu¸ mét giíi h¹n nµo ®ã, vÝ dô 30. Ch­¬ng tr×nh cÇn thÓ hiÖn râ
qu¸ tr×nh rót gän nµy.

5) KÕt hîp tÊt c¶ c¸c yªu cÇu
trªn ®Ó viÕt mét ch­¬ng tr×nh:

a. ®äc vµo sè n tõ bµn phÝm.

b. Sö dông Gensterm sinh ra c¸c
S-d·y cã ®é dµi n.

c. BiÕn ®æi c¸c S-d·y nµy vÒ
d¹ng hîp lý cña b¹n.

d. ChuÈn hãa d·y nµy nÕu cã thÓ
®­îc.

e. KÕt qu¶ ®­a ra b¶ng c¸c
S-d·y ®· ®­îc chuÈn ho¸.

f. Ghi l¹i sè c¸c phÐp rót gän
®¬n vÞ c¸c S-d·y ®· ®­îc chuÈn ho¸ hoÆc ®­a ra th«ng b¸o “Kh«ng chuÈn hãa
®­îc” ®èi víi c¸c S-d·y kh«ng chuÈn ho¸ ®­îc hoÆc sè phÐp biÕn ®æi v­ît
qu¸ 30.

g. Ghi l¹i tæng sè c¸c S-d·y
kh«ng chuÈn hãa ®­îc vµ tæng sè c¸c S-d·y cã thÓ chuÈn hãa ®­îc.

479. LÞch kh¸m b¸c sÜ

Gi¸o s­ W.Semorton bÞ bÖnh, «ng
cÇn tham kh¶o ý kiÕn c¸c b¸c sÜ. V× vËy «ng muèn cã ®­îc mét lÞch gÆp c¸c b¸c
sÜ trong ngµy sao cho cµng gÆp ®­îc nhiÒu b¸c sÜ cµng tèt. H·y viÕt ch­¬ng
tr×nh lËp lÞch gióp cho Gs Semorton thùc hiÖn ®­îc ý muèn nãi trªn.

Input file ®­¬c t¹o tõ c¸c
dßng, mçi dßng bao gåm: tªn cña b¸c sÜ, thêi ®iÓm b¾t ®Çu vµ thêi ®iÓm kÕt thóc
cña kho¶ng thêi gian b¸c sÜ ®ã cã thÓ tiÕp kh¸ch vµ tªn c¬ quan n¬i «ng ta lµm
viÖc. C¸c quy t¾c lËp lÞch lµ nh­ sau:

1) Mçi cuéc gÆp ph¶i diÔn ra Ýt
nhÊt lµ 60 phót. «ng gi¸o s­ cÇn Ýt nhÊt lµ 30 phót gi÷a hai cuéc gÆp ®Ó di
chuyÓn tõ c¬ quan nµy ®Õn c¬ quan kh¸c.

2) TÊt c¶ thêi gian cho trong
Input file ®Òu thuéc cïng mét ngµy vµ «ng Gs kh«ng muèn gÆp mét «ng b¸c sÜ nµo
®ã hai lÇn trong cïng mét ngµy.

3) Hai cuéc gÆp liªn tiÕp nhau
kh«ng ®­îc x¶y ra trong cïng mét c¬ quan.

4) Trong sè c¸c b¸c sÜ, «ng Gs
lu«n thÝch gÆp b¸c sÜ lµ ng­êi cã thÓ gÆp sím h¬n c¶.

5) NÕu cã nhiÒu h¬n mét b¸c sÜ
mµ «ng Gs cã thÓ gÆp cïng mét lóc th× «ng Gs muèn gÆp ng­êi cã thêi gian tiÕp
kh¸ch cßn l¹i lµ Ýt nhÊt cã thÓ ®­îc.

6) «ng Gs lu«n nhí ®­îc thêi
gian cña cuéc hÑn tiÕp theo, v× thÕ nÕu cÇn vµ khi ®· gÆp ®­îc 60 phót råi, «ng
Gs cã thÓ ®×nh chØ cuéc gÆp hiÖn thêi ®Ó cã thÓ tiÕn hµnh kÞp cuéc gÆp tiÕp
theo.

7) NÕu «ng Gs kh«ng ph¶i véi
cho cuéc gÆp tiÕp theo, «ng cã thÓ kÐo dµi cuéc gÆp ®ang tiÕn hµnh.

VÝ dô d¹ng d÷ liÖu cña input
file ®­îc viÕt nh­ sau:

Hoµ 16.00 – 17.25 ViÖn_M¾t

HuÖ 09.30 – 11.50 B¹ch_Mai

Hång 22.00 – 23.05 Xanh_P«n

. . . . . . . . . . . . . . . .
. . . . . .

VÝ dô d¹ng d÷ liÖu cña output
file ®­îc viÕt nh­ sau:

09.30 – 11.10 HuÖ B¹ch_Mai

16.00 – 17.25 Hoµ ViÖn_M¾t

. . . . . . . . . . . . . . . .
. . . . . . . . . .

* Gi¶i bµi to¸n trªn cho c¶ vî
«ng Gs víi mét h¹n chÕ bæ sung lµ kh«ng cho c¶

hai «ng bµ Gs cïng gÆp mét b¸c
sÜ trong cïng mét lóc.

480. Trß ch¬i bèc sái

Cho mét ®èng sái N viªn (N
<= 40). Hai ng­êi ch¬i lu©n phiªn bèc sái. Mçi lÇn ph¶i bèc ®óng k viªn
(k>=3 vµ lµ sè nguyªn tè cho tr­íc). Sau mçi lÇn bèc, nÕu muèn ng­êi võa bèc
sái cã thÓ chia phÇn cßn l¹i cña ®èng sái võa bèc thµnh hai ®èng tïy ý. Mçi lÇn
chØ ®­îc bèc ë mét ®èng sái. Ng­êi nµo ®Õn l­ît mµ kh«ng bèc ®­îc th× coi bÞ
thua.

1) Víi k vµ N cho tr­íc, cã tån
t¹i mét c¸ch bèc ®Ó ng­êi ®i tr­íc lu«n th¾ng kh«ng? Tr×nh bµy lËp luËn.

2) Tr×nh bµy chiÕn l­îc vµ
ch­¬ng tr×nh t­¬ng øng thÓ hiÖn trß ch¬i trªn ®Ó cho m¸y cã kh¶ n¨ng th¾ng
nhiÒu nhÊt. Gi¶ sö m¸y ®i tr­íc, ng­êi ®i sau vµ thÓ hiÖn c¸ch ®i cña m×nh qua
bµn phÝm. Sau mçi l­ît ®i cña tõng ®èi thñ cÇn ®­a lªn mµn h×nh d­íi d¹ng thÝch
hîp t×nh tr¹ng hiÖn thêi:

– Cã bao nhiªu ®èng sái.

– Sè l­îng mçi ®èng.

481. ThuËt to¸n tÝnh luü thõa

Cã thÓ tÝnh X55 chØ b»ng c¸c
phÐp nh©n vµ sè c¸c phÐp nh©n nhá h¬n 9 hay kh«ng? ®ã lµ nh÷ng phÐp nh©n nµo?
NÕu kh«ng thÓ ®­îc th× h·y gi¶i thÝch t¹i sao?

XÐt tr­êng hîp tæng qu¸t:

H·y x¸c ®Þnh sè N nguyªn d­¬ng
bÐ nhÊt cã thÓ sao cho cã thÓ tÝnh ®­îc Xm(m nguyªn d­¬ng cho tr­íc vµ X tïy ý)
bëi Ýt h¬n N phÐp nh©n. H·y viÕt ch­¬ng tr×nh thùc hiÖn c¸c phÐp nh©n ®ã ®Ó
nhËn ®­îc kÕt qu¶ cuèi cïng lµ Xm. §­a ra mµn h×nh kÕt qu¶ cña tõng phÐp nh©n
trªn.

482. Bµn Bi-a

Cho 4 täa ®é cña mét bµn bi-a
ch÷ nhËt:

(0,0) , (x,0) , (0,y) , (x,y)

Cho to¹ ®é cña mét qu©n bi-a
trªn bµn (x1,y1) víi 0<x1<x, 0<y1<y. Trªn bµn cã 4 lç thñng ë 4
gãc. T¸c ®éng vµo qu©n bi-a k ®¬n vÞ lùc ®Èy theo h­íng h, trong ®ã h biÓu thÞ
gãc lÖch so víi tia Ox, ®o b»ng ®é: 0o<=h<360o.

Gi¶ thiÕt:

– 1 ®¬n vÞ lùc ®Èy lµm cho bi-a
l¨n ®i xa 0,9.

– Trªn ®­êng chuyÓn ®éng khi va
vµo c¹nh bªn, bi-a nÈy trë l¹i theo nguyªn lý ph¶n x¹ cña ¸nh s¸ng (gãc tíi
b»ng gãc ph¶n x¹).

1) H·y m« t¶ thuËt gi¶i vµ viÕt
ch­¬ng tr×nh x¸c ®Þnh vÞ trÝ míi cña bi-a trªn bµn sau khi bÞ ®Èy.

2) H·y chØ ra mét c¸ch ®Èy sao
cho bi-a ch¾c ch¾n sÏ r¬i vµo lç.

483. MÉu « vu«ng trïng nhau

Cho mét b¶ng « vu«ng n hµng vµ
m cét (m vµ n ®ñ lín). « ë hµng i cét j cña b¶ng gäi lµ « (i,j). Hai « gäi lµ
kÒ nhau nÕu chóng cã chung c¹nh. Mét mÉu lµ mét tËp hîp nµo ®ã c¸c « cña b¶ng
sao cho mçi « trong tËp hîp ®Òu cã 2 « kh¸c

trong tËp hîp kÒ víi nã.

MÉu B lµ tÞnh tiÕn cña mÉu A
nÕu cã 2 sè nguyªn kh«ng ©m r vµ s sao cho:

Hai mÉu gäi lµ trïng nhau nÕu
mét trong hai mÉu cã thÓ nhËn ®­îc tõ mÉu kia

b»ng c¸ch ¸p dông phÐp tÞnh
tiÕn hoÆc phÐp chuyÓn vÞ.

H·y m« t¶ gi¶i thuËt vµ viÕt
ch­¬ng tr×nh ®Ó x¸c ®Þnh mÉu A vµ B cho tr­íc cã

trïng nhau hay kh«ng?

484. T¹o ®­êng gÊp khóc ®i qua
c¸c ®iÓm cho tr­íc

Cho N ®iÓm P1, P2,…,Pn trªn
mÆt ph¼ng cã c¸c to¹ ®é t­¬ng øng lµ (x1,y1), (x2,y2),..,(xn,yn).

1) H·y dùng mét ®­êng gÊp khóc
khÐp kÝn kh«ng tù c¾t ®i qua tÊt c¶ c¸c ®iÓm nãi trªn vµ ®i qua mçi ®iÓm ®óng
mét lÇn.

2) ®­êng gÊp khóc nãi trªn cã
®é dµi ng¾n nhÊt cã thÓ lµ bao nhiªu?

485. Qui ®Þnh ®­êng ®i 1 chiÒu

Cã N thµnh phè A1, A2, …, An
vµ mét sè ®­êng nèi c¸c thµnh phè nµy. §Ó tr¸nh ïn t¾c giao th«ng, ng­êi ta ®·
qui ®Þnh tÊt c¶ c¸c ®­êng ®i thµnh mét chiÒu. HÖ thèng ®­êng ®i ®¶m b¶o tÝnh
chÊt liªn th«ng nÕu nh­ tõ mét thµnh phè bÊt kú ®Òu ®i ®Õn ®­îc mét thµnh phè
bÊt kú kh¸c (cã thÓ qua mét sè thµnh phè trung gian).

H·y x¸c ®Þnh xem sau khi ®· qui
®Þnh hÖ thèng ®­êng thµnh mét chiÒu, hÖ thèng ®­êng cã cßn liªn th«ng kh«ng?

C¸c chiÒu ®i cÇn qui ®Þnh l¹i
nh­ thÕ nµo vµ sè Ýt nhÊt c¸c ®­êng ®i nµo cÇn ®­îc x©y dùng thªm ®Ó hÖ thèng
®­êng trë thµnh liªn th«ng?

486. VÒ c¸c « vu«ng chøa ch÷

Cho h×nh vu«ng A kÝch th­íc M x
M « vu«ng, mçi « chøa mét ch÷ c¸i in hoa bÊt kú (trong b¶ng ch÷ tõ A ®Õn Z).
C¸c phÐp biÕn ®æi Bn vµ C2 ®­îc ®Þnh nghÜa nh­ sau:

– Lo¹i Bn: chän h×nh vu«ng con
bÊt kú kÝch th­íc n x n (n>=2) tõ h×nh vu«ng A vµ chuyÓn c¸c ch÷ c¸i trong
mçi « sang ch÷ c¸i kÒ sau trong b¶ng ch÷ (qui ­íc kÒ sau Z lµ A).

– Lo¹i C2: chän h×nh ch÷ nhËt
kÝch th­íc 1 x 2 « vµ chuyÓn c¸c ch÷ c¸i ®ã còng theo qui t¾c nh­ ®èi víi phÐp
biÕn ®æi Bn.

1) Thùc hiÖn c¸c phÐp biÕn ®æi
Bn, C2 lµm cho tÊt c¶ c¸c « cña h×nh vu«ng A ban ®Çu ®Òu chøa ch÷ A.

2) Cã thÓ gi¶i bµi to¸n nh­ c©u
(1) mµ c¸c phÐp biÕn ®æi Bn ®Òu ®­îc thùc hiÖn

tr­íc c¸c phÐp biÕn ®æi C2. NÕu
®­îc th× sè l­îng Bn Ýt nhÊt cã thÓ lµ bao nhiªu?

§­a th«ng tin ra mµn h×nh:

– Sè lÇn ¸p dông liªn tiÕp mét
phÐp biÕn ®æi nµo ®ã.

– Tªn phÐp biÕn ®æi.

– Täa ®é: gãc tr¸i trªn ®èi víi
Bn.

gãc tr¸i trªn vµ gãc ph¶i d­íi
®èi víi C2.

487. D·y con xo¾n tr«n èc

Cho hai sè tù nhiªn n (n<30)
vµ m (m<10). Cho mét m¶ng h×nh vu«ng gåm n hµng n cét, trªn ®ã cã xÕp c¸c sè
nguyªn. LiÖt kª c¸c phÇn tö cña m¶ng theo mét thø tù kiÓu xo¸y tr«n èc nh­ h×nh
vÏ d­íi ®©y (tr­êng hîp n=4):

Tõ d·y c¸c phÇn tö cña m¶ng
®­îc liÖt kª theo thø tù nãi trªn, h·y chØ ra ®o¹n

con trong d·y mµ gi¸ trÞ c¸c sè
trong ®o¹n con sai kh¸c nhau kh«ng qu¸ m. KÕt

qu¶ ®­îc cho d­íi d¹ng:

– Sè l­îng phÇn tö cña ®o¹n
con.

– LiÖt kª tõng phÇn tö trong
®o¹n con, mçi phÇn tö cho d­íi d¹ng bé ba sè:

gi¸ trÞ cña phÇn tö, chØ sè
hµng vµ chØ sè cét trong m¶ng vu«ng.

LËp ch­¬ng tr×nh:

a) NhËp d÷ liÖu tõ File Text
DATA2. Trong tÖp ®ã:

+ Dßng ®Çu tiªn chøa hai sè m
vµ n.

+ n dßng tiÕp theo chøa gi¸ trÞ
cña m¶ng lµ c¸c phÇn tö cña hµng 1, 2, 3, …,

n lÇn l­ît.

b) T×m vµ chØ ra mét ®o¹n con
gåm qu¸ mét phÇn tö vµ mét ®o¹n con dµi nhÊt

cã thÓ ®­îc.

488. C¸c qui t¾c giao ho¸n

Cho P lµ mét tËp hîp c¸c qui
t¾c giao ho¸n trªn c¸c ch÷ sè:

P = { (x1,y1),..,(xk,yk) } xi ¹
yi, i= 1,…,k.

Trong ®ã x1,…,xk, y1,…,yk
lµ c¸c ch÷ sè. Mét ho¸n vÞ ®­îc phÐp cña sè cã n+1 ch÷ sè aoa1…aiai+1…an lµ
sè aoa1…aiai+1…an víi (ai,ai+1)Î P hoÆc (ai+1,ai)P.

Sè B nhËn ®­îc tõ A b»ng c¸ch
¸p dông c¸c qui t¾c giao ho¸n cña P nÕu cã sè Ao,…,Am sao cho:

Ao=A, Am=B vµ Ai lµ ho¸n vÞ
®­îc phÐp cña Ai-1, i=1,..,m.

Cho tr­íc sè A gåm n+1 ch÷ sè
aoa1…an. H·y t×m sè cã trÞ sè lín nhÊt nhËn ®­îc tõ A b»ng c¸ch ¸p dông c¸c
qui t¾c giao ho¸n cña P.

489. Ph­¬ng ¸n chuyÓn ®æi hép
diªm

Cho k hép diªm xÕp thµnh h×nh
trßn. Sè n1,n2,..,nk ghi trªn mçi hép lµ sè diªm

trong mçi hép. Cho phÐp chuyÓn
mét sè l­îng diªm bÊt kú (nhá h¬n hoÆc b»ng sè diªm t¹i thêi ®iÓm hiÖn thêi)
sang hép kÒ nã (tr¸i hoÆc ph¶i).

Yªu cÇu: ChuyÓn sè diªm gi÷a
c¸c hép sao cho trong mçi hép diªm cã sè l­îng

nh­ nhau.

NÕu ®­îc:

1) H·y nªu mét ph­¬ng ¸n
chuyÓn.

2) T×m ph­¬ng ¸n chuyÓn sao cho
tæng sè diªm ph¶i chuyÓn lµ Ýt nhÊt.

3) NÕu kh«ng: bæ sung mét sè Ýt
nhÊt hép diªm rçng ®Ó cã thÓ thùc hiÖn ®­îc yªu cÇu trªn.

490. Mét thuËt to¸n t¹o tÖp v¨n
b¶n

Cho mét file d¹ng ASCII cã tªn
XAU.IN chøa x©u c¸c tõ W1, W2,…, Wk cã ®é dµi t­¬ng øng l1, l2,…, lk. C¸c
tõ ph©n c¸ch nhau bëi c¸c dÊu trèng vµ cã ®é réng lµ

b. Gi¶ sö c¸c dÊu c¸ch cã thÓ
xo¸ hoÆc thªm vµo nh­ng ph¶i ®¶m b¶o gi÷ nguyªn c¸c tõ. CÊu t¹o file XAU.RA
tháa m·n c¸c ®iÒu kiÖn:

– File gåm nhiÒu dßng, mçi dßng
cã ®é dµi nh­ nhau vµ ®óng b»ng L cho tr­íc vµ chøa trän vÑn mét sè tõ: Wi,
Wi+1,…, Wj (1<=i,j<=k).

– Gi¸ ®Ó t¹o dßng (Wi,
Wi+1,…, Wj) ®­îc tÝnh b»ng (j-i)|b’ – b| (víi j>i); trong ®ã b’= (L-li-
li+1-…- lk)/(j-i). Yªu cÇu gi¸ t¹o file lµ rÎ nhÊt. ChiÕu lªn mµn h×nh:

– VÞ trÝ vµ sè l­îng xo¸ ®i hay
thªm vµo;

– Gi¸ rÎ nhÊt t×m ®­îc;

– Sè l­îng dßng cña file
XAU.RA.

491. LÞch kh¸m bÖnh

Cã N ng­êi cÇn kh¸m bÖnh theo
thø tù: ®Çu tiªn qua phßng kh¸m A, sau ®ã qua

phßng kh¸m B. C¸c phßng chØ cã
thÓ kh¸m lÇn l­ît tõng ng­êi mét. Thêi gian kh¸m cña mçi ng­êi tïy thuéc vµo
kÕt qu¶ xÐt nghiÖm tr­íc ®ã. Gi¶ sö ng­êi b¸c sÜ trùc ®· biÕt ®­îc kÕt qu¶ xÐt
nghiÖm cña tõng ng­êi, tõ ®ã «ng ta tÝnh ®­îc thêi gian cÇn kh¸m cho mçi ng­êi
ë mçi phßng t­¬ng øng. H·y lËp tr×nh thùc hiÖn c¸c c«ng viÖc sau:

1) NhËp thêi gian kh¸m bÖnh cho
mçi ng­êi ë c¸c phßng kh¸m A,B.

2) HiÓn thÞ lªn mµn h×nh mét
tr×nh tù kh¸m sao cho tæng thêi gian kh¸m lµ Ýt nhÊt vµ ®­a gi¸ trÞ nµy lªn mµn
h×nh.

492. LÞch ®i picnic

Mét tËp thÓ cã n ng­êi
(n>=3). Mçi chñ nhËt hä rñ nhau ®i picnic (kh«ng ®i mét m×nh vµ kh«ng ®i tÊt
c¶). Kh«ng cã hai ng­êi nµo ®· ®i cïng víi nhau trong mét chñ nhËt l¹i ®i cïng
víi nhau trong mét chñ nhËt kh¸c. Sau mét sè lÇn ®i nµo ®ã, c¸c thµnh viªn cña
tËp thÓ chØ cã thÓ ®i mét m×nh (v× mçi ng­êi ®· ®i cïng víi mäi ng­êi kh¸c).

VÝ dô: n=4 ng­êi 1,2,3,4. Cã
thÓ bè trÝ thµnh lÞch tr×nh ®i nh­ sau:

Buæi 1: {1,2,3}

Buæi 2: {1,4}

Buæi 3: {2,4}

Buæi 4: {3,4}

Hai lÞch tr×nh ®­îc xem lµ nh­
nhau nÕu chóng chØ kh¸c nhau con ng­êi cô thÓ

vµ kh«ng kÓ thø tù c¸c buæi ®i
(tøc lµ nÕu gäi A lµ tËp n ng­êi th× cã mét t­¬ng

øng 1-1 gi÷a c¸c phÇn tö cña A
sao cho sau khi thay ®æi thø tù c¸c buæi, tõ mét

lÞch tr×nh ta nhËn ®­îc lÞch
tr×nh kh¸c qua phÐp t­¬ng øng). VÝ dô, lÞch tr×nh trªn vµ lÞch tr×nh sau ®­îc
xem lµ mét:

Buæi 1: {2,1 }

Buæi 2: {2,3,4}

Buæi 3: {1,3}

Buæi 4: {1,4 }

PhÐp t­¬ng øng lµ 1 —> 4, 2
—> 2, 3 —> 3, 4 —> 1

Cho tËp A gåm n ®èi t­îng. H·y
t×m tÊt c¶ c¸c lÞch tr×nh kh¸c nhau.

493. BiÓu thÞ sè b»ng biÓu thøc

Cho hai phÐp to¸n *2 (nh©n víi
2) vµ /3 (chia nguyªn cho 3). Cho tr­íc sè 1. B»ng c¸ch sö dông hai phÐp to¸n
trªn ta x©y dùng ®­îc c¸c biÓu thøc cho gi¸ trÞ

lµ mét sè tù nhiªn. VÝ dô:
1*2*2*2*2*2/3/3*2=6 (c¸c phÐp to¸n trong biÓu thøc

®­îc thùc hiÖn tõ tr¸i qua
ph¶i). Cho tr­íc mét file kiÓu Text cã tªn NUM.INP chøa m dßng (m<=15), mçi
dßng lµ mét sè tù nhiªn kh«ng qu¸ 70 ch÷ sè. Víi mçi sè tù nhiªn n n¹p tõ bµn
phÝm, h·y x¸c ®Þnh vµ hiÓn thÞ biÓu thøc ng¾n nhÊt

cã thÓ ®­îc cã gi¸ trÞ b»ng
tæng cña n sè ®Çu tiªn trong file NUM.INP.

Trong tr­êng hîp kh«ng thÓ hiÓn
thÞ ®­îc, h·y nªu lý do.

494. TËp ®¹i biÓu ®¹i diÖn

Mét khu d©n c­ cã n lo¹i ng­êi,
mçi ng­êi chØ thuéc mét lo¹i vµ cã n chÝnh kiÕn kh¸c nhau, mçi ng­êi cã mét vµ
chØ mét chÝnh kiÕn (nh÷ng ng­êi thuéc cïng mét lo¹i cã thÓ cã chÝnh kiÕn kh¸c
nhau). LiÖu cã thÓ chän ra n ng­êi sao cho trong n ng­êi ®ã cã ®ñ n lo¹i vµ ®ñ
n chÝnh kiÕn? TËp n ng­êi nµy ®­îc gäi lµ tËp ®¹i diÖn ®ång thêi.

H·y viÕt ch­¬ng tr×nh nhËp sè
d©n (<256), sè n. Ph©n chia sè d©n thµnh n lo¹i (tïy chän c¸ch thÓ hiÖn).
NÕu kh«ng cã tËp ®¹i diÖn, h·y th«ng b¸o ra mµn h×nh; nÕu cã, h·y th«ng b¸o
danh s¸ch tõng ng­êi kÌm theo lo¹i vµ chÝnh kiÕn cña hä.

495. Ph­¬ng ¸n cho thuª m¸y

Mét c¬ së cã n m¸y cho thuª
trong kho¶ng thêi gian d ngµy (c¸c ngµy ®­îc ®¸nh sè tõ 1 ®Õn d). Yªu cÇu cña
mét kh¸ch thuª lµ sö dông mét m¸y trong mét sè ngµy. Gi¶ sö biÕt ®­îc yªu cÇu
cña m kh¸ch (mçi kh¸ch cho biÕt cÇn thuª m¸y vµo nh÷ng ngµy nµo trong d ngµy
trªn).

H·y lËp tr×nh x©y dùng ph­¬ng
¸n cho thuª sao cho tæng sè ngµy mµ c¸c m¸y ®­îc sö dông lµ nhiÒu nhÊt. Yªu cÇu
ch­¬ng tr×nh hiÓn thÞ danh s¸ch nh÷ng kh¸ch ®­îc chÊp nhËn vµ tæng sè ngµy
t­¬ng øng.

496. LÞch bè trÝ c«ng viÖc

CÇn ph¶i bè trÝ n c«ng viÖc
trªn mét m¸y (t¹i mét thêi ®iÓm, m¸y chØ thùc hiÖn mét c«ng viÖc). ®èi víi mçi
c«ng viÖc i (i = 1, 2, …, n) biÕt ®­îc thêi ®iÓm b¾t ®Çu thÝch hîp ai vµ thêi
®iÓm kÕt thóc thÝch hîp bi, nghÜa lµ c«ng viÖc i sÏ kh«ng bÞ ph¹t nÕu nã ®­îc
thùc hiÖn trong kho¶ng thêi gian [ai, bi]. Mçi c«ng viÖc i ®ßi hái mét thêi
gian dïng m¸y lµ pi vµ viÖc thùc hiÖn nã kh«ng ®­îc ng¾t qu·ng.

Gäi si lµ thêi ®iÓm b¾t ®Çu vµ
ti lµ thêi ®iÓm kÕt thóc cña c«ng viÖc

i (ti = si+pi).

NÕu c«ng viÖc i b¾t ®Çu sím h¬n
thêi ®iÓm ai th× sÏ chÞu mét l­îng ph¹t lµ:

gi = ki(ai-si) vµ nÕu nã kÕt
thóc muén h¬n thêi ®iÓm bi th× sÏ bÞ ph¹t mét l­îng lµ: hi = li(ti-bi) trong ®ã
ki vµ li lµ nh÷ng sè d­¬ng cho tr­íc.

H·y lËp tr×nh bè trÝ c¸c c«ng
viÖc trªn m¸y sao cho:

M = max{g1, …, gn, h1, …, hn
} ®¹t gi¸ trÞ nhá nhÊt.

Yªu cÇu ch­¬ng tr×nh hiÓn thÞ
d·y gi¸ trÞ s1, s2, …, sn c¸c thêi ®iÓm b¾t ®Çu cña c¸c c«ng viÖc vµ gi¸ trÞ
nhá nhÊt M t­¬ng øng.

497. Trß ch¬i “DOT”

Cho n x n ®iÓm lµ c¸c ®Ønh cña
mét l­íi « vu«ng (n-1)×(n-1). « cã c¹nh lµ mét ®¬n vÞ. Hai ng­êi ch¬i lÇn l­ît
thay phiªn nèi hai ®iÓm bÊt kú kÒ nhau theo chiÒu ngang hoÆc däc, mçi lÇn nèi
®óng mét cÆp ®iÓm. Mçi lÇn ng­êi nµo ®ãng kÝn ®­îc « th× ®­îc th­ëng ®iÓm;
ngoµi ra ng­êi ®ã cßn ®­îc quyÒn ®i tiÕp. Mét l­ît ®i cña mét ng­êi ®­îc tÝnh
tõ khi ng­êi ®ã b¾t ®Çu ®­îc quyÒn ®i cho ®Õn khi ng­êi ®ã ph¶i chuyÓn quyÒn ®i
cho

®èi ph­¬ng hoÆc trß ch¬i kÕt
thóc tøc lµ kh«ng cßn ai ®i tiÕp ®­îc n÷a.

1) NhËp tõ bµn phÝm sè nguyªn n
(4<=n<=15) vµ biÓu diÔn l­íi ®iÓm trªn mµn

h×nh.

2) Cho mét tr¹ng th¸i bÊt k×
gi÷a cuéc ch¬i. T×m cÊu tróc d÷ liÖu biÓu diÔn tr¹ng th¸i ®ã vµ nhËp d÷ liÖu
t­¬ng øng tõ bµn phÝm.

3) Gi¶ sö ®Õn l­ît b¹n ®i kÓ tõ
tr¹ng th¸i ®· cho. H·y chØ ra mét c¸ch ®i ®Ó b¹n cã thÓ:

– NhËn thªm ®­îc nhiÒu ®iÓm
nhÊt trong l­ît ®i nµy.

– NhËn thªm ®­îc nhiÒu ®iÓm
nhÊt sau hai l­ît ®i cña m×nh hoÆc cho ®Õn khi trß ch¬i kÕt thóc, nÕu viÖc kÕt
thóc x¶y ra tr­íc khi b¹n ®i ®ñ hai l­ît.

498. ThuËt to¸n ®a gi¸c låi

Cho n lµ sè tù nhiªn. Cã n ®iÓm
trªn mÆt ph¼ng M1, M2,…, Mn, trong ®ã Mi ®­îc cho bëi to¹ ®é thùc (Xi, Yi).

Víi n ®iÓm nãi trªn cã thÓ t¹o
ra nhiÒu ®a gi¸c n c¹nh.

LËp ch­¬ng tr×nh:

– KiÓm tra xem cã ®a gi¸c nµo
trong c¸c ®a gi¸c nãi trªn lµ låi? NÕu cã h·y chØ ra mét ®a gi¸c nh­ vËy.

– NÕu víi n ®Ønh trªn, kh«ng
thÓ t¹o ra ®­îc mét ®a gi¸c låi, h·y chØ ra c¸ch lo¹i ®i Ýt ®Ønh nhÊt ®Ó t¹o ra
®­îc mét ®a gi¸c låi.

499. XÕp thêi kho¸ biÓu d¹y häc

(®Ò thi Tin häc chän ®éi tuyÓn
quèc gia 1995)

Trong mét tr­êng häc cã M thÇy
gi¸o ®¸nh sè tõ 1 ®Õn M vµ N líp häc ®¸nh sè tõ 1 ®Õn N. Víi 1<=i<=M,
1<=j<=N, thÇy i ph¶i d¹y cho líp j P[i,j] ngµy, P[i,j] lµ sè nguyªn trong
kho¶ng tõ 0 ®Õn 10. Trong mçi ngµy mçi thÇy kh«ng d¹y h¬n mét líp vµ mçi líp
kh«ng häc h¬n mét thÇy. H·y thu xÕp lÞch d¹y cho c¸c thÇy gi¸o sao cho toµn bé
yªu cÇu gi¶ng d¹y trªn ®­îc hoµn thµnh trong sè ngµy Ýt nhÊt.

C¸c ngµy trong lÞch d¹y ®¸nh sè
lÇn l­ît 1,2,3, …

®äc th«ng tin tõ mét file v¨n
b¶n, tªn lµ INP.TXT, trong ®ã dßng ®Çu ghi lÇn l­ît gi¸ trÞ M vµ gi¸ trÞ N
(M<=20, N<=20), dßng thø i+1 (1<=i<=M) ghi lÇn l­ît N gi¸ trÞ
P[i,1], P[i,2], …, P[i, N] lµ c¸c sè nguyªn trong kho¶ng tõ 0 ®Õn 10. Hai gi¸
trÞ liÒn nhau trªn mét dßng c¸ch nhau Ýt nhÊt mét dÊu tr¾ng.

Lêi gi¶i ghi ra file v¨n b¶n cã
tªn OUT.TXT, trong ®ã dßng thø nhÊt ghi sè ngµy hoµn thµnh toµn bé khèi l­îng
gi¶ng d¹y, trong c¸c dßng tiÕp theo lÇn l­ît tõ ngµy 1, ghi theo quy c¸ch nh­
vÝ dô d­íi ®©y, mçi dßng lÞch d¹y trong ngµy ®ã cña c¸c thÇy, lÇn l­ît tõ thÇy
1, nÕu thÇy nµo kh«ng d¹y kh«ng ghi ra.

VÝ dô víi file d÷ liÖu:

5 4

2 0 0 0

0 1 1 0

1 0 1 0

1 1 1 1

0 0 0 1

File kÕt qu¶ cã thÓ cã néi dung
nh­ sau:

Sè ngµy: 4

Ngµy 1: ThÇy 2 d¹y líp 2, ThÇy
3 d¹y líp 3, ThÇy 4 d¹y líp 1

Ngµy 2: ThÇy 1 d¹y líp 1, ThÇy
2 d¹y líp 3, ThÇy 4 d¹y líp 2.

Ngµy 3: ThÇy 3 d¹y líp 1, ThÇy
4 d¹y líp 3, ThÇy 5 d¹y líp 4.

Ngµy 4: ThÇy 1 d¹y líp 1, ThÇy
4 d¹y líp 4.

500. VÒ mét phÐp biÕn ®æi ma
trËn

(§Ò thi Tin häc chän ®éi tuyÓn
quèc gia 1995)

XÐt mét b¶ng h×nh ch÷ nhËt kÝch
th­íc M x N « vu«ng. Mçi « chøa sè 0 hoÆc 1. LuËt biÕn ®æi b¶ng nh­ sau: nÕu cã
3 « liÒn nhau (cïng dßng hay cïng cét), trong ®ã cã 2 « liÒn nhau chøa sè 1,
cßn « kia chøa sè 0 th× gi¸ trÞ cña c¸c « nµy

®­îc ®¶o ng­îc (0 thµnh 1, 1
thµnh 0).

VÝ dô:

Hai « kh¸c nhau ®­îc gäi lµ kÒ
nhau nÕu chóng cã chung Ýt nhÊt mét ®iÓm biªn

(nh­ vËy mçi « cã kh«ng qu¸ 8 «
kÒ víi nã). Th«ng tin cña b¶ng ®­îc cho b»ng m¶ng 2 chiÒu A[1..M, 1..N] víi
A[i, j] b»ng sè « chøa sè 1 kÒ víi « [i, j]. 1) ®äc th«ng tin cña b¶ng tõ mét
file v¨n b¶n, tªn lµ INP.TXT, dßng ®Çu ghi lÇn

l­ît gi¸ trÞ M vµ gi¸ trÞ N
(M<=20, N<=20), dßng thø i+1 (1<=i<=M) ghi lÇn l­ît N gi¸ trÞ
A[i,1], A[i,2], …, A[i,N] lµ c¸c sè nguyªn trong kho¶ng tõ 0 ®Õn 8. Hai gi¸
trÞ liÒn nhau trªn mét dßng c¸ch nhau Ýt nhÊt mét dÊu tr¾ng. §­a ra mµn h×nh
c¸c b¶ng øng víi th«ng tin ®· ®äc (nÕu cã) hoÆc th«ng b¸o lµ kh«ng cã b¶ng nh­
vËy.

2) Trong tr­êng hîp cã b¶ng,
víi mçi b¶ng nhËn ®­îc h·y t×m d·y biÕn ®æi cã Ýt phÐp biÕn ®æi nhÊt ®Ó ®­a
b¶ng tõ tr¹ng th¸i ban ®Çu vÒ tr¹ng th¸i kh«ng biÕn ®æi ®­îc n÷a.

3) Trong tr­êng hîp cã b¶ng,
víi mçi b¶ng nhËn ®­îc h·y t×m d·y biÕn ®æi ®Ó ®­a b¶ng tõ tr¹ng th¸i ban ®Çu
vÒ tr¹ng th¸i cã sè « chøa sè 1 lµ Ýt nhÊt.

Yªu cÇu lêi gi¶i trong c¸c c©u
(2) vµ (3) ®­îc ghi ra c¸c file v¨n b¶n cã tªn t­¬ng øng lµ OUT2.TXT, OUT3.TXT,
trong ®ã øng víi mçi b­íc biÕn ®æi cÇn ghi râ trong mét dßng sè thø tù cña
b­íc, dßng tiÕp theo lµ täa ®é cña 3 « cã gi¸ trÞ bÞ thay ®æi vµ trong c¸c dßng
tiÕp theo, mçi dßng ghi mét dßng cña b¶ng sau b­íc biÕn ®æi ®ã. Hai gi¸ trÞ
liÒn nhau trªn mét dßng ghi c¸ch nhau Ýt nhÊt mét dÊu tr¾ng.

VÝ dô víi file INP.TXT cã néi
dung:

2 4

3 4 4 2

2 4 4 3

ta cã thÓ nhËn ®­îc b¶ng sau:

vµ kÕt qu¶ OUT2.TXT sÏ cã d¹ng:

1

1 1 1 2 1 3

1 0 0 1

1 1 1 0

2

2 2 2 3 2 4

1 0 0 1

1 0 0 1

 

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Chuyên mục

Tháng Mười Một 2014
H B T N S B C
« Th10   Th12 »
 12
3456789
10111213141516
17181920212223
24252627282930

NCT Computer

Flickr Photos

Staithes

Reflecting Pool

Golden Hour

More Photos

Thống kê

  • 115,384 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: