500 bài tập tin học

g 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 + 2mn Tr­êng hîp m=n th× sè trªn b»ng 2n2 + 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. §Ò sè 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 =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