Olympic lập trình

Chia sẻ: Lý Hoàng Duy | Ngày: | Loại File: PDF | Số trang:124

Thêm vào BST

Báo xấu

163
lượt xem 68
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo chuyên ngành công nghệ thông tin - Olympic lập trình. Olympic Tin học Quốc tế (International Olympiad in Informatics - IOI) là một kỳ thi tin học được tổ chức hàng năm dành cho học sinh trung học (độ tuổi tương đương với học sinh lớp 11 và 12 ở Việt Nam). Kỳ thi IOI đầu tiên được tổ chức vào năm 1989.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Olympic lập trình

VIETBOOK Olimpic lËp tr×nh I.1. C¸c bµi to¸n Olimpic Trong Olimpic Tin häc Mat-Xc¬-va, ng−êi ta ra cho häc sinh phæ th«ng mét sè nhãm bµi to¸n. Sè c¸c bµi to¸n dao ®éng tõ 5 ®Õn 11 bµi. C¸c bµi to¸n lu«n lu«n cã møc ®iÓm kh¸c nhau, xÕp theo trËt tù dÔ dÇn vµ khi tÝnh ®iÓm chØ lÊy 3 lêi gi¶i tèt nhÊt. C¸c thÝ sinh ®−îc b¸o tr−íc tÊt c¶ nh÷ng ®iÒu nµy. Nh÷ng bµi ®Çu tiªn cã thÓ lµ kh¸ khã, cßn nh÷ng bµi cuèi cïng mang tÝnh chÊt khÝch lÖ. Kú thi kÐo dµi 4 giê, lêi gi¶i cã thÓ viÕt trªn bÊt kú ng«n ng÷ nµo. Tr−íc khi gi¶i nhÊt thiÕt ph¶i viÕt thuËt gi¶i b»ng lêi. §iÒu nµy lµm cho viÖc ®äc ch−¬ng tr×nh dÔ dµng. TÝnh râ rµng cña thuËt to¸n, viÖc tiÕt kiÖm sè c¸c thao t¸c, tÝnh ng¾n gän cña ch−¬ng tr×nh ®−îc cho thªm ®iÓm, cßn viÖc lËp tr×nh sö dông m¶ng thõa vµ cã lçi bÞ h¹ thÊp ®iÓm. Trong ph¸t biÓu c¸c bµi to¸n vµ tr×nh bµy thuËt to¸n qui −íc dïng c¸c ký hiÖu sau ®©y: C¸c m¶ng A1, A2,..An ®−îc ký hiÖu lµ A[1:n] víi A[i] lµ c¸c phÇn tö cña nã. Còng nh− vËy kÝ hiÖu A[1:m,1:n] vµ A[i,j] cho m¶ng hai chiÒu..v.v... Sè l−îng c¸c phÇn tö cña m¶ng vµ chØ sè c¸c phÇn tö cña m¶ng lµ c¸c sè tù nhiªn, cßn l¹i lµ c¸c sè thùc ( nghÜa lµ sè víi dÊu phÈy ®éng), nÕu kh«ng cã −íc ®Þnh nµo kh¸c. NÕu ë ®Çu bµi nãi r»ng “ Cho m¶ng A[1:n] th× häc sinh cÇn viÕt ch−¬ng tr×nh tù nhËp sè n, t¹o m¶ng n phÇn tö vµ nhËp gi¸ trÞ cña c¸c phÇn tö nµy. NÕu trong ng«n ng÷ ( VÝ dô ng«n ng÷ Pascal...) kh«ng cã m¶ng ®éng, th× cÇn chÊp nhËn n
VIETBOOK 80.2.2 Tæng b×nh ph−¬ng Cã thÓ viÕt sè tù nhiªn M cho tr−íc d−íi d¹ng tæng c¸c b×nh ph−¬ng cña hai sè tù nhiªn hay kh«ng ? H·y viÕt ch−¬ng tr×nh gi¶i bµi to¸n nµy. 80.2.3 C¸c sè kh¸c nhau Cho tr−íc m¶ng sè A[1:m]. T×m vµ in ra sè c¸c sè kh¸c nhau trong m¶ng nµy. VÝ dô trong m¶ng 5,7,5 cã hai sè kh¸c nhau ( 5 vµ 7 ). 80.3.1 Sè cã tæng c¸c ch÷ sè cho tr−íc ViÕt ch−¬ng tr×nh in ra tÊt c¶ c¸c sè ë hÖ c¬ sè 10 cã ba ch÷ sè mµ tæng c¸c ch÷ sè b»ng mét sè tù nhiªn cho tr−íc. 80.3.2 M + 1 ë hÖ nhÞ ph©n Sè nguyªn kh«ng ©m M ®−îc cho bëi m¶ng c¸c ch÷ sè nhÞ ph©n lµ a0, a1, a2,...an-1 : M = an- n-1 .2 1 +......+ a1.2 + a0 Trong ®ã ai b»ng 0 hoÆc 1 ( i = 0,1,2,...n-1 ) H·y viÕt m¶ng c¸c ch÷ sè nhÞ ph©n cña M+1. 80.3.3 Cùc ®¹i cña c¸c cùc tiÓu : Trong m¶ng X[1:m,1:n] tÊt c¶ c¸c sè kh¸c nhau. ë mçi dßng t×m mét phÇn tö nhá nhÊt, sau ®ã trong sè nµy chän ra sè lín nhÊt. H·y in ra chØ sè cña dßng cña m¶ng X chøa sè ®· ®−îc chän. 80.3.4. Ho¸n vÞ 0, 1, 2. Trong m¶ng X[1:n] mçi phÇn tö b»ng 0, 1 hoÆc 2. Ho¸n vÞ c¸c phÇn tö cña m¶ng, sao cho ®Çu m¶ng chøa c¸c sè 0, sau ®ã lµ c¸c sè 1 vµ cuèi m¶ng lµ c¸c sè 2 ( kh«ng ®−îc dïng m¶ng phô ). Olimpic 81 C¸c thÝ sinh ®−îc giao 5 bµi to¸n s¾p xÕp theo thø tù dÔ dÇn. ChØ ®−îc tÝnh ®iÓm 3 bµi. 81.1 Hµm sè : Hµm sè f(n) víi c¸c sè n nguyªn kh«ng ©m ®−îc x¸c ®Þnh nh− sau : f(0) = 0 , f(1) = 1 , f(2n) = f(n) , f(2n+1) = f(n) + f(n+1). Víi N cho tr−íc x¸c ®Þnh vµ in ra f(N). §iÒu kiÖn b¾t buéc : N ®ñ lín ®Ó kh«ng thÓ m¶ng gåm N phÇn tö ( hoÆc khai b¸o m¶ng cã chiÒu dµi t¨ng theo N ). 81.2. CÆp bèn sè . H·y n¹p sè n vµ lÊp ®Çy m¶ng hai chiÒu kÝch th−íc n2 b»ng c¸c sè 1, 2, 3,.. theo h×nh xo¾n èc ( h×nh vÏ ). 81.3. C¸c sè lËp tõ c¸c ch÷ sè kh¸c nhau: In ra tÊt c¶ c¸c sè tù nhiªn cã 4 ch÷ sè mµ biÓu diÔn ë hÖ thËp ph©n cña chóng kh«ng cã hai ch÷ sè nµo gièng nhau. 81.5 Lo¹t c¸c sè kh«ng. Trang 2
VIETBOOK Cho m¶ng sè A[1:n] . H·y t×m ®é dµi cña d·y con lín nhÊt gåm c¸c phÇn tö liªn tiÕp toµn sè kh«ng. Olimpic 82 C¸c thÝ sinh ®−îc giao 6 bµi to¸n theo trËt tù dÔ dÇn. ChØ tÝnh ®iÓm 3 bµi. 82.1 H×nh ch÷ nhËt . Trªn giÊy kÎ « khæ 100 x 100 «, cã vÏ mét sè h×nh ch÷ nhËt. Mçi h×nh ch÷ nhËt ®−îc t¹o tõ c¸c « nguyªn vÑn, c¸c h×nh kh¸c nhau kh«ng chång lªn nhau vµ kh«ng tiÕp xóc nhau. ( h×nh 1.2 ) Cho m¶ng kÝch th−íc 100 x 100, trong ®ã phÇn tö A[i,j] = 1 nÕu « [i,j] thuéc mét h×nh ch÷ nhËt nµo ®ã, cßn A[i,j] = 0 trong tr−êng hîp ng−îc l¹i. H·y viÕt ch−¬ng tr×nh tÝnh vµ in ra sè c¸c h×nh ch÷ nhËt. 82.2 C¸c ph©n sè ®−îc s¾p thø tù In theo trËt tù t¨ng dÇn tÊt c¶ c¸c ph©n sè tèi gi¶n trong kho¶ng (0, 1) cã c¸c mÉu sè kh«ng v−ît qu¸ 7. 82.3 Tæng theo tËp con : Cho tr−íc m¶ng sè nguyªn A[1: n] vµ sè M . T×m tËp hîp c¸c phÇn tö A[i1], A[i2], ......A[ik] 1
VIETBOOK Olimpic 83 C¸c thÝ sinh ®−îc giao 5 bµi theo trËt tù dÔ dÇn. ChØ cã 3 bµi ®−îc tÝnh ®iÓm. 83.1. §¶o bit : Sè nguyªn m ®−îc viÕt trong hÖ c¬ sè 2 theo trËt tù ng−îc l¹i. Sè nhËn ®−îc viÕt trong hÖ thËp ph©n, ®−îc coi lµ gi¸ trÞ cña hµm B(m). H·y in gi¸ trÞ B(m) víi m=512,513,514,...1023. ThÝ dô, ba gi¸ trÞ ®Çu tiªn cÇn in lµ : 1; 513; 257;... 83.2. H×nh tam gi¸c vµ ®iÓm : Cho tr−íc trong hÖ to¹ ®é vu«ng gãc c¸c ®iÓm (X1,Y1), (X2,Y2),(X3,Y3) lµ ®Ønh cña mét tam gi¸c vµ X,Y lµ to¹ ®é cña mét ®iÓm. H·y x¸c ®Þnh xem ®iÓm ®ã cã n»m trong tam gi¸c hay kh«ng ( bá qua sai sè cña phÐp tÝnh) 83.3. Mª cung : Du kh¸ch cã thÓ ra khái mª cung ®−îc hay kh«ng ? NÕu cã thÓ h·y in ®−êng ®i tõ lèi ra ®Õn vÞ trÝ ban ®Çu cña du kh¸ch. Mª cung ®−îc cho bëi m¶ng A kÝch th−íc 40 x 40, trong ®ã : A[k,m] = 0 , nÕu « [k,m] ®i qua ®−îc (« th«ng) A[k,m] = 1 , nÕu « [k,m] kh«ng ®i qua ®−îc (« cÊm). VÞ trÝ ban ®Çu cña du kh¸ch ®−îc cho ë « th«ng [i,j]. Du kh¸ch cã thÓ chuyÓn tõ mét « th«ng nµy ®Õn « th«ng kh¸c nÕu chóng cã chung c¹nh. Du kh¸ch ®i ra khái mª cung nÕu r¬i vµo « biªn giíi ( tøc lµ « [k,m], trong ®ã k hoÆc m b»ng 1 hoÆc 40 ). 83.4. C¸i c−a : Cho tr−íc m¶ng X[1:m]. H·y t×m ®é dµi lín nhÊt cña d·y liªn tiÕp c¸c sè “h×nh c−a” (cã r¨ng h−íng lªn trªn ) X[p+1] < X[p+2] > X[p+3]X[p+k]. 83.5. Rót gän ph©n sè : Cho tr−íc c¸c sè tù nhiªn m vµ n . H·y t×m c¸c sè m1, n1 nguyªn tè cïng nhau vµ m/n = m1/n1. Olimpic 84 C¸c thÝ sinh ®−îc giao 7 bµi theo trËt tù dÔ dÇn. ChØ tÝnh ®iÓm 3 bµi. 84.1 NghÞch thÕ. Gi¶ sö P = (p1,....,pn) lµ mét ho¸n vÞ cña c¸c sè 1,2,...,n. Ng−êi ta gäi d·y T = (t1....tn) lµ b¶ng nghÞch thÕ cña phÐp ho¸n vÞ P, nÕu ti lµ sè l−îng c¸c phÇn tö cña phÐp ho¸n vÞ P, n»m ë phÝa tr¸i i vµ lín h¬n i. VÝ dô, ®èi víi phÐp ho¸n vÞ P = (5,9,1,8,2,6,4,7,3) cña c¸c sè 1,2,...,9 th× b¶ng nghÞch thÕ sÏ lµ T = (2,3,6,4,0,2,2,1,0). H·y viÕt ch−¬ng tr×nh sao cho theo b¶ng nghÞch thÕ cho tr−íc phôc håi ®−îc ho¸n vÞ ban ®Çu. 84.2 Con ®−êng: Cho tr−íc c¸c sè tù nhiªn n>=2 vµ m¶ng c¸c sè thùc A[1 : m,1: m,1: n-1]. H·y t×m gi¸ trÞ nhá nhÊt cña tæng [ R= A]i1,i2,1]+ A[i2,i3,2] + ...... + A[in-1,in,in-1] víi c¸c bé sè nguyªn tè cã thÓ cã 1
VIETBOOK Chó ý : Gi¸ trÞ c¸c sè m, n kho¶ng vµi chôc, v× thÕ kh«ng chÊp nhËn lêi gi¶i víi sè thao t¸c mn 84.3. Nh÷ng sè hoµn thiÖn. Sè tù nhiªn ®−îc gäi lµ hoµn thiÖn, nÕu nã b»ng tæng tÊt c¶ c¸c −íc sè cña nã, kÓ c¶ 1. H·y in tÊt c¶ c¸c sè hoµn thiÖn nhá h¬n sè N cho tr−íc. 84.4 Chu k× cña ph©n sè : N¹p c¸c sè tù nhiªn m vµ n råi in chu k× cña ph©n sè m/n. VÝ dô : ®èi víi ph©n sè 1/7 sÏ cã chu k× ( 142857 ). NÕu ph©n sè h÷u h¹n th× chu k× b»ng 0. 84.5 Trén c¸c m¶ng : Cho tr−íc hai sè m, n vµ hai m¶ng ®· ®−îc s¾p A[1]
VIETBOOK Cã thÓ ®Æt khÝt c¸c tø diÖn sao cho trªn c¸c mÆt trïng nhau cã c¸c sè nh− nhau hay kh«ng ? H·y in Cã hoÆc Kh«ng t−¬ng øng víi c¸c tr¶ lêi t×m ®−îc. 85.5. Mèt. T×m sè xuÊt hiÖn nhiÒu lÇn nhÊt trong m¶ng sè nguyªn A[1:n]. NÕu cã vµi sè nh− vËy th× lÊy mét sè. 85.6. HÖ ®Õm. Trong m¶ng M[1:9] cã viÕt c¸c ch÷ sè cña mét sè tù nhiªn trong hÖ ®Õm I. ( M[1] lµ sè hµng ®¬n vÞ,...v.v). In c¸c ch÷ sè nµy trong hÖ ®Õm J, b¾t ®Çu tõ hµng ®¬n vÞ. C¸c sè I, J kh«ng v−ît qu¸ 10. 85.7. §−êng chÐo phô. T×m tæng c¸c phÇn tö A(i,j) cña m¶ng A[1:m,1:n], cã hiÖu c¸c chØ sè lµ i-j=k. Chó ý : k cã thÓ lµ sè ©m. Olimpic 86 ThÝ sinh ®−îc giao 5 bµi theo trËt tù dÔ dÇn. ChØ tÝnh ®iÓm 3 bµi. 86.1. Kh«ng lÆp 3 lÇn . H·y t×m d·y 50 sè 0 vµ sè 1, trong ®ã kh«ng cã d·y con lÆp l¹i 3 lÇn liªn tôc. H·y in Kh«ng nÕu d·y nh− kh«ng tån t¹i. VÜ dô : trong d·y t×m ®−îc kh«ng chøa c¸c ®o¹n 000 hoÆc 101010, hoÆc 101101101. 86.2. Bµi P«-C¬. Cho m¶ng gåm 5 sè, trong ®ã : - NÕu 5 sè gièng nhau, th× in sè 1, nÕu kh«ng - NÕu cã 4 sè gièng nhau, th× in sè 2, nÕu kh«ng - NÕu cã 3 sè gièng nhau vµ cßn 2 sè cßn l¹i còng gièng nhau, th× in sè 3, nÕu kh«ng - NÕu chØ cã 3 sè gièng nhau, th× in sè 4, nÕu kh«ng - NÕu cã 1 cÆp sè gièng nhau th× in sè 6, nÕu kh«ng th× in sè 7. 86.3. C¸i trèng. Theo h×nh trßn viÕt 12 sè a1,...., a12. NÕu viÕt chóng tõ sè hiÖu k, th× nhËn ®−îc vec t¬ xk = (ak, ak+1,...., ak+11) Trong ®ã a13 ®−îc hiÓu lµ a1, a14 ®−îc hiÓu lµ a2.... Vec t¬ xk ®−îc coi lµ nhá h¬n xp, nÕu cÆp sè ®Çu tiªn kh«ng b»ng nhau sÏ lµ ak+i < ap+i 86.4. TÝnh ®¬n ®iÖu kÐp. M¶ng sè A[1:m,1:n] ®−îc s¾p theo dßng nh− sau : A[i,1]
VIETBOOK 86.5. Lµng trung t©m . Cã k lµng. NÕu ë lµng i ®Æt tr¹m cÊp cøu, th× xe cÊp cøu ®i ®Õn lµng j theo tÝn hiÖu gäi cÇn thêi gian : A[i,i] + A[i,j] [ 1
VIETBOOK 88.1. Lín bªn ph¶i. Cho tr−íc m¶ng sè d−¬ng A[1:n]. §èi víi mäi phÇn tö A[i] h·y chän trong sè c¸c phÇn tö vÒ bªn ph¶i A[i] vµ lín h¬n A[i] chØ sè nhá nhÊt j råi thay gi¸ trÞ A[i] b»ng A[j]. NÕu kh«ng t×m ®−îc phÇn tö A[j] nh− vËy th× thay thÕ A[i] b»ng 0. In l¹i m¶ng ®· nhËn ®−îc. §iÒu kiÖn b¾t buéc : sè phÐp tÝnh ë lêi gi¶i cÇn ph¶i lµ O(n) chø kh«ng ph¶i lµ O(n2). Cã thÓ sö dông m¶ng phô. Gi¶i thÝch : VÝ dô m¶ng 2,9,8,5,9,3,4,5,2, sai khi thay trë thµnh m¶ng 9,0,9,9,0,4,5,0,0. 88.2. §a thøc. TÝnh c¸c hÖ sè a[0], a[1], ...., a[n-1] cña ®a thøc P(x) = a[0] + a[1]*x + a[2]*x2 +.....+ a[n-1]*xn-1 + xn Víi c¸c nghiÖm thùc cho tr−íc x[1], x[2],.....x[n]. Gîi ý : Theo ®Þnh lý B¬ Du : P(x) = (x - x[1]) * (x - x[2]) * .........* (x - x[n]). 88.3. ¦íc sè nguyªn tè : Cho tr−íc sè tù nhiªn N. H·y t×m tÊt c¶ c¸c −íc sè nguyªn tè cña nã. 88.4. Hµng mua bu«n. Mét ®«i tÊt ng¾n gi¸ 1,05 róp, mét bã tÊt ( 12 ®«i ) gi¸ 10,25 róp, cßn 1 hép ( 12 bã ) gi¸ 114 róp. LËp ch−¬ng tr×nh sao cho øng víi n ®«i tÊt cÇn mua, tÝnh sè n1 hép tÊt, n2 bã tÊt, n3 ®«i tÊt mµ ng−êi ®ã cÇn mua cho ®ì tèn tiÒn nhÊt . Gi¶i thÝch : Thay viÖc mua 11 ®«i tÊt cÇn mua b»ng mua mét bã tÊt ®ì tèn tiÒn h¬n. 88.5 §−a vÒ b»ng 0 : Trong mét m¶ng 2 chiÒu cho tr−íc A[1:n, 1:n], h·y thay thÕ tÊt c¶ c¸c phÇn tö ë hµng hoÆc cét cã ch÷ sè 0 b»ng 0. §iÒu kiÖn : Cã thÓ ®−a vµo m¶ng phô mét chiÒu nh−ng kh«ng ®−îc dïng m¶ng phô 2 chiÒu. Trang 8
VIETBOOK PhÇn hai - ThuËt to¸n Trong phÇn nµy tr×nh bµy c¸c thuËt gi¶i. Víi mét sè bµi thuËt gi¶i ®−îc tr×nh bµy cã thÓ dÔ dµng chuyÓn sang ch−¬ng tr×nh, víi mét sè bµi kh¸c ®ã míi chØ lµ ý t−ëng gi¶i, cã lóc lµ chó gi¶i, gi¶i thÝch ch−¬ng tr×nh. Nh−ng trong mäi tr−êng hîp chóng t«i cè g¾ng lµm cho viÖc ®äc ch−¬ng tr×nh ®−îc dÔ dµng, tr×nh bµy ph−¬ng ph¸p lËp tr×nh ®óng ®−îc ghi nhí. Sè l−îng c¸c phÐp to¸n cña thuËt gi¶i chÝnh x¸c ®Õn mét béi h»ng. «limpic 80 80.1.1. Nh÷ng sè nguyªn tè ®Õn M : §Ó t¨ng tèc ®é tÝnh to¸n ta nªn dïng mét m¶ng chøa nh÷ng sè nguyªn tè thu ®−îc vµ kiÓm tra xem sè ®ang xÐt chia hÕt cña phÇn tö ®· n¹p trong b¶ng hay ch−a. Sè ch½n hiÓn nhiªn kh«ng ph¶i xÐt. B¶ng cÇn cã kÝch th−íc tèi ®a lµ phÇn tö. V× thÕ nh÷ng b¶ng 1000 phÇn tö sÏ ®ñ ®Ó chøa nh÷ng sè nguyªn tè ®Õn 4.000.000. 80.1.2. Ho¸n vÞ : §Æc tr−ng cña bµi to¸n bµi lµ ë chç, cÇn thu ®−îc tÊt c¶ c¸c ho¸n vÞ. §iÒu nµy sÏ lµm gi¶m ®¸ng kÓ sè l−îng thao t¸c so víi bµi to¸n chän toµn bé. Tuy nhiªn thö t−ëng t−îng lµ toµn bé c¸c ho¸n vÞ cña c¸c sè 1,2,3,............m ®−îc s¾p xÕp theo trËt tù tõ ®iÓn ®Ó t×m c¸ch ®−a vµo mét ho¸n vÞ x©y dùng c¸c ho¸n vÞ tiÕp theo b»ng c¸ch, xuÊt ph¸t tõ ho¸n vÞ ®Çu tiªn x©y dùng c¸c ho¸n vÞ tiÕp theo. Cô thÓ lµ víi mçi ho¸n vÞ P = ( p1,p2,........,pm ) cña c¸c sè 1,2,......,m, chóng ta còng lµm phÐp ®æi chç nh− vËy (A(p1),A(p2),.....,A(pm)) cña nh÷ng sè A cho tr−íc. §Ó x©y dùng trùc tiÕp ho¸n vÞ tiÕp theo ho¸n vÞ cho tr−íc P = ( p1, p2,......,pm ) chóng ta duyÖt c¸c sè p1, p2,...,pm tõ phÝa cuèi vµ dõng l¹i khi gÆp ®−îc thµnh phÇn p1 ®Çu tiªn nhá h¬n thµnh phÇn thµnh phÇn ®øng bªn ph¶i nã ( p1 < pi+1). NÕu kh«ng cã thµnh phÇn nh− vËy, th× ho¸n vÞ P cã d¹ng (m,m-1,...,1) nghÜa lµ ho¸n vÞ cuèi cïng. Râ rµng r»ng c¸c thµnh phÇn pi+1 > pi+2 >...> pm t¹o c¸c d·y gi¶m dÇn. Chóng ta t×m trong sè ®ã thµnh phÇn ®Çu tiªn pj ( tÝnh tõ cuèi ), lín h¬n pi, vµ ®æi chç chóng cho nhau. ViÖc cßn l¹i lµ s¾p xÕp c¸c phÇn tö pi+1, pi+2,..., pm theo trËt tù t¨ng dÇn, ho¸n vÞ t×m ®−îc Q = (q1, q2,....., qm ) sÏ lµ ho¸n vÞ cÇn t×m ®−îc. H×nh vÏ 1.4 ThËt vËy, P < Q bëi v× (i-1) thµnh phÇn ®Çu tiªn cña chóng trïng nhau vµ p1pi ). Trong i thµnh phÇn ®Çu tiªn P lµ lín nhÊt, cßn Q nhá nhÊt, bëi v× trong P c¸c thµnh phÇn gi¶m dÇn , cßn Q - t¨ng dÇn. Cuèi cïng nÕu ho¸n vÞ R n»m gi÷a P vµ Q, th× i -1 thµnh phÇn ®Çu tiªn cña nã trïng víi c¸c thµnh phÇn P vµ Q, cßn thµnh phÇn ri = p1 hay qi, bëi v× trong i-1 thµnh phÇn ®Çu tiªn ®· chiÕm chç kh«ng cã nh÷ng sè n»m gi÷a pi vµ qi. NÕu pi = ri vµ P nhá h¬n hoÆc b»ng R th× P=R (bëi v× P lín nhÊt víi c¸c phÇn tö p1, p2,...,pi cho tr−íc ) vµ nÕu ri=qi th× t−¬ng tù ta cã R = Q. Trang 9
VIETBOOK Trong ch−¬ng tr×nh ®iÒu nµy ®−îc thùc hiÖn nh− sau : Ta dïng m¶ng P chøa c¸c ho¸n vÞ hiÖn t¹i. Tr−íc tiªn lÊp dÇn bëi ho¸n vÞ ®Çu tiªn cña chóng P=(1,2,....,m) vµ g¾n ho¸n vÞ ®ång nhÊt (a1, a2,...,am) cña c¸c thµnh phÇn cña m¶ng A cho tr−íc. Gi¶ sö ho¸n vÞ P nhËn ®−îc vµ ho¸n vÞ ®¸p øng nã A ®−îc in. Trong phÇn t−¬ng øng cña ch−¬ng tr×nh sÏ t×m phÇn tö pi < pi+1 víi chØ sè lín nhÊt i. NÕu kh«ng cã i ®ã, th× ho¸n vÞ P lµ cuèi cïng. NÕu cã i ta sÏ t×m chØ sè lín nhÊt j > i mµ pi < pj, råi ®æi chç pi vµ pj, sau ®ã d·y pi+1, pi+2,..., pm trËt tù thay ®æi theo chiÒu ng−îc l¹i: ®Ó cã trËt tù nµy ng−êi ta ®æi chç Pi+1vµ Pm, Pi+2vµ Pm-1,.... Tíi ®©y viÖc nhËn ®−îc ho¸n vÞ P tiÕp theo ®−îc kÕt thóc vµ ho¸n vÞ ®¸p øng cña nã cña m¶ng A ®−îc in ra. Bµi to¸n vÒ ho¸n vÞ trë nªn khã h¬n nÕu ®ßi hái ho¸n vÞ tiÕp theo nhËn ®−îc tõ ho¸n vÞ tr−íc ®ã b»ng c¸ch ®æi chç hai phÇn tö c¹nh nhau. Bµi to¸n nh− trªn ®−îc gi¶i ë ch−¬ng tr×nh 80.1.2-2. Ch−¬ng tr×nh ng¾n nh−ng phøc t¹p. B¹n ®äc h·y tù t×m hiÓu theo b¶ng ho¸n vÞ, mµ ch−¬ng tr×nh in ra víi m = 4. 1 2 3 4 1 3 4 2 1 4 2 3 2 1 3 4 3 1 4 2 4 1 2 3 2 3 1 4 3 4 1 2 4 2 1 3 2 3 4 1 3 4 2 1 4 2 3 1 3 2 1 4 4 3 2 1 2 4 3 1 3 1 2 4 4 1 3 2 2 1 4 3 1 3 2 4 1 4 3 2 1 2 3 4 80.1.3. N©ng luü thõa nhanh B×nh th−êng ®Ó tÝnh ak ng−êi ta ®−a vµo biÕn sè b, ban ®Çu g¸n b:=1 råi thùc hiÖn nhiÒu lÇn c¸c phÐp to¸n : k:=k-1; B:=b*a . Trang 10
VIETBOOK Khi biÕn cè k trë thµnh 0 (®iÒu nµy ®ßi hái k vßng) ta sÏ cã b=ak ý t−ëng lµm gän c¸ch tÝnh lµ nh− sau . Ban ®Çu ta ®Æt b=1. NÕu k lÎ , ta thùc hiÖn phÐp to¸n : K:=k-1, b:=b*a NÕu k ch½n, ta sö dông ®ång nhÊt thøc : Ak = ( a2 )k/2 ®Ó biÕn ®æi : k:=k/2 ; a := a*a khi k = 0 , biÕn b sÏ chøa gi¸ trÞ ph¶i t×m • §Ó chøng minh ta lÝ hiÖu gi¸ trÞ cÇn t×m ak lµ w vµ ®Æt b=1, khi ®ã ak * b = w (*) • NÕu k lÎ, th× c¸c phÐp thÕ : k = k-1 , b = b*a kh«ng ph¸ vì dÊu ®¼ng thøc (*). NÕu k ch½n th× c¸c phÐp thÕ k = k/2, a = a*2 còng kh«ng ph¸ vì, nghÜa lµ b = w. VËy b lµ gi¸ trÞ cÇn t×m. 80.1.4. C¸c phÐp tÝnh sè häc : Bµi to¸n nµy còng lµ sù thµnh lËp tÊt c¶ c¸c ho¸n vÞ. §iÓm kh¸c biÖt ë ®©y lµ cã sù lÆp l¹i. Ta viÕt biÓu thøc cho tr−íc ë d¹ng : w = ((((( 1 a2 2) a3 3) a4 4) a5 5 ) a6 6. Trong ®ã c¸c phÇn tö cña m¶ng a[2:6] biÓu thÞ dÊu c¸c phÐp tÝnh sè häc. Ta qui −íc c¸c dÊu +, -, *, / ®−îc biÓu thÞ qua c¸c gi¸ trÞ 1, 2, 3, 4. V× cã thÓ cã nhiÒu kh¶ n¨ng ( 46 >1000 ) nªn chóng ta cè g¾ng tæ chøc phÐp to¸n mét c¸ch tiÕt kiÖm. §Ó lµm ®iÒu nµy khi tÝnh w chóng ta sÏ ghi c¸c kÕt qu¶ trung gian vµo m¶ng B[1:6], theo qui ®Þnh B1=1, B2=B1 a2 2,....,B6=B6 a6 6 vµ w = B6 TiÕp theo khi lùa chän c¸c kh¶ n¨ng, ta sÏ cho a6 biÕn thiªn dÇn theo 1, 2, 3, 4 vµ v.v.... ThuËt to¸n nµy ®−îc thÓ hiÖn trong ch−¬ng tr×nh 80.1.4. Chóng ta gi¶i thÝch mét sè ý trong ph−¬ng ¸n BASIC nã ë ng«n ng÷ Basic. C¸c biÕn m vµ n biÓu thÞ cho c¸c sè 35 vµ 6. Nh÷ng dßng ®Çu tiªn cña ch−¬ng tr×nh (®Õn dßng sè 60) tèt nhÊt. C¸c dßng ®ã lµm c«ng viÖc khëi ®éng ®Ó c¸c to¸n tö b¾t ®Çu tõ dßng sè 60 vµ c¸c to¸n tö dïng cho sù lùa chän ph−¬ng ¸n kÕ tiÕp, khëi trÞ cho ph−¬ng ¸n ®Çu tiªn. Chóng ta xem ch−¬ng tr×nh tõ dßng sè 60. Sè h¹ng ®Çu tiªn ai ®−îc chän tõ d·y an, an-1,...,a2 kh«ng b»ng 4. Nã t¨ng lªn 1 cßn tÊt c¶ nh÷ng sè h¹ng tr−íc nã ®−îc g¸n lµ 1. B©y giê Bi ®−îc tÝnh theo Bi-1 vµ sau ®ã tÊt c¶ c¸c thµnh phÇn cßn l¹i Bi+1, Bi+2,...,Bn. PhÇn viÖc thø hai kh«ng phøc t¹p l¾m bëi c¸c aj t−¬ng øng b»ng 1, nghÜa lµ chóng biÓu thÞ phÐp (+). Nªn Bn kh¸c th× gi¸ trÞ w lµ kh«ng cho tr−íc vµ ch−¬ng tr×nh chuyÓn sang sang dßng 60 ®Ó xÐt kh¶ n¨ng tiÕp theo. NÕu Bn=m th× ch−¬ng tr×nh còng chuyÓn sang dßng 60 nh−ng cã in ra mét kh¶ n¨ng ®· t×m ®−îc. Trong c¸c ch−¬ng tr×nh kh¸c 80.1.4 c¸c kÝ hiÖu cã kh¸c nhau : trong Pascal vµ C vai trß dßng sè 60 do nh·n R ®¶m nhiÖm, cßn trong Fotran th× do nh·n 2 ®¶m nhiÖm. 80.2.1. T×m c¸c phÇn tö b»ng nhau . §Ó cã lêi gi¶i chÊp nhËn ®−îc cho bµi to¸n nµy cÇn ph¶i tr¸nh kh«ng chän c¸c cÆp phÇn tö A[i,j] vµ A[p,q] hai lÇn vµ kh«ng ®−îc lÉn lén trong c¸c tr−êng hîp khi i = p vµ j = q. Trong ch−¬ng tr×nh Fotran c¸c khã kh¨n nãi trªn nµy ®−îc kh¾c phôc qua viÖc chuyÓn ®Õn m¶ng mét chiÒu víi sù gióp ®ì cña to¸n tö EQUIALENCE. 80.2.2. Tæng c¸c b×nh ph−¬ng . Ch−¬ng tr×nh kh¸ dÔ ®äc. Trang 11
VIETBOOK Bµi to¸n nµy cã thÓ gi¶i kh«ng ph¶i nhê ®Õn hµm lÊy c¨n bËc hai. Gi¶i dùa trªn ý t−ëng chØ ra trong ch−¬ng tr×nh 87.3. B¹n ®äc tù t×m hiÓu ch−¬ng tr×nh nµy, cã thÓ xem l¹i bµi 80.2.2 vµ dÔ dµng kh«i phôc c¸c chi tiÕt. 80.2.3. C¸c sè kh¸c nhau : Ch−¬ng tr×nh 80.2.3. dÔ ®äc. Nh−ng cã thÓ ®Èy nhanh tèc ®é thùc hiÖn nã, khi so s¸nh c¸c phÇn tö thö nghiÖm kh«ng ph¶i víi c¸c phÇn tö tr−íc ®ã mµ víi c¸c phÇn tö sau nã, ®Õn khi gÆp sù trïng ®Çu tiªn. Sè lÇn do ®ã sÏ gi¶m tõ m*n ®Ôn m*k, víi m lµ sè l−îng c¸c sè, cßn k lµ sè c¸c sè kh¸c nhau trong m¶ng cho tr−íc. Ch−¬ng tr×nh 80.2.3-2 thùc hiÖn ®iÒu ®ã. 80.3.1. Tæng cho tr−íc c¸c ch÷ sè . TÊt nhiªn lµ cã thÓ dïng 3 vßng FOR lång nhau : FOR i:=0 to 9 do FOR j:=0 to 9 do FOR k:=1 to 9 do If i+j+k = n then WRITELN ( i+10*j + 100*k ); Tuy nhiªn lêi gi¶i nµy lµ tåi v× nã chøa 900 vßng lÆp trong khi ®ã chØ cÇn 100 lµ ®ñ. Lêi gi¶i tèt h¬n chøa ®ùng vßng lÆp kÐp theo i vµ j cßn k tÝnh theo tæng cho n: k=n-i-j. Thªm vµo sù kiÓm tra 1
VIETBOOK §Ó chøng minh ®iÒu nµy - ®ång thêi cho bªn c¹nh hµm sè mét biÕn cho tr−íc f(n) chóng ta xÐt thªm hµm : g(n,i,j) = if(n) + jf(n+1) , 3 ®èi sè n, i, j Ta dÔ dµng kiÓm tra c«ng thøc truy håi : g(2n,i,j) = g(n,i+j,j); g(2n+1,i,j) = g(n,i,i+j) Khi ®ã gi¸ trÞ cÇn t×m f(n) cã thÓ viÕt d−íi d¹ng : f(n) = g(n,1,0) B»ng c¸ch sö dông nhiÒu lÇn c«ng thøc truy håi ta cã thÓ lµm cho ®èi sè ®Çu tiªn cña hµm sè g b»ng 0 vµ nhËn ®−îc : f(n) = g(n,1,0) =.......=g(0,i,j) = j C«ng viÖc cßn l¹i chØ lµ h×nh thøc qua diÔn ®¹t ng«n ng÷ mµ lËp tr×nh tuú chän. 81.2 CÆp bèn Bµi to¸n nµy chøa mét bÉy nhá bëi v× thay viÖc t×m sè nhá nhÊt víi tÝnh chÊt cÇn cã ta cã thÓ t×m sè ®Çu tiªn trong qu¸ tr×nh lùa chän c¸c sè h¹ng. B¹n ®äc cã thÓ t¨ng tèc ®é ch−¬ng tr×nh Basic, Pascal, vµ C nÕu ®Ó ý r»ng víi sè cÇn t×m cã 2 d¹ng biÓu diÔn ( cña tæng b×nh ph−¬ng) kh¸c nhau ë sè h¹ng lín nhÊt. 81.3 H×nh xo¸y èc Chóng ta chia vßng xo¸y èc thµnh 4 phÇn : ®o¹n ngang tõ ph¶i sang tr¸i vµ ®o¹n th¼ng ®øng tõ trªn xuèng, ®o¹n ngang tõ ph¶i sang tr¸i vµ ®o¹n th¼ng ®øng tõ d−íi lªn trªn. Trong ch−¬ng tr×nh mçi ®o¹n ®−îc xö lý riªng vµ ®−îc nèi kÕt víi ®o¹n kh¸c. Ch−¬ng tr×nh kÕt thóc sau khi ®· n¹p phÇn tö cuèi cïng k= n*n 81.4. C¸c sè lËp tõ c¸c ch÷ sè kh¸c nhau Ch−¬ng tr×nh 81.4. kh¸ râ rµng 81.5. Ch−¬ng tr×nh 81.5 ®¬n gi¶n. olimpic 82 82.1.H×nh ch÷ nhËt Ta nhËn thÊy sè l−îng h×nh ch÷ nhËt chÝnh lµ sè l−îng c¸c gãc t©y – b¾c tøc lµ gãc tr¸i trªn cña chóng. ChØ cÇn kh«ng nhÇm lÉn trong tr−êng hîp gãc ë trªn biªn . C¸c ch−¬ng tr×nh 82.1 vµ 82.1-2 kh¾c phôc khã kh¨n trªn theo hai c¸ch kh¸c nhau. L−u ý b¹n ®äc nµo muèn lµm rót gän ch−¬ng tr×nh 82.1, b»ng viÖc sö dông biÓu thøc ( i > 1 and A[i-1,j] = 0). BiÓu thøc cã chøa lçi có ph¸p khi i = 1 nÕu chØ sè b¾t ®Çu tõ 1. 82.2. S¾p xÕp ph©n sè Ch−¬ng tr×nh kh«ng dïng m¶ng phô vµ kh«ng ®ßi hái sù kiÓm tra tÝnh tèi gi¶n cña ph©n sè. §Ó lµm viÖc nµy ta xÐt ph©n sè m/n vµ ®Æt ban ®Çu m=0, n=1. Chóng ta in m/n, sau ®ã trong sè tÊt c¶ c¸c ph©n sè a/b, lín h¬n m/n vµ b
VIETBOOK 82.3. Tæng theo tËp con §©y lµ bµi to¸n liÖt kª tÊt c¶ c¸c tËp con cña mét tËp hîp. BÒ ngoµi nã gièng sù liÖt kª tÊt c¶ c¸c kh¶ n¨ng nh−ng ®¬n gi¶n h¬n. Cho b lµ mét sè tù nhiªn vµ bi lµ ch÷ sè biÓu diÔn theo hÖ ®Õm c¬ sè 2. B = b1 + 2b2 +.....+ 2n-1bn ( b1=0 hay b1=1). Khi b lÇn l−ît nhËn gi¸ trÞ b=1, 2,...., 2n – 1 theo c¸c bé chØ sè i cña c¸c phÇn tö bi =1 lÇn l−ît lµ c¸c tËp con ( kh«ng rçng ) cña tËp hîp ( 1, 2,....,n). V× thÕ ch−¬ng tr×nh cã mét m¶ng phô B víi c¸c phÇn tö cña nã ®−îc tham chiÕu tíi nh− lµ c¸c ch÷ sè nhÞ ph©n biÓu diÔn cho sè b. 82.4 Sè 0 ë cuèi Bµi to¸n dÔ dµng gi¶i víi viÖc sö dông 2 vßng lÆp. Vßng thø nhÊt chuyÓn c¸c phÇn tö kh¸c 0 vÒ ®Çu b¶ng, cßn vßng thø hai ®iÒn 0 vµo c¸c vÞ trÝ cßn l¹i. 82.5 §iÓm yªn ngùa NÕu Mi lµ min cña c¸c phÇn tö Aij ë dßng i, cßn Mj lµ Max cña c¸c phÇn aij ë cét j th× Mi
VIETBOOK Olimpic 83. 83.1. §¶o bit §Ó hiÓu râ ®Çu bµi chóng ta h·y viÕt ( trong b¶ng ) mét vµi gi¸ trÞ cña m vµ B (m) trong hÖ nhÞ ph©n. (Xem b¶ng) HÖ thèng 10 2 2 10 Gi¸ trÞ cña m vµ 512 1000000000 00000000001 1 B(m) 513 1000000001 10000000001 513 514 1000000010 01000000001 257 515 1000000011 11000000001 769 516 1000000100 00100000001 129 ................ ..................... .................. ............... 1023 1111111111 11111111111 1023 Chóng ta thÊy r»ng ch÷ sè hµng cao nhÊt cña m=512 trong hÖ nhÞ ph©n biÓu thÞ bëi sè 1 , vµ ch÷ sè hµng ®¬n vÞ cña sè B(m) t−¬ng øng c¸c gi¸ trÞ ®ã sÏ lµ 1. C¸c sè h¹ng sau cña d·y lµ 256 vµ 2. HÖ sè hµng cao nhÊt cña sè m lu«n lµ 1 bëi v× m>=512. Ta khö nã vµ thay thÕ b»ng sè m-512 vµ mang mét ®¬n vÞ vµo trong B(m). Trong ch÷ sè tiÕp theo, ®¬n vÞ cña sè m sÏ lµ 1 nÕu gi¸ trÞ míi cña m >=256. NÕu nã tån t¹i chóng ta khö nã vµ mang vµo trong B(m) sè 2. Chóng ta sÏ kiÓm tra sù cã mÆt cña sè 1 ë hµng tiÕp theo......§iÒu nµy dÉn ®Ôn ch−¬ng tr×nh 83.1. L−u ý r»ng vßng lÆp sÏ kÕt thóc khi m=0. Ch−¬ng tr×nh ph¶i dïng ®Õn 512*10 lÇn lÆp. Ch−¬ng tr×nh sÏ nhanh h¬n khi x©y dùng B(m+1) theo B(m). Nh×n vµo c¸ch viÕt ë hÖ nhÞ ph©n gi¸ trÞ B(m) cã thÓ h×nh dung r»ng khi x©y dùng B(m+1) cÇn ph¶i duyÖt B(m) tõ tr¸i sang ph¶i vµ thay 1 b»ng 0 ( nghÜa lµ ph¶i trõ tõ B(m) sè 512, 256,...) ®Õn sè 0 ®Çu tiªn ta ph¶i thay thÕ nã b»ng 1 vµ sÏ nhËn ®−îc sè B(m+1). Ch−¬ng tr×nh tÝnh mét nöa sè m theo mét vßng, sè 7 theo 3 vßng............TÊt c¶ sÏ Ýt h¬n 512 * 2 vßng. Ch−¬ng tr×nh 83.1-2 ®−îc x©y dùng nh− vËy. 83.2. Tam gi¸c vµ ®iÓm Chóng ta nhËn thÊy nh− sau : NÕu ®iÓm M(x,y) n»m trªn ®−êng th¼ng L12 qua M1(x1,y1) vµ M2(x2,y2) th× do sù ®ång d¹ng cña tam gi¸c ta cã : (y-y1)/(x-x1) = (y2-y1)/(x2-x1) Bá qua ®iÒu kiÖn b»ng 0 cña c¸c mÉu sè chóng ta viÕt l¹i ch−¬ng tr×nh d−íi d¹ng: F12(x,y) = (x-x1)(y2 - y1) – (x2-x1)*(y-y1) = 0 Râ rµng ®èi víi ®iÓm M(x,y) kh«ng n»m trªn ®−êng th¼ng L12 th× F12(x,y)0, h¬n n÷a dÔ kiÓm tra F12(x,y)0 ®èi víi ®iÓm n¨m bªn ph¶i L12. §iÒu ®ã cã nghÜa lµ ®iÓm M n»m trong tam gi¸c (M1,M2,M3) khi vµ chØ khi 3 sè: F12(x,y), F23(x,y), F31(x,y) NhËn ®−îc ®èi víi c¸c ®−êng th¼ng L12 = (M1------M2), L23=(M2------M3) vµ L31 = (M3------M1) cã Trang 15
VIETBOOK cïng dÊu. §Ó gi¶i bµi to¸n dÔ dµng chóng ta ®−a vµo 2 m¶ng X[1..3 ] vµ Y[1..3] ®Ó chøa c¸c to¹ ®é cña c¸c ®iÓm M1, M2, M3 vµ x¸c ®Þnh hµm : Q(i,j) = sin [(x-x[i]*(y[j]-y[i]) – (x[j]-x[i]*(y-y[i])] Gäi hµm nµy 3 lÇn chóng ta tÝnh ®−îc 3 sè t1, t2, t3 sau ®©y : t1 = Q(1,2), t2 = Q(2,3), t3 = Q(3,1) NÕu t1, t2, t3 b»ng nhau th× ®iÓm M n»m trong tam gi¸c, nÕu kh«ng th× n»m ngoµi hoÆc ë trªn c¹nh. Lêi gi¶i kh¸c cña bµi to¸n nµy dùa trªn sù so s¸nh diÖn tÝch cña tam gi¸c. Chóng ta kÝ hiÖu diÖn tÝch tam gi¸c (M1, M2, M3) lµ S, cßn S1, S2, S3 lµ diÖn tÝch c¸c tam gi¸c t¹o bëi ®iÓm M víi hai ®Ønh trong sè M1, M2, M3. NÕu S = S1 + S2 + S3 th× ®iÓm n»m trong tam gi¸c, nÕu kh«ng th× n»m ngoµi tam gi¸c. Lêi gi¶i nµy ®−îc dÉn ra ë ch−¬ng tr×nh Pascal. DiÖn tÝch tam gi¸c ®−îc tÝnh theo c«ng thøc Hª-r«ng. §iÓm ®−îc coi lµ n»m ngoµi tam gi¸c nÕu S1 + S2 + S3 > 1,000001*S. Thõa sè 1,000001 cÇn ®Ó tÝnh sai sè cña phÐp tÝnh. 83.3. Mª cung . Bµi to¸n quen thuéc nµy dÔ dµng biÕn ®æi. Lêi gi¶i chia ra lµm hai phÇn : T×m con ®−êng ®Ó ra vµ in con ®−êng “ Ng−îc l¹i “, tõ lèi ra ®Õn xuÊt ph¸t cña du kh¸ch. Lêi gi¶i ®¬n gi¶n cña phÇn thø nhÊt nh− sau : Ta viÕt ë c¸c « A[i,j], n¬i xuÊt ph¸t cña du kh¸ch sè 2 vµ ®Æt k = 2. Chóng ta xÐt tÊt c¶ c¸c « A cña mª cung. §èi víi ®ã, nÕu gÆp sè 0, th× ta xÐt bèn « liÒn kÒ « ®ã. NÕu cã Ýt nhÊt mét trong chóng chøa sè k ( lóc nµy b»ng 2 ) th× ta viÕt vµo « Êy sè k+1. B©y giê t¨ng k lªn k+1 vµ l¹i xÐt toµn thÓ c¸c « A. Qu¸ tr×nh nµy kÕt thóc khi sè ®−îc viÕt ë « giíi h¹n ( lèi ra ®· t×m ®−îc ) hoÆc sau khi ®· xÐt toµn bé c¸c « A sè ®· cho kh«ng ®−îc viÕt vµo mét « míi nµo (kh«ng cã lèi ra). Cã bao nhiªu lÇn duyÖt c¸c « th× cã bÊy nhiªu « ë trªn ®−êng ®i ng¾n nhÊt. DÔ dµng lµm tèt h¬n thuËt to¸n trªn. ë mçi b−íc ®i sÏ xem xÐt tÊt c¶ c¸c « A cña mª cung nh− tr−íc. NÕu trong mét « nµo ®ã ta gÆp sè kh«ng, cßn ë « bªn c¹nh bÊt kú cã sè k >=2 th× chóng ta viÕt vµo « A sè k+1. Râ rµng lêi gi¶i nµy lµ phÇn ®Çu cña bµi to¸n, nh−ng nÕu tr«i ch¶y, th× ë ®©y lêi gi¶i t×m ra nhanh h¬n. Ch−¬ng tr×nh sÏ hiÖu qu¶ h¬n, khi b¾t ®Çu tõ « ®Çu tiªn (n¬i b¾t ®Çu sè 2 ®−îc ghi), t×m ra « bªn c¹nh ®Çu tiªn lµ bá trèng( nghÜa lµ víi sè 0 ). Ghi vµo ®ã sè 3 vµ t×m « trèng bªn c¹nh viÕt sè 4.v.v...... Qu¸ tr×nh sÏ kÕt thóc nÕu ®¹t danh giíi ( cã lèi ra ) hoÆc kh«ng cã « trèng bªn c¹nh (« côt). NÕu « côt lµ xuÊt ph¸t (n¬i ghi sè 2)th× kh«ng cã lèi ra. NÕu « côt kh¸c « xuÊt ph¸t vµ ë ®ã ghi K >2 , th× ta viÕt vµo ®ã sè 1 ( lµm nã kh«ng ®i qua ®−îc ) vµ chuyÓn sang « bªn c¹nh « ®ã víi sè k-1. ¤ nh− vËy lµ cã vµ duy nhÊt. Lêi gi¶i tr×nh bµy ë ch−¬ng tr×nh 83.3. ë ®ã dÔ dµng nhËn ra s¬ ®å chung cña sù lùa chän c¸c t×nh huèng. Cã thÓ lµm gän h¬n n÷a ch−¬ng tr×nh ®Ó gi¶i bµi to¸n Mª cung, nÕu ta dïng kü thuËt ®Ö qui. §iÒu nµy ®−îc thùc hiÖn ë ch−¬ng tr×nh 83.3-2. Tuy nhiªn viÕt ch−¬ng tr×nh nh− thÕ dÔ h¬n lµ ®äc nã. C¸c thuËt to¸n ®· tr×nh bµy (ngoµi thuËt to¸n ®Çu tiªn) cã thÓ t×m ra con ®−êng kh«ng ng¾n nhÊt. §Ó tiÕt kiÖm t×m kiÕm con ®−êng ng¾n nhÊt trong Mª cung cã thÓ dïng thªm hai m¶ng X vµ Y ®Ó ghi nhËn to¹ ®é (x,y) cña c¸c « cÇn xÐt. Kü thuËt nµy ®−îc gäi lµ t×m kiÕm theo bÒ réng. §Çu tiªn ë X, Y ta ghi to¹ ®é cña « xuÊt ph¸t cña du kh¸ch. ë mçi b−íc, tõ m¶ng X, Y ta xÐt c¸c to¹ ®é c¸c « hiÖn cã ( víi sè hiÖu b ) cßn c¸c « tù do bªn c¹nh, theo trËt tù bÊt kú, ®−îc viÕt tiÕp vµo X, Y ( víi sè hiÖu e ). Nh− thÕ danh s¸ch sÏ ®−îc xö lý ë phÝa ®Çu vµ thªm vµo ë phÝa cuèi. Sù t×m kiÕm kÕt thóc khi t×m ®−îc « tù do ë biªn hoÆc ®· xÐt hÕt c¸c m¶ng X, Y ( khi kh«ng cã lèi ra ). ThuËt to¸n nµy ®−îc thùc hiÖn ë ch−¬ng tr×nh 83.3-3. ViÖc t×m vµ in con ®−êng ng−îc l¹i ë c¸c ch−¬ng tr×nh kh«ng ®Ö quy lµ nh− nhau, cßn ë ch−¬ng tr×nh ®Ö qui lµ tù ®éng . Trang 16
VIETBOOK 83.4. C¸i c−a . 83.5. Rót gän ph©n sè . Cã thÓ viÕt ch−¬ng tr×nh cho thuËt to¸n ¥-clit ®Ó t×m −íc sè chung lín nhÊt cña c¸c sè m, n vµ chia tö vµ mÉu cho sè nµy. §ã lµ ch−¬ng tr×nh 83.5. Chóng ta tr×nh bµy b¶n chÊt cña thuËt to¸n ¥-clit. Cho m1 > m2, −íc chung lín nhÊt ( m1, m2 ) lµ −íc sè chung cña cÆp ( m2, ( m1 - m2 ) ), do ®ã lµ −íc sè chung cña cÆp (m2, m3) víi m3 = m1 - (m1/m2) * m2 Lµ sè d− cña phÐp chia m1 cho m2, nh− thÕ hiÓn nhiªn m3 < m2. §iÒu ng−îc l¹i còng ®óng: −íc chung nµo cña (m2,m3) còng lµ −íc chung cña ( m1,m2 ). Do ®ã ( m1, m2 ) = ( m2, m3 ) LÇn l−ît thay thÕ ®èi sè lín nhÊt ë hµm USCLN (m,n) bëi sè d− cña sè lín chia cho sè nhá, chóng ta cã d·y ( m1, m2 ) = ( m2, m3 ) =.............= ( mk, 0 ) = mk trong ®ã m1 >= m2 >= m3 >=.......>= mk vµ mk sÏ lµ −íc sè chung lín nhÊt cña c¸c sè ban ®Çu m1, m2 . Tuy nhiªn nÕu n kh«ng lín ta cã thÓ trùc tiÕp chän i/j = m/n víi mÉu sè nhá nhÊt j, nghÜa lµ ph©n sè ®ã tèi gi¶n. ChØ cÇn kiÓm tra ®¼ng thøc gi÷a c¸c ph©n sè kh«ng theo quan hÖ b»ng nhau mµ theo ®¼ng thøc cña c¸c tÝch i*n = j*m. §iÒu nµy ®−îc tr×nh bµy trong ch−¬ng tr×nh 83.5-2. Chó ý r»ng ch−¬ng tr×nh 83.5-2 cã thÓ ®ßi hái n phÐp tÝnh, trong khi ®ã 83.5 lu«n cÇn bËc log2n phÐp tÝnh. Olimpic 84 84.1. NghÞch thÕ . Lµm s¹ch m¶ng P bëi sè 0. Chóng ta lÊy sè lÇn l−ît i=1, 2,..., n vµ sè T1. Chóng ta ®i theo c¸c phÇn tö P1, P2,... ®Õn khi gÆp ®−îc Ti+1 phÇn tö 0, vµ viÕt vµo phÇn tö cuèi trong chóng sè i. 84.2. Con ®−êng. Ta kh«ng thÓ duyÖt tÊt c¶ c¸c t×nh huèng i1, i2, ..., in , tÊt c¶ lµ mn Nh−ng cã thÓ gi¶i bµi to¸n b»ng ph−¬ng ph¸p qui n¹p theo k =1, 2,..., n-1. Cè ®Þnh sè k vµ k+1 ®Æt B[k,ik+1] = min (A[i1,i2,1] +....+ A[ik,ik+1,k] ë ®©y min ®−îc lÊy theo c¸c tuyÓn chän i1, i2, ...., ik. Khi ®ã dÔ thÊy : B[1, i2] = min ( A[i1, i2, 1]) víi mäi i1 B[2, i3 ] = min ( B[1,i2] + A[i2,i3,2]) víi mäi i2 ....................................................................................... B[n-1, in] = min ( B[n-2, in-1] + A[in-1, in, in-2] víi mäi in-1 Vµ t×m kiÕm : R = min B[n-1,in] víi tÊt c¶ in Nh− thÕ, ®Ó tÝnh sè B[k,ik+1] sÏ xem xÐt m kh¶ n¨ng (lùa chän ik ). §èi víi k cè ®Þnh vµ tÊt c¶ c¸c B[k,ik+1] sè c¸c kh¶ n¨ng lµ m2, cßn toµn bé bµi to¸n ®ßi hái xem xÐt Ýt h¬n m2 * n kh¶ n¨ng. 84.3. Sè hoµn thiÖn. Trang 17
VIETBOOK §Ó gi¶i quyÕt vÊn ®Ò cã hay kh«ng cã sè tù nhiªn i hoµn thiÖn cã thÓ xem xÐt tÊt c¶ c¸c sè j = 1, 2,....., i-1 xem c¸c sè nµo lµ −íc sè cña sè 1, céng nh÷ng −íc sè nµy. Nh− thÕ chóng ta sÏ cã ch−¬ng tr×nh 84.3. Cã thÓ ®Èy nhanh ch−¬ng tr×nh nµy, kh«ng cÇn xem xÐt c¸c −íc sè ®Õn i-1 mµ chØ cÇn tíi c¨n . §Ó lµm ®iÒu ®ã ta t×m k=i/j ( k>=j), cßn nÕu j lµ −íc sè cña i th× ta sÏ tÝnh kh«ng ®Õn j mµ ®Õn k. CÇn chó ý ®Ó kh«ng cã −íc sè nµo ®−îc lÊy 2 lÇn ( khi j=k). ThuËt to¸n nµy thùc hiÖn ë ch−¬ng tr×nh 84.3-2. 84.4. Chu k× cña ph©n sè. Lêi gi¶i phô thuéc nhiÒu mét sè ®iÒu kh«ng nh¾c tíi trong ®Çu bµi. Khi chia sè tù nhiªn M cho sè tù nhiªn N ta ®−îc phÇn nguyªn cña th−¬ng vµ sè d− : I = M/N , k = M - i * N ; §Ó gi¶i bµi to¸n tr−íc hÕt ta lo¹i bá tõ ph©n sè M/N phÇn nguyªn cña nã, b»ng c¸ch thay thÕ sè chia M bëi sè d− : M = M - M/N * N. B©y giê chóng ta cã thÓ tuÇn tù nhËn ®−îc c¸c ch÷ sè cña sè th−¬ng vµ sè d− cña ph©n sè : I = 10 * M/N ; m = 10 * M - i * N vµ v.v....... Mçi sè d− kh«ng v−ît qu¸ N, do vËy sÏ kh«ng cã nhiÒu h¬n N sè d− kh¸c nhau vµ chóng b¾t ®Çu lÆp l¹i. Khi sè d− b¾t ®Çu lÆp l¹i th× c¸c th−¬ng sè b¾t ®Çu lÆp l¹i vµ c¸c chu k× ®−îc b¾t ®Çu. §Ó t×m ®−îc phÇn lÆp l¹i, ®¬n gi¶n h¬n hÕt lµ dùa vµo m¶ng D[1:N]. ViÕt vµo ®ã c¸c sè d− theo trËt tù nhËn ®−îc vµ so s¸nh mçi sè d− míi víi tÊt c¶ c¸c sè d− tr−íc. Lêi gi¶i trªn ®¸ng tin cËy, nh−ng kh«ng hay, nã ®ßi hái k phÐp so s¸nh vµ xö lý k lÇn theo phÐp tÝnh sè d− vµ cã thÓ cÇn dïng ®Õn n2/2 phÐp so s¸nh ®Õn tÊt c¶ c¸c sè d−. H¬n n÷a ë tÊt c¶ c¸c m¸y hiÖn ®¹i lÊy phÇn nguyªn M vµ N kho¶ng 1016 , nh−ng ph¶i mÊt hµng n¨m vµo viÖc thùc hiÖn 1016 phÐp tÝnh. V× thÕ nÕu ta quyÕt ®Þnh ®−a vµo m¶ng D cã N sè ta sÏ khëi t¹o nã vµ ®¸nh dÊu sù xuÊt hiÖn cña sè d− lÇn l−ît thø M trong phÇn tö D[M]. Khi ®ã viÖc kiÓm tra sè d− theo “k” míi chØ cÇn mét phÐp so s¸nh. ThuËt to¸n trªn thùc hiÖn ë ch−¬ng tr×nh 84.4. Lêi gi¶i nµy cßn nh−îc ®iÓm. Sè N cã thÓ lín bao nhiªu tuú ý, sao cho N phÐp tÝnh cã thÓ tiÕn hµnh, nh−ng ®−a vµo bé nhí to¸n tö m¶ng N kh«ng thÓ ®−îc. Chóng ta sÏ t×m kiÕm chu kú mµ kh«ng cÇn ®−a ra m¶ng cho sè d−. Tr−íc tiªn chóng ta t¸ch ra tõ N bé phËn. Sau ®ã bá qua N ch÷ sè cña th−¬ng sè. Vµ b©y giê, khi chu kú râ rµng b¾t ®Çu, chóng ta ghi nhí mét sè d− duy nhÊt vµ sÏ in ch÷ sè cña th−¬ng sè t¹m thêi nã ch−a lÆp l¹i. §iÒu ®ã thùc hiÖn ë ch−¬ng tr×nh 84.4-2. Thó vÞ lµ nã ng¾n h¬n ch−¬ng tr×nh tr−íc. 84.5. Trén c¸c m¶ng. Bµi to¸n quan träng nµy vÒ nguyªn t¾c cÇn m+n thao t¸c. Chóng ta lÊy tõ A, B theo c¸c phÇn tö thø nhÊt, phÇn tö nhá h¬n trong ®ã chuyÓn ®Õn C vµ thay thÓ bëi phÇn tö tiÕp theo nã trong m¶ng. Mét lÇn n÷a chóng ta chän phÇn tö nhá h¬n trong hai phÇn tö chuyÓn sang m¶ng C. Vµ cø nh− thÕ....... Sau mçi phÐp so s¸nh, mét phÇn tö ®−îc thªm vµo C - nghÜa lµ sÏ cã Ýt h¬n m+n phÐp so s¸nh. ViÖc cuèi cïng lµ sao chÐp c¸c phÇn tö ë m¶ng sang C. 84.6. LÞch ThuËn tiÖn khi lËp m¶ng M[1:11] víi sè ngµy trong th¸ng cña n¨m kh«ng nhuËn. DÔ dµng sö dông hµm sè Mod(m,n) t×m sè d− cña phÐp chia m cho n hoÆc t−¬ng tù nã. 84.7. H×nh vu«ng. Trang 18
VIETBOOK NÕu tÊt c¶ c¸c sè ®øng ë c¸c gãc cña h×nh vu«ng kh¸c nhau, th× tæng cña chóng 0+1+5+11=17. Chó ý r»ng mÖnh ®Ò ®¶o còng ®óng. §iÒu nµy lµm ®¬n gi¶n ch−¬ng tr×nh. Olimpic 85 85.1. Ph©n tÝch ra n sè h¹ng. §Ó tr¸nh viÖc lÆp l¹i sù ph©n tÝch trong viÖc s¾p xÕp l¹i c¸c sè h¹ng, chóng ta sÏ chØ xÐt nh÷ng phÐp ph©n tÝch c¸c sè n ra sè tù nhiªn : n = m1 + m2 + .............trong ®ã m1>= m2>=.... Chóng ta s¾p xÕp c¸c kÕt qu¶ ph©n tÝch, gi¶ sö : n = m'1 + m'2 + m'3 +..................................(m') n = m''1 + m''2 + m''3 +..............................(m'') lµ hai phÐp ph©n tÝch. Chóng ta sÏ coi r»ng phÐp ph©n tÝch m' sÏ −u thÕ h¬n phÐp ph©n tÝch m'', nÕu ë cÆp ®Çu tiªn kh¸c nhau cã m'1m''1 vµ m'1>m''1, nghÜa lµ : m'j = m''j víi mäi j
VIETBOOK IJ=KR NÕu IJ>KR J[i]=j[i+1] j[i] = j[i] + 1 KR = IJ i = i+1 i=1 H×nh 1.5 Tr−íc khi nhËn ®−îc IJ = A[i,j[i]] cÇn viÕt kiÓm tra sù kÕt thóc. NÕu i>m th× gi¸ trÞ cÇn ®· t×m ®−îc . NÕu j[i] > n th× kh«ng cã. ThuËt to¸n nµy thùc hiÖn ë ch−¬ng tr×nh 85.2. Trong ch−¬ng tr×nh viÕt b»ng Basic thay thÓ c¸c phÇn tö j[i] b»ng c¸c phÇn tö A[i,0]. Nh−ng thay thÓ m¶ng gióp viÖc j[1:m] cã thÓ ®−a vµo dßng gióp viÖc io[1:m]. Ban ®Çu dßng ®Çu tiªn cña m¶ng ®−îc ®−a vµo, cßn sè c¸c phÇn tö cña dßng io gi¶ ®Þnh b»ng n. TiÕp theo c¸c dßng i=2, 3, ...., m cña m¶ng A ®−îc so s¸nh víi dßng io. ë dßng io chØ cßn l¹i c¸c phÇn tö (vµ ®−îc chuyÓn dÞch lªn ®Çu) ®−îc gÆp ë dßng i, cßn sè n0 c¸c phÇn tö cßn l¹i ë dßng io nhËn gi¸ trÞ míi. NÕu n0 ë b−íc nµo ®ã b»ng kh«ng, th× kh«ng cã c¸c phÇn tö b»ng nhau, cßn nÕu kh«ng io[1] sÏ lµ phÇn tö cÇn t×m kiÕmThuËt to¸n nµy ®−îc thùc hiÖn ë ch−¬ng tr×nh 85.2-2. ë ®©y trong ng«n ng÷ Basic hay Pascal thay thÕ c¸c phÇn tö io[j] b»ng c¸c phÇn tö A(0,j) (t−¬ng øng víi A[0,j]). 85.3. Sè kh«ng t¸ch ®−îc. Bµi to¸n nµy hay h¬n viÖc cã thÓ chØ ra tõ c¸ch nh×n ®Çu tiªn, v× nã ®−îc gi¶i sau n*n ( thËm chÝ sau n*log n ) phÐp to¸n. §©y lµ lêi gi¶i cã thÓ cã. §Æt s = 1 vµ xem xÐt cã hay kh«ng trong m¶ng P phÇn tö P[j]