Tuyển tập các bài toán olympic lập trình

Tham khảo tài liệu tuyển tập các bài toán olympic lập trình, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Tuyển tập các bài toán olympic lập trình tungvn40@yahoo.com CM Soft 70 NCT F2 Q10 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 ntungvn40@yahoo.com CM Soft 70 NCT F2 Q10 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 +......+ a1.2 + a0 1 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 CM Soft 70 NCT F2 Q10tungvn40@yahoo.comtungvn40@yahoo.com CM Soft 70 NCT F2 Q10 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 nha ...