Bai Tap Pascal Co Ban

Bµi tËp c¬ b¶n – TËp I

C¸c bµi tËp c¬ b¶n Bµi 1. ViÕt ch¬ng tr×nh nhËp sè nguyªn d¬ng N<=1000 vµ N sè nguyªn A[1], . . ., A[N]. H·y th«ng b¸o ra mµn h×nh c¸c sè sau: - Gi¸ trÞ lín nhÊt cña d·y vµ c¸c chØ sè cña c¸c sè h¹ng ®¹t gi¸ trÞ lín nhÊt. - Gi¸ trÞ nhá nhÊt cña d·y vµ c¸c chØ sè cña c¸c sè h¹ng ®¹t gi¸ trÞ nhá nhÊt. - Gi¸ trÞ lín thø nh× cña d·y vµ c¸c chØ sè cña c¸c sè h¹ng ®¹t gi¸ trÞ lín nh×. - Gi¸ trÞ nhá thø nh× cña d·y vµ c¸c chØ sè cña c¸c sè h¹ng ®¹t gi¸ trÞ nhá nh×. - D·y con gåm nhiÒu nhÊt c¸c sè h¹ng liªn tiÕp cña d·y lËp thµnh mét cÊp sè céng - D·y con gåm nhiÒu nhÊt c¸c sè h¹ng liªn tiÕp cña d·y lËp thµnh mét d·y ®¬n ®iÖu - D·y con gåm nhiÒu nhÊt c¸c sè h¹ng liªn tiÕp tr¸i dÊu nhau cña d·y - D·y con gåm nhiÒu nhÊt c¸c sè h¹ng liªn tiÕp cïng dÊu cña d·y Bµi 2. ViÕt ch¬ng tr×nh nhËp tõ bµn phÝm hai sè nguyªn d¬ng M vµ N ≤ 10000 vµ in ra mµn h×nh íc chung lín nhÊt cña hai sè ®ã. Bµi 3. ViÕt ch¬ng tr×nh nhËp tõ bµn phÝm sè nguyªn d¬ng N ≤ 30000 vµ th«ng b¸o ra mµn h×nh N cã lµ sè nguyªn tè hay kh«ng. Bµi 4. ViÕt ch¬ng tr×nh nhËp tõ bµn phÝm sè nguyªn d¬ng N ≤ 10000 vµ th«ng b¸o ra mµn h×nh c¸c sè K<=N cã b»ng tæng c¸c íc cña nã vµ nhá h¬n nã? (Sè K tho¶ m·n ®iÒu kiÖn trªn ®îc gäi lµ sè hoµn thiÖn, vÝ dô 6=1+2+3 lµ sè hoµn thiÖn) Bµi 5. NhËp tõ bµn phÝm sè nguyªn d¬ng N<=10000 vµ N sè thùc A1, . ., AN. H·y s¾p xÕp d·y ®ã theo thø tù kh«ng gi¶m. Th«ng b¸o ra mµn h×nh d·y ®îc s¾p xÕp l¹i ®ã vµ ghi râ tõng sè h¹ng lµ sè h¹ng nµo cña d·y cò. Bµi 6. Cã N gãi kÑo, N<=200, c¸c gãi kÑo ®îc ®¸nh sè tõ 1 ®Õn N, gãi kÑo thø i cã A[i] c¸i kÑo, c¸c sè a[1], . ., a[N] ®Òu nguyªn d¬ng vµ kh«ng qu¸ 200. H·y th«ng b¸o ra mµn h×nh mét c¸ch chia c¸c gãi kÑo lµm hai nhãm sao cho tæng sè kÑo trong c¸c nhãm sai kh¸c nhau Ýt nhÊt. D÷ liÖu vµo ®îc cho bëi file INP.BL trong ®ã dßng thø nhÊt ghi sè N vµ trong c¸c dßng tiÕp theo, mçi dßng ghi 10 sè lÇn lît tõ A[1] ®Õn A[N]. KÕt qu¶ ghi ra file OUT.BL nh sau: dßng thø nhÊt ghi sè kÑo chªnh lÖch gi÷a hai nhãm, tiÕp theo lµ mét nhãm dßng ghi sè hiÖu c¸c gãi kÑo thuéc nhãm thø nhÊt, mçi dßng ghi 20 sè hiÖu, cuèi cïng lµ mét

-1– Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

nhãm dßng ghi sè hiÖu c¸c gãi kÑo thuéc nhãm thø hai, mçi dßng ghi 20 sè hiÖu. Bµi 7. ViÕt ch¬ng tr×nh nhËp tõ bµn phÝm bèn sè nguyªn d¬ng A, B, C, D, 1<=A<=31, 1<=B<=12, -2000<=C<=2000, 1<=D<=7. ý nghÜa cña bèn sè nµy lµ ngµy A th¸ng B n¨m C lµ ngµy thø D, trong ®ã 1 lµ chñ nhËt, 2 lµ thø hai, . ., 7 lµ ngµy thø b¶y. NhËp tiÕp ba sè nguyªn d¬ng A1, B1, C1 tho¶ m·n c¸c ®iÒu kiÖn t¬ng øng nh ®èi víi A, B, C. H·y th«ng b¸o ra mµn h×nh ngµy A1 th¸ng B1 n¨m C1 lµ ngµy thø mÊy? BiÕt r»ng nÕu n¨m chia hÕt cho 4, th¸ng 2 cã 29 ngµy, cßn víi c¸c n¨m kh¸c, th¸ng 2 chØ cã 28 ngµy. Bµi 8. Cho mét h×nh ch÷ nhËt cã c¸c c¹nh lµ c¸c sè nguyªn d¬ng M, N, M vµ N kh«ng qu¸ 100. H×nh ch÷ nhËt ®îc chia thµnh c¸c « vu«ng c¹nh ®¬n vÞ b»ng c¸c ®êng song song víi c¸c c¹nh, c¸c « nµy ®îc ®¸nh sè nh sau: c¸c dßng « ®¸nh sè tõ 1 ®Õn M tõ díi lªn trªn, c¸c cét « ®¸nh sè tõ 1 ®Õn N tõ tr¸i sang ph¶i, khi ®ã mçi « ®îc ®Æc trng bëi chØ sè dßng vµ chØ sè cét cña nã. H·y ghi ra mµn h×nh c¸c « vu«ng cã ®iÓm chung víi ®êng chÐo cña h×nh ch÷ nhËt ®i tõ gãc tr¸i trªn cña « [1,1] ®Õn gãc ph¶i díi cña « [M,N]. Bµi 9. ViÕt ch¬ng tr×nh nhËp sè nguyªn d¬ng N<=1000 vµ d·y N sè nguyªn A[1], . . ., A[N]. H·y xÐt xem d·y sè ®ã cã bao nhiªu gi¸ trÞ kh¸c nhau vµ mçi gi¸ trÞ ®ã lµ gi¸ trÞ cña c¸c sè h¹ng nµo cña d·y. Bµi 10. ViÕt ch¬ng tr×nh nhËp tõ bµn phÝm hai sè nguyªn d¬ng M vµ N, M,N<=10000. H·y viÕt ra mµn h×nh biÓu diÔn díi d¹ng sè thËp ph©n (nãi chung lµ v« h¹n tuÇn hoµn) cña ph©n sè M/N tøc lµ d¹ng M/N = b1 . .bk,c1. . . cm (d1 . . dr) VÝ dô nÕu M=2, N=3, ta ph¶i viÕt ra mµn h×nh 0,(6). Bµi 11. H·y t×m mét c¸ch biÓu diÔn c¸c sè lín hµng tr¨m ch÷ sè vµ thùc hiÖn c¸c phÐp to¸n céng vµ trõ. Bµi 12. ViÕt ch¬ng tr×nh nhËp tõ bµn phÝm hai sè nguyªn d¬ng M, N. H·y t×m c¸ch thay c¸c dÊu ? trong biÓu thøc sau bëi c¸c phÐp to¸n +, -, * sao cho gi¸ trÞ cña biÓu thøc nhËn ®îc b»ng N: ((((M?M)?M)?M)?M) NÕu kh«ng cã thÓ ®îc, h·y th«ng b¸o lµ kh«ng thÓ ®îc. Bµi 13. ViÕt ch¬ng tr×nh nhËp mét sè thùc d¬ng R vµ mét sè nguyªn d¬ng MAX. H·y t×m trong sè c¸c ph©n sè cã d¹ng P/Q víi Q<=MAX ph©n sè gÇn sè R nhÊt. Bµi 14. ViÕt ch¬ng tr×nh nhËp sè nguyªn d¬ng N<=30000 vµ th«ng b¸o ra mµn h×nh sè ch÷ sè kh«ng tËn cïng cña N!.

-2– Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

Bµi 15. ViÕt ch¬ng tr×nh nhËp tõ bµn phÝm hai x©u ký tù S1 vµ S2. 1. Th«ng b¸o ra mµn h×nh ®é dµi cña S1 vµ S2. 2. H·y xÐt xem S1 cã xuÊt hiÖn bao nhiªu lÇn trong S2 vµ xuÊt hiÖn t¹i nh÷ng vÞ trÝ nµo? 3. H·y xÐt xem liÖu S2 cã lµ ghÐp liªn tiÕp cña mét sè lÇn x©u S1 kh«ng? Bµi 16. ViÕt ch¬ng tr×nh nhËp tõ bµn phÝm mét ký tù vµ mét x©u ký tù. H·y th«ng b¸o ra mµn h×nh ký tù ®ã xuÊt hiÖn bao nhiªu lÇn trong x©u ký tù vµ t¹i nh÷ng vÞ trÝ nµo? Bµi 17. ViÕt ch¬ng tr×nh nhËp 5 sè nguyªn A0, A1, A2, A3, A4. H·y th«ng b¸o ra mµn h×nh t×m mäi nghiÖm nguyªn cña ph¬ng tr×nh A0 +A1X + A1X2 + A3X3 + A4 X4 = 0 Bµi 18. ViÕt ch¬ng tr×nh nhËp mét x©u ký tù S chØ gåm c¸c ch÷ c¸i thêng. H·y lËp x©u S1 nhËn ®îc tõ S b»ng c¸ch s¾p xÕp l¹i c¸c ký tù theo vÇn a, b, c, . . . VÝ dô nÕu S = 'xbaqp' th× S1 = 'abpqx'. Bµi 19. ViÕt ch¬ng tr×nh nhËp 8 sè thùc X1, Y1, X2, Y2, X3, Y3, X4, Y4, t¬ng øng lµ to¹ ®é cña bèn ®iÓm A, B, C, D trong mÆt ph¼ng to¹ ®é. Th«ng b¸o ra mµn h×nh c¸c kÕt qu¶ sau: 1. Ba ®iÓm A, B, C cã lËp thµnh mét tam gi¸c kh«ng? 2. NÕu ABC lµ mét tam gi¸c, h·y xÐt xem ®iÓm D cã n»m bªn trong tam gi¸c nµy kh«ng? Bµi 20. ViÕt ch¬ng tr×nh nhËp sè nguyªn d¬ng N<=1000 vµ d·y A gåm N sè nguyªn d¬ng kh¸c nhau tõng ®«i A[1], . ., A[N]. H·y t×m mét d·y B gåm nhiÒu sè h¹ng nhÊt (kh«ng nhÊt thiÕt lµ liªn tiÕp) cña A sao cho víi bÊt kú ba sè h¹ng kh¸c nhau X, Y, Z cña B, ta lu«n cã tæng X + Y + Z kh«ng lín h¬n tæng c¸c sè h¹ng cßn l¹i cña B. Bµi 21. Gi¶ sö trong mét phiªn lµm viÖc tõ thêi ®iÓm 0 ®Õn thêi ®iÓm T = 8640000, mét trung t©m tÝnh to¸n ph¶i thùc hiÖn N ch¬ng tr×nh, ch¬ng tr×nh i thùc hiÖn tõ thêi ®iÓm A[i] ®Õn thêi ®iÓm B[i], 0<=A[i]<=B[i]
-3– Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

D÷ liÖu vµo ®îc cho bëi file INP.BL trong ®ã dßng thø nhÊt ghi sè nguyªn d¬ng N <=200. Víi 1<=i<=N, dßng thø i+1 ghi hai sè nguyªn kh«ng ©m A[i] vµ B[i]. Dßng thø N+2 ghi hai sè nguyªn kh«ng ©m P1, Q1, P1<=Q1. Dßng thø N+3 ghi hai sè nguyªn kh«ng ©m R1, S1, R1<=S1. KÕt qu¶ ghi ra file OUT.BL: dßng thø nhÊt ghi CO/KHONG tuú theo kÕt qu¶ cô thÓ; dßng thø hai ghi CO/KHONG tuú theo kÕt qu¶ cô thÓ; dßng thø ba ghi hai sè P,Q; dßng thø t ghi hai sè R, S. Bµi 22. ViÕt ch¬ng tr×nh lµm c¸c viÖc sau: 1. NhËp mét sè nguyªn d¬ng N<=1000 vµ d·y A gåm N sè tù nhiªn A[1], . ., A[N]. 2. T×m sè tù nhiªn nhá nhÊt kh«ng lµ tæng cña mét sè sè h¹ng cña d·y A. Tæng nµy cã thÓ chØ gåm mét sè h¹ng vµ nÕu cã nhiÒu h¬n, c¸c sè h¹ng kh«ng nhÊt thiÕt liªn tiÕp nhau nhng mçi sè h¹ng cña d·y kh«ng xuÊt hiÖn qu¸ mét lÇn. Bµi 23. Cho mét s©n h×nh ch÷ nhËt cã kÝch thíc MxN ®îc chia thµnh MxN « vu«ng b»ng nhau bëi c¸c ®êng song song víi c¸c c¹nh. Trªn mçi « vu«ng cã thÓ ch«n hoÆc kh«ng ch«n mét qu¶ m×n. T×nh tr¹ng cña b·i m×n cã thÓ ®îc m« t¶ bëi mét trong hai c¸ch sau: C¸ch thø nhÊt: Dïng mét m¶ng MIN1[1..M,1..N] trong ®ã phÇn tö MIN1[i,j] = 1 hay 0 tuú theo « [i,j] cã m×n hay kh«ng. C¸ch thø hai: Mçi « cña s©n cã nhiÒu nhÊt 8 « kh¸c nã kÒ c¹nh víi nã nh trong h×nh vÏ sau 1

2

4

1

0

1

16

18 4

96

12 8

« i,j

8

0

1

1

58

10 9

19 4

64

32

16

1

1

0

12

13 4

13 1

H×nh 1

H×nh 2 (bªn tr¸i: MIN1, bªn ph¶i: MIN2)

Ta øng c¸c « nµy víi c¸c sè 1, 2, 4, 8, 16, 32, 64, 128 nh h×nh 1. Khi ®ã ta lËp mét m¶ng MIN2[1..M,1..N] nh sau: MIN2[i,j] b»ng tæng c¸c sè h¹ng cã d¹ng X.Y trong ®ã X lµ sè øng víi mét « kÒ c¹nh víi nã, Y b»ng 1 hay 0 tuú theo « ®ã cã hay kh«ng cã m×n, « [i,j] cã bao nhiªu « kÒ c¹nh th× tæng cã bÊy nhiªu sè h¹ng. Trong h×nh 2 cho vÝ dô vÒ c¸ch lËp m¶ng MIN2 øng víi t×nh tr¹ng m×n cho bëi m¶ng MIN1. ViÕt ch¬ng tr×nh lµm c¸c viÖc sau: 1. §äc tõ file MIN1.TXT m¶ng MIN1 cho biÕt t×nh tr¹ng m×n theo c¸ch thø nhÊt, trong ®ã dßng thø nhÊt ghi hai sè nguyªn d¬ng M, N <=100, trong M dßng sau, dßng thø i ghi N sè lÇn lît lµ MIN1[i,1], . ., -4– Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

MIN1[i,N]. Ghi ra file MIN1-2.TXT m¶ng MIN2 thÓ hiÖn t×nh tr¹ng m×n theo c¸ch thø hai, mçi dßng cña m¶ng MIN2 ghi thµnh mét dßng cña file. 2. §äc tõ file MIN2.TXT m¶ng MIN2 cho biÕt t×nh tr¹ng m×n theo c¸ch thø nhÊt, trong ®ã dßng thø nhÊt ghi hai sè nguyªn d¬ng M, N <=100, trong M dßng sau, dßng thø i ghi N sè lÇn lît lµ MIN2[i,1], . ., MIN2[i,N]. Ghi ra file MIN2-1.TXT m¶ng MIN1 thÓ hiÖn t×nh tr¹ng m×n theo c¸ch thø hai, mçi dßng cña m¶ng MIN1 ghi thµnh mét dßng cña file. Bµi 24.ViÕt ch¬ng tr×nh lµm c¸c viÖc sau: 1. NhËp tõ bµn phÝm hai x©u ký tù S1 vµ S2. 2. Ta cã thÓ dïng mét trong ba lo¹i phÐp biÕn ®æi sau: BD1: xo¸ mét ký tù nµo ®ã trong x©u, BD2: thªm mét ký tù nµo ®ã vµo mét vÞ trÝ nµo ®ã cña x©u, BD3: thay mét ký tù nµo ®ã trong x©u b»ng mét ký tù kh¸c. H·y th«ng b¸o ra file OUT.TXT liÖu cã thÓ dïng mét sè phÐp biÕn ®æi thuéc ba lo¹i trªn ®Ó biÕn ®æi S1 thµnh S2 kh«ng, quy c¸ch th«ng b¸o nh sau: vÝ dô S1 = ptsddf, S2 = tsgldds, th× ta ph¶i th«ng b¸o nh sau: BiÕn ®æi ®îc ptslddf - xo¸ p/1 => tslddf tslddf - thªm g/3 => tsgdldf tsgdldf - thay f/7/s => tsgldds 3. Trong trêng hîp biÕn ®æi ®îc, h·y t×m mét c¸ch biÕn ®æi dïng Ýt phÐp biÕn ®æi nhÊt vµ th«ng b¸o tiÕp vµo file OUT.TXT theo quy c¸ch nh trªn. Bµi 25. Cho mét b¶ng vu«ng c¹nh dµi N ®¬n vÞ, N nguyªn d¬ng, 3<=N<=25. B¶ng ®îc chia thµnh NxN « vu«ng b»ng nhau b»ng c¸c ®êng song song víi c¸c c¹nh.Trªn mét sè « kh«ng n»m trªn c¹nh cña b¶ng cã ®Æt vËt c¶n nhng b¶ng cã m¸i che nªn kh«ng biÕt ®îc vËt c¶n n»m ë nh÷ng « nµo. Ta cã thÓ dïng mét qu¶ bãng l¨n tõ ngoµi vµo b¶ng theo c¸c dßng/cét cña b¶ng. Khi ®ã diÔn biÕn chuyÓn ®éng cña qu¶ bãng nh sau: TH1. NÕu qu¶ bãng gÆp « cã vËt c¶n, nã quay l¹i ngîc chiÒu. TH2. NÕu qu¶ bãng ®i tiÕp sóc víi mét « cã vËt c¶n, nã ®æi híng 90o theo híng vu«ng gãc víi c¹nh tiÕp sóc ngay t¹i « kÒ ®Ønh víi « chøa vËt c¶n. TH1 sÏ xÈy ra khi ®ång thêi cã c¶ TH1 vµ TH2. TH3. NÕu qu¶ bãng tiÕp sóc víi hai « cã vËt c¶n, nã sÏ quay l¹i ngîc chiÒu NhËp tõ file INP.BL1 sè nguyªn d¬ng N, 3<=N<=100 ghi ë dßng thø nhÊt, trong N dßng sau mçi dßng ghi N sè 0/1, dßng thø i+1 lµ t×nh tr¹ng c¸c « cña dßng i cña b¶ng trong ®ã 1/0 t¬ng øng lµ cã/kh«ng cã vËt c¶n. Dßng thø N+2 ghi mét x©u ký tù cã mét trong c¸c d¹ng sau thÓ hiÖn c¸ch l¨n qu¶ bãng vµo b¶ng. - D-U-1 (cã nghÜa lµ bãng l¨n vµo dßng U theo híng tõ « [U,1]) - D-U-N (cã nghÜa lµ bãng l¨n vµo dßng U theo híng tõ « [U,N]) - C-U-1 (cã nghÜa lµ bãng l¨n vµo cét U theo híng tõ « [1,U]) -5– Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

- C-U-N (cã nghÜa lµ bãng l¨n vµo cét U theo híng tõ « [N,U]) In ra file OUT.BL1 d·y c¸c « liªn tiÕp cña b¶ng trªn hµnh tr×nh cña qu¶ bãng, mçi « ghi trªn mét dßng gåm hai sè lµ sè dßng vµ sè cét cña « ®ã. VÝ dô. Trong h×nh vÏ sau trong ®ã « ghi ch÷ X lµ « cã vËt c¶n. 1

2

3

4

5

6

1 2

X

3

X X

4 5

X

X

6

NÕu x©u ký tù lµ C-4-6 th× hµnh tr×nh cña qu¶ bãng sÏ lµ: 64 63 NÕu x©u ký tù lµ D-3-6 th× hµnh tr×nh cña qu¶ bãng sÏ lµ 36 35 45 35 46 Bµi 26. Cho mét d·y N viªn bi gåm 3 mÇu xanh, tr¾ng, ®á xÕp lÉn lén. B»ng c¸ch ®æi chç tõng cÆp viªn bi cho nhau, h·y xÕp l¹i d·y bi trªn theo tr×nh tù xanh tríc, tr¾ng gi÷a, ®á sau. Yªu cÇu cÇn dïng mét sè Ýt nhÊt phÐp ®æi chç. D÷ liÖu vµo ®îc cho bëi file INP1.TXT. Dßng thø nhÊt ghi sè nguyªn d¬ng N<=1000. Trong N dßng tiÕp theo, mçi dßng ghi ë vÞ trÝ ®Çu tiªn mét ký tù thuéc ba lo¹i: X, T, D thÓ hiÖn d·y bi ban ®Çu. D÷ liÖu ra ghi vµo file OUT1.TXT trong ®ã dßng thø nhÊt ghi sè lîng phÐp ®æi chç cÇn dïng. Trong nh÷ng dßng tiÕp theo, mçi dßng ghi mét phÐp ®æi chç díi d¹ng hai sè p q cã nghÜa lµ ®æi chç c¸c viªn bi ë hai vÞ trÝ p vµ q cho nhau. Tr×nh tù viÕt c¸c dßng lµ tr×nh tù c¸c phÐp ®æi chç ®îc tiÕn hµnh. -6– Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

Thêi gian ch¹y ch¬ng tr×nh: 20 gi©y. VÝ dô INP1.TXT OUT1.TXT 9 4 T 1 3 T 4 7 X 9 2 D 5 9 D D T D X Bµi 27. Tæng gi¸m ®èc mét c«ng ty muèn tæ chøc mét buæi liªn hoan cho c¸c ®ång nghiÖp trong c«ng ty. Mçi c¸n bé cña c«ng ty ngo¹i trõ tæng gi¸m ®èc ®Òu cã ®óng mét cÊp trªn trùc tiÕp cña m×nh. C¸n bé P ®îc gäi lµ cÊp trªn cña c¸n bé Q nÕu cã mét d·y c¸n bé P1, P2, . ., Pk, k>=2, sao cho P=P1, Pk=Q vµ víi 1<=i<=k-1, Pi lµ cÊp trªn trùc tiÕp cña Pi+1. §Ó cho mäi c¸n bé ®îc tho¶i m¸i, tæng gi¸m ®èc kh«ng muèn mét c¸n bé bÊt kú nµo ngåi cïng mét bµn víi cÊp trªn cña m×nh. H·y tÝnh xem cÇn tèi thiÓu bao nhiªu bµn dïng cho buæi liªn hoan theo yªu cÇu cña TG§. D÷ liÖu vµo ®îc cho bëi file INP.TXT trong ®ã dßng thø nhÊt ghi sè nguyªn d¬ng N <=200 lµ sè lîng toµn thÓ c¸n bé cña c«ng ty, c¸c c¸n bé cña c«ng ty cã tªn tõ 1 ®Õn N, TG§ cã tªn 1 vµ kh«ng cã cÊp trªn. Dßng thø hai ghi sè nguyªn d¬ng K, 2 <= k <= 10, lµ sè ngêi tèi ®a cã thÓ ngåi trong mét bµn (chó ý r»ng khi xÕp, kh«ng nhÊt thiÕt mäi bµn ph¶i ®ñ K ngêi). Dßng thø ba ghi N sè trong ®ã sè thø nhÊt lµ sè 0, sè thø i lµ tªn cÊp trªn trùc tiÕp cña c¸n bé i. D÷ liÖu ®óng nh m« t¶. Ghi ra file OUT.TXT sè lîng M bµn cÇn dïng. Trong M dßng tiÕp theo, dßng thø i ghi tªn c¸n bé ngåi bµn i. VÝ dô INP.TXT OUT.TXT 13 5 4 0 1 9 9 9 2 2 1 1 8 8 10 Thêi gian ch¹y ch¬ng tr×nh: Kh«ng qu¸ 30 gi©y. Bµi 28. Cã N qu¶ cÇu víi sè hiÖu lµ 1, 2, . . ., N, N<=200. BiÕt träng lîng cña qu¶ cÇu 1 lµ M[1], cña qu¶ cÇu N lµ M[N]. Cã h»ng sè D sao cho víi mäi i, 1
-7– Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

Bµi 29. Cã N l¸ Bµi víi c¸c sè hiÖu 1, 2, . . ., N, N<=50, trªn l¸ Bµi i ghi mét sè nguyªn d¬ng F[i], 1<=F[i]<=N. H·y t×m mét sè nhiÒu nhÊt c¸c l¸ Bµi sao cho tËp c¸c sè hiÖu cña chóng trïng víi tËp c¸c sè ghi trªn c¸c l¸ Bµi ®ã. D÷ liÖu vµo cho bëi file INP.BL2 trong ®ã dßng thø nhÊt ghi sè N nguyªn d¬ng. Trong c¸c dßng tiÕp theo ghi mçi dßng 10 sè (cho tíi khi hÕt N sè) lÇn lît lµ c¸c sè ghi trong c¸c l¸ Bµi tõ l¸ Bµi 1 ®Õn l¸ Bµi N. D÷ liÖu ra ghi ra file OUT.BL2 trong ®ã dßng thø nhÊt ghi sè lîng l¸ bµi. Trong c¸c dßng tiÕp theo, mçi dßng ghi 10 sè hiÖu cña c¸c l¸ Bµi ®îc chän, c¸c sè hiÖu ghi theo thø tù t¨ng dÇn cho tíi hÕt. VÝ dô INP.BL2 14 6 5 1 3 4 2 8 10 7 9 3 2 1 9 OUT.BL2 10 1 2 3 4 5 6 7 8 9 10 Bµi 30. B¾t ®Çu tõ thêi ®iÓm 0, mét ngêi lµm N viÖc víi sè hiÖu tõ 1 ®Õn N, N<=200. Víi 1<=i<=N, viÖc i cÇn lµm trong T[i] ®¬n vÞ thêi gian vµ mçi ®¬n vÞ thêi gian tõ thêi ®iÓm 0 ®Õn lóc b¾t ®Çu lµm nã, ngêi ®ã bÞ ph¹t mét lîng tiÒn C[i]. Khi ®· lµm mét viÖc nµo th× ph¶i lµm xong míi chuyÓn sang lµm viÖc kh¸c. H·y thu xÕp tr×nh tù c¸c viÖc lµm sao cho tæng sè tiÒn bÞ ph¹t lµ Ýt nhÊt. D÷ liÖu vµo ®îc cho bíi file INP.BL trong ®ã dßng thø nhÊt ghi sè nguyªn d¬ng N. Víi 1<=i<=N, dßng thø i+1 ghi hai sè thùc T[i] vµ C[i]. D÷ liÖu ra ghi trong file OUT.BL. Dßng thø nhÊt ghi tæng sè tiÒn bÞ ph¹t. Tõ dßng thø hai ghi mçi dßng 1 cÆp sè: sè thø nhÊt lµ sè hiÖu viÖc, sè thø hai lµ thêi ®iÓm b¾t ®Çu viÖc. Tr×nh tù tõ trªn xuèng díi lµ tr×nh tù lÇn lît lµm c¸c viÖc. Bµi 31. Cho x©u S chØ gåm c¸c dÊu më vµ ®ãng ngoÆc trßn (, ). H·y xÐt xem liÖu cã thÓ viÕt thªm mét sè to¸n h¹ng vµ dÊu phÐp to¸n gi÷a c¸c dÊu ®ã ®Ó nhËn ®îc mét biÓu thøc sè häc ®óng kh«ng. D÷ liÖu vµo ®îc cho bëi file INP.BL trong ®ã mçi dßng ghi mét x©u ký tù. Víi mçi dßng ®äc ®îc cña file INP.BL, cã ba kh¶ n¨ng: - NÕu x©u t¬ng øng chøa ký tù kh¸c víi ( vµ ), ghi vµo file OUT.BL dßng ch÷ KHONG HOP LE - NÕu x©u chØ gåm c¸c ký tù ( vµ ) vµ cã thÓ viÕt thªm mét sè to¸n h¹ng vµ dÊu phÐp to¸n gi÷a c¸c dÊu ®ã ®Ó nhËn ®îc mét biÓu thøc sè häc ®óng th× ghi vµo file OUT.BL dßng ch÷ DUNG - NÕu x©u chØ gåm c¸c ký tù ( vµ ) nhng kh«ng thÓ viÕt thªm mét sè to¸n h¹ng vµ dÊu phÐp to¸n gi÷a c¸c dÊu ®ã ®Ó nhËn ®îc mét biÓu thøc sè häc ®óng th× ghi vµo file OUT.BL dßng ch÷ -8– Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

VÝ dô

KHONG DUNG INP.BL (((abc)) ((()()))() (()(()()))))

OUT.BL KHONG HOP LE DUNG KHONG DUNG

Bµi 32. Cho mét ®å thÞ v« híng N ®Ønh ®¸nh sè tõ 1 ®Õn N, N<=100, cã ma trËn kÒ A[1..N,1..N] vµ hai ®Ønh U, V bÊt kú. H·y t×m ®êng ®i tõ U ®Õn V (nÕu cã) qua Ýt c¹nh nhÊt. D÷ liÖu vµo ®îc cho bëi file INP.BL trong ®ã dßng thø nhÊt ghi 3 sè nguyªn d¬ng N, U, V, trong N dßng tiÕp theo, dßng thø i ghi N sè A[i,1], . ., A[i,N]. KÕt qu¶ ghi ra file OUT.BL nh sau: - NÕu kh«ng cã ®êng ®i, ghi dßng ch÷ KHONG CO DUONG DI, - NÕu cã ®êng ®i, ghi hai dßng: dßng thø nhÊt ghi sè c¹nh, dßng thø hai ghi c¸c ®Ønh lÇn lît trªn ®êng ®i tõ U ®Õn V. Bµi 33. Cho mét ®å thÞ cã híng N ®Ønh, N<=100, cã ma trËn kÒ A[1..N,1..N] vµ hai ®Ønh U, V bÊt kú. H·y t×m ®êng ®i tõ U ®Õn V (nÕu cã) qua nhiÒu cung nhÊt mµ mçi cung kh«ng ®i h¬n mét lÇn. D÷ liÖu vµo ®îc cho bëi file INP.BL trong ®ã dßng thø nhÊt ghi 3 sè nguyªn d¬ng N, U, V, trong N dßng tiÕp theo, dßng thø i ghi N sè A[i,1], . ., A[i,N]. KÕt qu¶ ghi ra file OUT.BL nh sau: - NÕu kh«ng cã ®êng ®i, ghi dßng ch÷ KHONG CO DUONG DI, - NÕu cã ®êng ®i, ghi hai dßng: dßng thø nhÊt ghi sè cung, dßng thø hai ghi c¸c ®Ønh lÇn lît trªn ®êng ®i tõ U ®Õn V. Bµi 34. Cho sè nguyªn d¬ng N<=50 vµ 2N sè thùc X1, Y1, X2, Y2, . . ., XN, YN mµ víi 1<=i<=N, (Xi,Yi) lµ to¹ ®é cña ®iÓm Mi. T×m ®iÓm M(X,0) trªn trôc hoµnh sao cho kho¶ng c¸ch lín nhÊt tõ M ®Õn c¸c ®iÓm Mi lµ nhá nhÊt cã thÓ ®îc. D÷ liÖu vµo ®îc cho bëi file INP.BL trong ®ã dßng thø nhÊt ghi sè N, trong N dßng tiÕp theo, dßng thø i ghi hai sè thùc Xi vµ Yi. Rh«ng b¸o ra mµn h×nh kho¶ng c¸ch cÇn t×m. Bµi 35. Cho mét thïng dung tÝch cã thÓ xem lµ v« h¹n vµ N b×nh cã dung tÝch V1, V2, . . ., VN lÝt. LiÖu cã thÓ dïng N b×nh nµy ®Ó ®æ vµo thïng ®óng V lÝt níc kh«ng? Khi dïng mçi b×nh ®Ó ®æ níc vµo thïng, b×nh ®ã ph¶i chøa ®Çy níc. D÷ liÖu vµo ®îc cho bëi file INP.BL, dßng thø nhÊt ghi sè nguyªn d¬ng N<=20 vµ sè nguyªn d¬ng V. Trong N dßng tiÕp theo, dßng thø i ghi sè nguyªn d¬ng Vi. KÕt qu¶ ghi ra file OUT.BL nh sau: - NÕu kh«ng ®îc, ghi dßng ch÷ KHONG DUOC - NÕu cã thÓ ®îc, ghi dßng ch÷ CO THE, tiÕp theo lµ N dßng, dßng thø i ghi sè lîng b×nh níc cã dung tÝch Vi cÇn ®æ vµo thïng.

-9– Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

Bµi 36. Cho N x©u ký tù A1, A2, . ., AN, N<=100, ®é dµi mçi x©u Ai kh«ng qu¸ 10, vµ mét x©u ký tù S. H·y t×m mäi c¸ch biÓu diÔn S díi d¹ng ghÐp cña c¸c x©u ký tù Ai, mçi x©u Si cã thÓ xuÊt hiÖn trong biÓu diÔn ®ã nhiÒu lÇn. D÷ liÖu vµo ®îc cho bëi file XAU.TXT trong ®ã dßng thø nhÊt ghi x©u S, dßng thø hai ghi sè N, trong N dßng tiÕp theo, dßng thø i ghi x©u Ai. KÕt qu¶ ghi ra file KQ.TXT nh sau: - NÕu kh«ng cã biÓu diÔn, ghi dßng ch÷ KHONG CO - NÕu cã biÓu diÔn, ghi mçi biÓu diÔn trªn mét dßng theo quy c¸ch nh vÝ dô. VÝ dô vÒ hai file d÷ liÖu vµo vµ ra: XAU.TXT KQ.TXT abcdef A[1]A[2]A[3] 11 A[1]A[2]A[10]A[11] ab A[1]A[8]A[5] cd A[1]A[8]A[9]A[3] ef A[1]A[8]A[9]A[10]A[11] abc A[4]A[5] def A[4]A[9]A[3] a A[4]A[9]A[10]A[11] b A[6]A[7]A[2]A[3] c A[6]A[7]A[2]A[10]A[11] d A[6]A[7]A[8]A[5] e A[6]A[7]A[8]A[9]A[3] f A[6]A[7]A[8]A[9]A[10]A[1 1] Bµi 37. H·y t×m hai sè nguyªn d¬ng P, Q sao cho cã sè A mµ khi viÕt trong c¬ sè P cã d¹ng 0,(ab), (ab) lµ chu kú cña A vµ khi viÕt trong d¹ng c¬ sè Q cã d¹ng 0,(ba). Bµi 38. Cã N thµnh phè víi c¸c tªn tõ 1 ®Õn N, N<=100. M¶ng C[1..N,1..N] tho¶ m·n c¸c ®iÒu kiÖn: C[i,j] = C[j,i] = 0 nÕu kh«ng cã ®êng ®i tõ i ®Õn j vµ b»ng 1 nÕu cã ®êng ®i tõ i ®Õn j, c¸c ®êng ®i ®Òu lµ hai chiÒu. H·y xÐt xem cã hay kh«ng mét hµnh tr×nh sao cho mçi ®êng ®i gi÷a c¸c thµnh phè ®îc ®i ®óng mét lÇn. D÷ liÖu vµo ®îc cho bëi file INP.BL trong ®ã dßng thø nhÊt ghi sè nguyªn d¬ng N, trong N dßng tiÕp theo, dßng thø i ghi N sè C[i,1], . ., C[i,N]. KÕt qu¶ ghi ra file OUT.BL nh sau: - NÕu kh«ng cã thÓ, h·y th«ng b¸o ra mµn h×nh dßng ch÷ KHONG THE - NÕu cã thÓ, h·y viÕt ra mµn h×nh c¸c thµnh phè lÇn lît ®i trªn hµnh tr×nh nµy. Bµi 39. Ngßi b¸n hµng A chØ cã M tê tiÒn víi mÖnh gi¸ lÇn lît lµ A[1], A[2], . . ., A[M] ®ång. Ngêi mua B chØ cã N tê tiÒn, N<=30 víi mÖnh gi¸ lÇn lît lµ B[1], B[2], . . ., B[N]; M, N <=50, c¸c sè A[i] vµ B[j] - 10 – Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

®Òu lµ nguyªn d¬ng. H·y t×m sè nguyªn d¬ng P lín nhÊt cã thÓ ®îc sao cho nÕu B mua kh«ng qu¸ P ®ång, A vÉn cã thÓ b¸n ®óng ®îc sè tiÒn ®ã b»ng c¸ch chØ sö dông c¸c tê tiÒn nãi trªn cña c¶ hai ngêi. D÷ liÖu vµo ®îc cho bëi file INP.BL trong ®ã dßng thø nhÊt ghi hai sè nguyªn d¬ng M, N, dßng thø 2 ghi M sè nguyªn d¬ng A[1], . ., A[M], dßng thø 3 ghi N sè nguyªn d¬ng B[1], . ., B[N]. Th«ng b¸o sè P ra mµn h×nh. Bµi 40. NhËp tõ bµn phÝm sè thùc d¬ng R. H·y t×m c¸ch biÓu diÔn R thµnh tæng c¸c sè thùc d¬ng R1, . ., Rk, c¸c Ri<=4, sao cho R còng b»ng tÝch cña R1, . ., Rk. KÕt qu¶ ghi ra mµn h×nh c¸c sè R1, . ., Rk t×m ®îc. Bµi 41. NhËp tõ bµn phÝm sè nguyªn d¬ng N<=30000. H·y t×m c¸ch biÓu diÔn N thµnh tæng c¸c sè nguyªn d¬ng A1, . . , Ak sao cho tÝch c¸c sè A1, . ., Ak lµ lín nhÊt cã thÓ ®îc. KÕt qu¶ ghi ra mµn h×nh tÝch c¸c sè Ai. Bµi 42. Mét thµy gi¸o gÆp N häc sinh cã tªn 1, 2, . ., N. Häc sinh i cã mÆt lóc T[i] vµ sÏ gÆp thµy trong kho¶ng thêi gian C[i]. Thµy gi¸o sÏ gÆp lÇn lît tõ häc sinh 1 ®Õn häc sinh N, nÕu häc sinh i ®Õn vµo giê T[i] nhng thµy cha gÆp xong c¸c häc sinh 1, 2, . ., i-1 th× häc sinh i ph¶i ®îi ®Õn lît m×nh. Gi¶ sö thµy gi¸o b¾t ®Çu s½n sµng gÆp häc sinh tõ thêi ®iÓm quy íc lµ 0. H·y tÝnh xem t¹i thêi ®iÓm nµo thµy gi¸o gÆp xong tÊt c¶ N häc sinh vµ ghi ra mµn h×nh. C¸c sè N, C[1], . ., C[N], T[1], . ., T[N] ®Òu lµ nguyªn d¬ng vµ cã thÓ nhËp tõ file hoÆc tõ bµn phÝm. KÕt qu¶ th«ng b¸o ra mµn h×nh. Bµi 43. Cã N ngêi cã tªn t¬ng øng lµ 1, 2, . ., N vµ t×nh tr¹ng quen biÕt cña N ngêi nµy ®îc cho bëi m¶ng ®èi xøng A[1..N,1..N] trong ®ã A[i,j]=A[j,i]=1 nÕu i quen j vµ b»ng 0 nÕu i kh«ng quen j. H·y xÐt xem liÖu cã thÓ chia N ngêi ®ã thµnh 2 nhãm mµ trong mçi nhãm, hai ngêi bÊt kú ®Òu kh«ng quen nhau? D÷ liÖu vµo ®îc cho bëi file INP.BL trong ®ã dßng thø nhÊt ghi sè nguyªn d¬ng N<=100, trong N dßng tiÕp theo, dßng thø i ghi N sè A[i,1], . ., A[i,N]. KÕt qu¶ ghi ra file OUT.BL nh sau: - NÕu kh«ng cã thÓ, h·y th«ng b¸o ra mµn h×nh dßng ch÷ KHONG THE - NÕu cã thÓ, h·y viÕt ra mµn h×nh hai dßng, dßng thø nhÊt tªn nh÷ng ngêi thuéc nhãm 1, dßng thø hai tªn nh÷ng ngêi thuéc nhãm 2. Bµi 44. Trªn trôc sè cho N ®o¹n th¼ng [Ai, Bi], 1<=i<=N, mµ Ai vµ Bi lµ to¹ ®é cña c¸c ®iÓm ®Çu mót ®o¹n i trªn trôc sè. Cho mét ®iÓm M víi to¹ ®é X. H·y xÐt xem t×nh huèng nµo trong hai t×nh huèng sau x¶y ra:

- 11 – Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

1. M kh«ng thuéc ®o¹n nµo trong sè N ®o¹n trªn, khi ®ã cÇn th«ng b¸o râ ®o¹n lín nhÊt chøa M kh«ng cã ®iÓm trong chung (cã thÓ chung ®Çu mót) víi N ®o¹n nãi trªn. 2. M thuéc mét sè ®o¹n trong sè N ®o¹n trªn, khi ®ã cÇn th«ng b¸o râ bao nhiªu ®o¹n vµ nh÷ng ®o¹n nµo. C¸c sè N, X vµ Ai, Bi nhËp tõ file hoÆc bµn phÝm. KÕt qu¶ th«ng b¸o ra mµn h×nh. Bµi 45. Mét sè nguyªn d¬ng N rÊt lín cã thÓ ®îc cho bëi sè nguyªn d¬ng P, P sè nguyªn d¬ng A1, . ., AP vµ P x©u ký tù chØ gåm c¸c ch÷ sè thËp ph©n S1, . ., SP. Khi ®ã N sÏ nhËn ®îc b»ng c¸ch viÕt S1 liªn tiÕp A1 lÇn råi S2 liªn tiÕp A2 lÇn, . ., SP AP lÇn VÝ dô víi P=3, A1=3, S1=123, A2=4, S2=0, A3=2, S3=45 th× ta cã N = 12312312300004545 Gi¶ sö sè N ®îc cho nh vËy vµ cho mét sè nguyªn d¬ng K kh«ng vît qu¸ sè ch÷ sè cña N, h·y t×m c¸ch g¹ch ®i K ch÷ sè cña N ®Ó nhËn ®îc mét sè cã gi¸ trÞ nhá nhÊt. C¸c sè P, K, A1, . ., AP, c¸c x©u S1, . ., SP cã thÓ nhËp tõ file hoÆc tõ bµn phÝm. Th«ng b¸o sè nhËn ®îc ra mµn h×nh. Bµi 46. NhËp tõ bµn phÝm mét x©u ký tù S. Th«ng b¸o ra mµn h×nh x©u X ng¾n nhÊt sao cho S lµ ghÐp cña mét sè lÇn liªn tiÕp cña X (cã thÓ X=S). Bµi 47. BiÕt d¹ng nhÞ ph©n B1B2 . . BM cña mét sè nguyªn d¬ng N mµ M rÊt lín do ®ã ta kh«ng thÓ chuyÓn nã thµnh d¹ng thËp ph©n mét c¸ch th«ng thêng. H·y t×m phÇn d cña phÐp chia N cho 15 trong hÖ thËp ph©n. D¹ng nhÞ ph©n cña sè N nhËp tõ bµn phÝm nh mét x©u ký tù chØ gåm c¸c ký tù 0 vµ 1. H·y th«ng b¸o ra mµn h×nh kÕt qu¶. Bµi 48. Mét nhãm gåm N ngêi d¸nh sè tõ 1 ®Õn N (N<=100) ngåi quanh mét bµn trßn theo thø tù tõ 1 ®Õn N theo chiÒu kim ®ång hå vµ ch¬i mét trß ch¬i nh sau: mét ngêi nµo ®ã b¾t ®Çu ®Õm tõ sè 1, ngêi tiÕp theo (theo chiÒu kim ®ång hå) ®Õm sè 2, cø tiÕp tôc nh vËy cho tíi khi ai ®Õm ®Õn sè S th× ra khái bµn. TiÕp tôc, ngêi ngåi c¹nh ®ã l¹i b¾t ®Çu ®Õm tõ sè 1 cho tíi khi ai ®Õm ®Õn sè S th× l¹i ra khái bµn, . . . NhËp tõ bµn phÝm c¸c sè nguyªn d¬ng N, S vµ L. 3.1. NÕu b¾t ®Çu ®Õm tõ ngêi sè 1 th× ngêi nµo cßn l¹i cuèi cïng? 3.2. NÕu ngêi cßn l¹i cuèi cïng lµ ngêi thø L th× b¾t ®Çu ®Õm tõ ngêi nµo? C¸c c©u tr¶ lêi viÕt ra mµn h×nh. Bµi 49. NhËp hai sè nguyªn d¬ng M vµ N. In ra mäi nghiÖm nguyªn kh«ng ©m cña ph¬ng tr×nh X1 + X2 + . . + XN = M - 12 – Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

Bµi 50. ViÕt ch¬ng tr×nh lµm c¸c viÖc sau: - NhËp mét sè thËp ph©n bÊt kú kh«ng qu¸ 1000000 vµ cã kh«ng qu¸ 6 sè lÎ sau dÊu ph¶y. - ViÕt ra mµn h×nh d¹ng viÕt cña sè thËp ph©n nµy. VÝ dô nÕu nhËp sè 13.24, ph¶i th«ng b¸o ra mµn h×nh dßng ch÷ mêi ba phÈy hai m¬i bèn. Bµi 51. ViÕt ch¬ng tr×nh lµm c¸c viÖc sau: - NhËp tõ bµn phÝm mét x©u ký tù S ®é dµi kh«ng qu¸ 40 chØ gåm c¸c ký tù 0 vµ 1. - BiÕn ®æi x©u S thµnh x©u S1 nh sau: ®äc tõ tr¸i sang ph¶i x©u S, thay nh÷ng x©u con chØ gåm c¸c ký tù 1 liªn tiÕp gi÷a c¸c ký tù 0 bëi sè thËp ph©n nhËn nã lµm d¹ng nhÞ ph©n vµ thay nh÷ng x©u con chØ gåm c¸c ký tù 0 liªn tiÕp gi÷a c¸c ký tù 1 bëi d¹ng nhÞ ph©n cña ®é dµi cña nã, gi÷a c¸c ®o¹n nµy ®Æt ký tù rçng ng¨n c¸ch. Th«ng b¸o ra mµn h×nh x©u S1. VÝ dô nÕu S = 000111100 th× S1 = 11 15 10. - Gi¶ sö biÕt S1 ®îc nhËp tõ bµn phÝm, h·y kh«i phôc l¹i x©u S vµ viÕt ra mµn h×nh. Bµi 52. ViÕt ch¬ng tr×nh lµm c¸c viÖc sau: 1. NhËp tõ file text DT.TXT sè nguyªn d¬ng N ghi ë dßng thø nhÊt, N<=100 vµ m¶ng A[1..N,1..N] lµ ma trËn kÒ cña mét ®å thÞ v« híng, dßng thø i+1 cña file ghi dßng thø i cña m¶ng A. 2. H·y xÐt xem ®å thÞ ®ã cã bao nhiªu thµnh phÇn liªn th«ng vµ mçi thµnh phÇn liªn th«ng gåm c¸c ®Ønh nµo. 3. NhËp tõ bµn phÝm hai sè nguyªn d¬ng U vµ V, 1<=U,V<=N, lµ hai ®Ønh cña ®å thÞ. H·y th«ng b¸o ra mµn h×nh cã hay kh«ng ®êng ®i tõ U ®Õn V vµ ®êng ®i ®ã ®i qua nh÷ng ®Ønh nµo. Bµi 53. Cho mét h×nh ch÷ nhËt kÝch thíc MxN, M, N nguyªn d¬ng. H×nh nµy ®îc chia thµnh MxN « vu«ng ®¬n vÞ b»ng c¸c ®êng song song víi c¸c c¹nh. Trªn « vu«ng [i,j] (dßng i cét j) ghi mét sè nguyªn d¬ng A[i,j]<=30000. 1. NhËp tõ file text MANG.TXT sè nguyªn d¬ng M, N ghi ë dßng thø nhÊt, M, N<=100 vµ m¶ng A[1..M,1..N] c¸c sè nguyªn d¬ng, dßng thø i+1 cña file ghi dßng thø i cña m¶ng. 2. Tõ mét « ta cã thÓ di chuyÓn ®Õn mét « kÒ c¹nh víi nã nÕu trÞ tuyÖt ®èi cña hiÖu hai sè ghi trong hai « ®ã lµ mét sè nguyªn tè. Tõ mét « ta cã thÓ ®i ®Õn mét « kh¸c cña m¶ng b»ng mét d·y c¸c di chuyÓn nh vËy. Mét tËp hîp K c¸c « ®îc gäi lµ mét miÒn nÕu gi÷a hai « bÊt kú cña K ®Òu cã thÓ ®i ®Õn ®îc nhau nhng tõ mét « bÊt kú thuéc K ta kh«ng thÓ ®i ®Õn mét « kh«ng thuéc K. H·y th«ng b¸o ra mµn h×nh sè miÒn vµ mçi miÒn gåm c¸c « nµo (cã thÓ ghi ra file). 3. NhËp tõ bµn phÝm bèn sè nguyªn d¬ng U, V, X, Y, U, X <= M, V, Y <= N. H·y th«ng b¸o ra mµn h×nh liÖu cã thÓ ®i tõ « [U,V] ®Õn « [X,Y] ®îc kh«ng; nÕu ®i ®îc th× ®êng ®i ®ã qua c¸c « nµo (cã thÓ ghi ra file). - 13 – Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

Bµi 54. NhËp tõ bµn phÝm hai sè nguyªn d¬ng M vµ N. H·y th«ng b¸o ra mµn h×nh xem cã thÓ nhËn ®îc M b»ng c¸ch g¹ch ®i tõ N mét sè ch÷ sè kh«ng? Bµi 55. Trªn mÆt ph¼ng to¹ ®é mét h×nh ch÷ nhËt víi c¸c c¹nh song song víi c¸c trôc to¹ ®é ®îc x¸c ®Þnh bëi hai ®Ønh ®èi t©m. Trong Bµi nµy, mäi h×nh ch÷ nhËt ®Òu cã c¸c c¹nh song song víi c¸c trôc to¹ ®é. 1. NhËp tõ file CN.TXT sè nguyªn d¬ng N<=30 ghi ë dßng thø nhÊt. Trong N dßng tiÕp theo mçi dßng ghi 4 sè lµ to¹ ®é cña hai ®Ønh ®èi t©m cña mét h×nh ch÷ nhËt, c¸c sè nµy lµ nguyªn cã gi¸ trÞ tuyÖt ®èi kh«ng qu¸ 100. 2. H·y x¸c ®Þnh h×nh ch÷ nhËt nhá nhÊt S chøa N h×nh ch÷ nhËt ®· cho. Th«ng b¸o ra mµn h×nh 4 sè lµ to¹ ®é cña hai ®Ønh ®èi t©m cña h×nh ch÷ nhËt nµy. 3. T×m diÖn tÝch phÇn cña h×nh S kh«ng n»m trong h×nh ch÷ nhËt nµo trong sè N h×nh trªn. Th«ng b¸o kÕt qu¶ ra mµn h×nh. Bµi 56. NhËp tõ bµn phÝm mét sè nguyªn d¬ng N<=3000000 vµ in ra mµn h×nh sè ch÷ sè 1 cña biÓu diÔn sè N trong hÖ nhÞ ph©n. Bµi 57. Ta x©y dùng mét d·y v« h¹n chØ gåm c¸c ch÷ sè 0, 1, 2 qua c¸c bíc nh sau: - T¹i bíc 0, phÇn ®Çu cña d·y lµ 0. - NÕu t¹i bíc k ta ®· x©y dùng ®îc phÇn ®Çu cña d·y lµ a[1]a[2] . . . a[m], th× t¹i bíc k+1, phÇn ®Çu cña d·y lµ a[1]a[2] . . . a[m]b[1]b[2] . . . b[m] mµ víi 1 <= i <= m, b[i] = a[i]+1 (mod 3). Nh vËy d·y ®ã ®îc x©y dùng nh sau: 0 ⇒ 01 ⇒ 0112 ⇒ 01121220 ⇒ 0112122012202001 ⇒ . . . . . NhËp tõ bµn phÝm sè nguyªn d¬ng N<=3000000000. H·y in ra mµn h×nh ch÷ sè thø N cña d·y nµy. Bµi 58. NhËp t¸m sè thùc X1, Y1, X2, Y2, AX, AY, CX, CY trong ®ã (X1, Y1) lµ to¹ ®é cña ®iÓm M1, (X2, Y2) lµ to¹ ®é cña ®iÓm M2, (AX, AY) vµ (CX, CY) t¬ng øng lµ to¹ ®é cña hai ®Ønh ®èi t©m A, C cña mét h×nh ch÷ nhËt ABCD cã c¸c c¹nh song song víi c¸c trôc to¹ ®é. H·y tr¶ lêi ra mµn h×nh vÞ trÝ t¬ng ®èi cña ®o¹n M1M2 ®èi víi h×nh ch÷ nhËt ABCD thuéc trêng hîp nµo trong ba trêng hîp sau: - Trêng hîp 1: M1M2 n»m ngoµi h×nh ch÷ nhËt (mäi ®iÓm cña ®o¹n n»m ngoµi h×nh ch÷ nhËt) - Trêng hîp 2: M1M2 n»m trong h×nh ch÷ nhËt (mäi ®iÓm cña ®o¹n n»m trong h×nh ch÷ nhËt cã thÓ trªn biªn) - Trêng hîp 3: Cã ®iÓm cña M1M2 n»m trong h×nh ch÷ nhËt vµ cã ®iÓm cña M1M2 n»m ngoµi h×nh ch÷ nhËt. Bµi 59. NhËp tõ bµn phÝm mét sè nguyªn d¬ng N<=1000 vµ in ra mµn h×nh x©u ký tù S ®é dµi N chØ gåm c¸c ký tù 0 hay 1 sao cho S kh«ng cã x©u con nµo xuÊt hiÖn liªn tiÕp 3 lÇn trong nã. - 14 – Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

Bµi 60. ViÕt ch¬ng tr×nh lµm c¸c viÖc sau: - NhËp mét sè nguyªn d¬ng N<=200 vµ hai d·y N sè nguyªn A[1], . . ., A[N]; B[1], . . ., B[N] (cã thÓ tõ file hoÆc tõ bµn phÝm). - Th«ng b¸o ra mµn h×nh: hai d·y ®ã cã cïng c¸c sè h¹ng nh nhau vµ chØ kh¸c nhau vÒ thø tù s¾p xÕp kh«ng. Bµi 61. Cã N ®iÓm ®¸nh sè tõ 1 ®Õn N, N<=100, vµ N sè nguyªn d¬ng A1, A2, . . ., AN. H·y t×m c¸ch nèi c¸c cÆp ®iÓm bëi c¸c ®o¹n th¼ng sao cho víi mäi i, 1 <= i <= N, ®iÓm i ®îc nèi víi ®óng Ai ®iÓm. Ch¬ng tr×nh ph¶i nhËp sè N, N sè A[1], . . ., A[N] vµ viÕt ra mµn h×nh hoÆc file c¸ch nèi mçi ®iÓm víi c¸c ®iÓm kh¸c. Bµi 62. NhËp tõ bµn phÝm hai sè nhÞ ph©n X vµ Y. H·y in ra mµn h×nh sè nhÞ ph©n Z cã gi¸ trÞ lín nhÊt cã thÓ ®îc mµ Z nhËn ®îc tõ X b»ng c¸ch g¹ch ®i mét sè ch÷ sè nhÞ ph©n nµo ®ã vµ Z còng nhËn ®îc tõ Y b»ng c¸ch g¹ch ®i mét sè ch÷ sè nhÞ ph©n nµo ®ã. Bµi 63. Cho n ®éi bãng thi ®Êu theo thÓ thøc mçi ®éi ®Òu ®Êu víi n-1 ®éi cßn l¹i. Ta gäi mét giai ®o¹n cña gi¶i lµ mét b¶ng trong ®ã ghi râ tõng cÆp ®éi ®· ®Êu víi nhau hay cha. ViÕt ch¬ng tr×nh lµm c¸c viÖc sau: 1. NhËp tõ bµn phÝm sè n c¸c ®éi bãng, n > 2. 2. Chän c¸ch thÓ hiÖn mét giai ®o¹n cña gi¶i vµ nhËp mét giai ®o¹n nµo ®ã tõ bµn phÝm. 3. T¹i giai ®o¹n ®ã cña gi¶i, h·y t×m vµ in ra ba ®éi bãng hoÆc ®Òu ®· ®Êu víi nhau hoÆc ®Òu cha ®Êu víi nhau nÕu cã ba ®éi nh vËy. NÕu kh«ng cã, h·y th«ng b¸o lµ kh«ng cã. Bµi 64. Mét h·ng bu«n cã n cöa hiÖu vµ n ngêi b¸n hµng. Mçi ngêi b¸n hµng cã thÓ ®i trùc tiÕp ®Õn mét sè cöa hiÖu b»ng « t« buýt. H·y viÕt ch¬ng tr×nh gi¶i Bµi to¸n sau: 1. NhËp tõ bµn phÝm sè n > 3. 2. Sinh ngÉu nhiªn mét b¶ng thÓ hiÖn víi mçi ngêi b¸n hµng mét sè cöa hiÖu mµ ngêi ®ã cã thÓ ®i tíi trùc tiÕp b»ng « t« buýt. 3. H·y gióp chñ h·ng ph©n bæ n ngêi b¸n hµng lµm ë n cöa hiÖu sao cho sè ngêi ®i trùc tiÕp tíi n¬i lµm viÖc b»ng « t« buýt lµ nhiÒu nhÊt. In ra mµn h×nh ph©n c«ng ®ã vµ th«ng b¸o cã bao nhiªu ngêi ®i trùc tiÕp tíi n¬i lµm viÖc b»ng « t« buýt. Bµi 65. Trong m«t gi¶i bãng ®¸ cã n ®éi tham gia,mçi ®éi ®Òu cã s©n bãng riªng vµ c¸c trËn ®Êu chØ diÔn ra trªn c¸c s©n cña n ®éi nµy. Trong gi¶i, hai ®éi gÆp nhau ®óng mét lÇn vµ trËn ®Êu diÔn ra trªn s©n cña mét trong hai ®éi. Gi¶i ®îc tæ chøc theo c¸c vßng ®Êu, trong mçi vßng, c¸c trËn diÔn ra ®ång thêi. CÇn thu xÕp lÞch ®Êu sao cho sè vßng Ýt nhÊt cã thÓ ®îc vµ trong toµn gi¶i, sè trËn ®Êu trªn s©n nhµ vµ sè trËn ®Êu trªn s©n kh¸ch cña mçi ®éi kh«ng chªnh nhau qu¸ 1. - 15 – Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

H·y nhËp tõ bµn phÝm sè ®éi bãng n vµ in lÞch thi ®Êu tõng vßng ghi râ tõng trËn ®Êu ®éi nµo gÆp ®éi nµo vµ trªn s©n nµo ra file. Bµi 66. Cho n ®iÓm kh¸c nhau trªn mÆt ph¼ng to¹ ®é vu«ng gãc pi = (xi,yi), 1<=i<=n. XÐt ®êng gÊp khóc lÇn lît nèi c¸c ®iÓm p1, p2, ...,pn, p1. H·y tr¶ lêi c¸c c©u hái sau ra mµn h×nh: 1. §êng gÊp khóc nµy cã tù c¾t kh«ng, tøc lµ cã hay kh«ng c¸c ®Ønh pi vµ pj sao cho ®o¹n (pi, pi+1) c¾t ®o¹n (pj, pj1) t¹i ®iÓm kh«ng lµ c¸c ®Çu mót. 2. NÕu ®êng gÊp khóc kh«ng lµ tù c¾t th× nã cã ph¶i lµ mét ®a gi¸c låi n ®Ønh hay kh«ng? 3. NÕu kh«ng, h·y t×m trong sè n ®iÓm trªn c¸c ®iÓm lËp thµnh mét ®a gi¸c låi bäc tÊt c¶ n ®iÓm. Bµi 67. Cho mét b¶ng ch÷ nhËt chia thµnh c¸c « vu«ng, mét chiÒu m «, mét chiÒu n «, t¹i « vu«ng [i,j] ghi sè nguyªn A[i,j]. Ta gäi mét h×nh ch÷ nhËt trong b¶ng nµy lµ tËp hîp c¸c « [i,j] mµ 1<=p<=i<=q<=n, 1<=r<=j<=s<=n víi p, q, r, s nµo ®ã vµ c¸c sè ghi trong c¸c « nµy gièng nhau. H·y tim h×nh ch÷ nhËt trong b¶ng cã diÖn tÝch lín nhÊt. D÷ liÖu vµo ®îc cho bëi file text MANG.TXT trong ®ã sè nguyªn d¬ng M, N ghi ë dßng thø nhÊt, M, N<=100 vµ dßng thø i+1 cña file ghi dßng thø i cña m¶ng A. Bµi 68. §Ó x¸c ®Þnh mét h×nh ch÷ nhËt cã c¸c c¹nh song song víi c¸c trôc to¹ ®é vu«ng gãc, ta chØ cÇn x¸c ®Þnh to¹ ®é cña hai ®Ønh ®èi t©m. Ta cè ®Þnh mét hÖ to¹ ®é vu«ng gãc trªn mÆt ph¼ng. Khi ®ã mét h×nh ch÷ nhËt ®îc cho bëi bèn sè a,b,c,d trong ®ã (a,b) vµ (c,d) lµ to¹ ®é cña hai ®Ønh ®èi t©m cña h×nh ch÷ nhËt ®ã. Cho N h×nh ch÷ nhËt, h×nh thø i ®îc cho bëi bèn sè (ai, bi, ci, di) víi ai, bi, ci, di lµ c¸c sè nguyªn, 0<=i<=N. H·y tr¶ lêi hai c©u hái sau: 1. Sè lín nhÊt c¸c h×nh ch÷ nhËt kh«ng cã ®iÓm chung lµ bao nhiªu? 2. LÊy mét h×nh ch÷ nhËt (a, b, c, d) bÊt kú víi a, b, c, d nguyªn, N h×nh ch÷ nhËt ®· cho cã phñ kÝn h×nh ch÷ nhËt nµy kh«ng? N h×nh ch÷ nhËt ®îc cho b»ng mét file c¸c string chunhat.dat trong ®ã dßng thø nhÊt ghi sè N<=20, N dßng kÕ tiÕp ghi mçi dßng mét h×nh ch÷ nhËt ®îc cho bëi bèn sè nguyªn, gi÷a hai sè cã mét dÊu trèng ng¨n c¸ch. Dßng thø n+2 ghi to¹ ®é mét h×nh ch÷ nhËt ®Ó xem xÐt trong c©u 2. KÕt qu¶ ghi ra mµn h×nh. Bµi 69. Trong mét thµnh phè cã kh«ng qu¸ 200 ngêi gåm N lo¹i c«ng d©n, vµ cã N lo¹i ý kiÕn kh¸c nhau vÒ mét vÊn ®Ò liªn quan ®Õn lîi Ých sèng cßn cña mçi c d©n. Mét c«ng d©n cã thÓ thuéc mét sè lo¹i c«ng d©n, vÝ dô mét c«ng d©n cã thÓ thuéc lo¹i thÝch nghe nh¹c, lo¹i thÝch uèng bia, lo¹i ®Ò nghÞ cÊm ®i xe m¸y .... vµ cã thÓ - 16 – Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

cã nhiÒu ý kiÕn trong sè N ý kiÕn. H·y chän ra N ngêi kh¸c nhau sao cho mçi lo¹i c«ng d©n ®Òu cã ®¹i diÖn trong sè ®îc chän vµ mçi lo¹i ý kiÕn ®Òu cã ngêi trong sè ®îc chän ñng hé. D÷ liÖu ®îc cho bëi mét file text víi tªn city.dat trong ®ã dßng thø nhÊt ghi sè nguyªn d¬ng N, tiÕp theo víi mçi c«ng d©n, mçi c«ng d©n ®îc ghi tªn gåm c¸c ch÷ c¸i la tinh liÒn nhau ch÷ ®Çu tiªn viÕt hoa, c¸c ch÷ sau viÕt thêng, tiÕp theo lµ c¸c sè chØ lo¹i ý kiÕn, gi÷a tªn vµ lo¹i ý kiÕn, hai lo¹i ý kiÕn cña mét tªn c¸ch nhau b»ng mét ký tù rçng, hai lo¹i c«ng d©n c¸ch nhau b»ng mét dßng rçng. H·y viÕt ch¬ng tr×nh lµm c¸c viÖc sau: 1. In ra danh s¸ch mäi c«ng d©n cña thµnh phè, mçi ngêi ®óng mét lÇn theo thø tù a, b, c, ... 2. In ra mµn h×nh Ýt nhÊt mét danh s¸ch n ngêi kh¸c nhau ®¹i diÖn ®ñ n lo¹i c«ng d©n vµ n lo¹i ý kiÕn, mçi ngêi ghi râ ®¹i diÖn cho lo¹i c«ng d©n nµo vµ lo¹i ý kiÕn nµo. NÕu kh«ng thÓ chän ®îc, h·y th«ng b¸o ra mµn h×nh lµ kh«ng thÓ chän ®îc. Bµi 70. Mét ngêi cã n ®ång muèn mua hµng trong sè k lo¹i hµng cã thÓ cã. §¬n gi¸ lo¹i hµng thø i lµ g[i]. H·y liÖt kª ra cho ngêi ®ã mäi c¸ch kh¸c nhau cã thÓ cã ®Ó ph©n bæ n ®ång thµnh c¸c kho¶n t[1], ..., t[k] trong ®ã kho¶n t[i] dïng ®Ó mua lo¹i hµng i sao cho sè lîng lo¹i hµng thø i mua ®îc ph¶i nguyªn (tøc lµ t[i] ph¶i lµ béi cña g[i]). C¸c sè n, k lµ nguyªn d¬ng, c¸c sè t1, ..., tk lµ c¸c sè nguyªn kh«ng ©m. D÷ liÖu ®îc ghi vµo mét file c¸c sè nguyªn mang tªn mua.dat. Sè thø nhÊt lµ n, sè thø hai lµ k, k sè cßn l¹i lÇn lît lµ c¸c ®¬n gi¸ cña c¸c lo¹i hµng g1, ..., gk. ViÕt ra mµn h×nh c¸c c¸ch ph©n bæ cã thÓ cã. Mçi c¸ch ph©n bæ ghi thµnh hai dßng: mét dßng cho c¸c t[i] vµ mét dßng cho sè lîng hµng t¬ng øng mua ®îc. Bµi 71. Cho mét b¶ng vu«ng c¹nh dµi N ®¬n vÞ, N nguyªn d¬ng ®îc chia thµnh NxN « vu«ng b»ng nhau bëi c¸c ®êng song song víi c¸c c¹nh cña b¶ng. Trªn « [i,j] cña b¶ng, 1<=i,j<=N ghi mét sè nguyªn d¬ng A[i,j]. Tõ mét « vu«ng ta cã thÓ di chuyÓn ®Õn mét trong bèn « kÒ c¹nh víi nã nÕu trÞ tuyÖt ®èi cña hiÖu c¸c sè ghi trªn hai « ®ã lµ mét sè nguyªn tè, mçi lÇn di chuyÓn nh vËy mÊt mét ®¬n vÞ thêi gian. Tõ mét « vu«ng ta còng cã thÓ di chuyÓn ®Õn mét trong bèn « kÒ c¹nh víi nã khi trÞ tuyÖt ®èi cña hiÖu c¸c sè ghi trªn hai « ®ã kh«ng lµ mét sè nguyªn tè nhng mçi lÇn di chuyÓn nh vËy mÊt KxNxN ®¬n vÞ thêi gian nÕu di chuyÓn ®ã lµ di chuyÓn thø K thuéc lo¹i nµy trªn mét hµnh tr×nh ®i qua mét sè «. ViÕt ch¬ng tr×nh nhËp tõ file v¨n b¶n INP.TXT m¶ng A. File nµy cã N+1 dßng (N<=15), dßng thø i, 1<=1<=N, ghi N sè nguyªn d¬ng kh«ng lín h¬n 30000 lÇn lît lµ c¸c sè A[i,1], A[i,2], . . ., A[i,N], dßng thø N+1 ghi bèn sè U, V, X, T, 1<= U, V, X, T <=N. T×m mét c¸ch ®i tõ « [U,V] ®Õn « [X,T] víi thêi gian Ýt nhÊt. Ghi ra file OUT.TXT d·y c¸c « liªn tiÕp trªn hµnh tr×nh ®ã b¾t ®Çu tõ « [U,V] kÕt thóc b»ng

- 17 – Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

« [X,T], mçi « ghi trªn mét dßng gåm hai sè lµ sè dßng vµ sè cét cña nã. Bµi 72. Cho mét h×nh vu«ng cã c¹nh ®é dµi N nguyªn d¬ng. B¶ng nµy ®îc chia thµnh N x N « vu«ng b»ng nhau b»ng c¸c ®êng song song víi c¸c c¹nh h×nh vu«ng. Trªn mçi « vu«ng ghi mét sè nguyªn d¬ng <=10000. Tõ mét « X ta cã thÓ di chuyÓn ®ªn mét « Y kÒ c¹nh víi nã nÕu sè ghi trong « X b»ng sè trong « Y céng víi mét sè chÝnh ph¬ng nguyªn d¬ng. Cho tríc hai « [x,y] vµ [z,t]. Mét ®êng ®i tõ « [x,y] ®Õn « [z,t] lµ mét d·y c¸c di chuyÓn qua c¸c « kÒ c¹nh (theo quy t¾c trªn) b¾t ®Çu tõ « [x,y] vµ kÕt thóc t¹i « [z,t]. ¤ kh¸c víi c¸c « [x,y] vµ [z,t] mµ mäi ®êng ®i tõ « [x,y] ®Õn « [z,t] ®Òu ph¶i ®i qua « ®ã ®îc gäi lµ « ®Æc biÖt. - NhËp d÷ liÖu tõ file INP.TXT trong ®ã dßng thø nhÊt ghi 5 sè nguyªn d¬ng lÇn lît lµ c¸c sè N, x, y, z, t, N<=100. Dßng thø i+1, 1<=i<=N, ghi N sè trong dßng thø i cña h×nh vu«ng theo thø tù tõ tr¸i sang ph¶i. Kh«ng ph¶i kiÓm tra tÝnh ®óng ®¾n cña d÷ liÖu. - Ghi ra file OUT.TXT c¸c « ®Æc biÖt, mçi dßng ghi hai sè lÇn lît lµ sè dßng vµ s« cét vµ sè cét cña «. NÕu kh«ng cã ®êng ®i tõ « [x,y] ®Õn « [z,t] hoÆc kh«ng cã « ®Æc biÖt nµo th× ghi th«ng b¸o Khong co VÝ dô víi file INP.TXT 4 1 31 27 27 26 8 22 12 20 file OUT.TXT sÏ lµ 3 3 3 4 Víi file INP.TXT 4 1 1 29 29 26 8 19 12 20 file OUT3.TXT sÏ lµ Khong co

1 26 22 13 14

4 1 5 4 3

4

1 26 19 14 14

3 1 5 7 5

4

Bµi 73. Cho hai x©u ký tù X vµ Y. §Ó biÕn ®æi mét x©u, ta cã thÓ dïng mét trong ba lo¹i biÕn ®æi sau: B1(m,c). Thªm vµo tríc ký tù thø m cña x©u ký tù c. B2(m,c). Thay ký tù thø m cña x©u bëi ký tù c. B3(m). Xo¸ ký tù thø m cña x©u. §äc tõ file INP.BL1 hai x©u ký tù X vµ Y, trong ®ã dßng thø nhÊt/hai viÕt x©u X/Y.

- 18 – Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

H·y t×m mét sè Ýt nhÊt c¸c biÕn ®æi thuéc ba lo¹i trªn ®Ó biÕn X thµnh Y. Qu¸ tr×nh biÕn ®æi ®îc ghi ra file OUT.BL1 theo quy c¸ch sau: nÕu c¸c biÕn ®æi dïng lµ S1, S2, . ., Sk vµ qu¸ tr×nh biÕn ®æi lµ X =S1=> X1 =S1=> X2 . . Xk-1 =Sk=> Xk=Y th× file OUT.BL1 sÏ cã d¹ng: X S1 X1 S2 X2 ... Sk Y Bµi 74. Cã N viÖc ®¸nh sè tõ 1 ®Õn N, N<=20. ViÖc thø i cÇn lµm trong C[i] ®¬n vÞ thêi gian vµ thu ®îc hiÖu qu¶ B[i]. Gi¶ sö ta chØ cã A ®¬n vÞ thêi gian lµm viÖc vµ t¹i mçt thêi ®iÓm chØ cã thÓ lµm kh«ng qu¸ mét viÖc. H·y chän mét sè viÖc lµm trong A ®¬n vÞ thêi gian ®Ó cã hiÖu qu¶ lín nhÊt. D÷ liÖu vµo ®îc cho bëi file INP.BL3 trong ®ã dßng thø nhÊt ghi sè N, dßng thø hai ghi N sè B[1], . ., B[N], dßng thø ba ghi N sè C[1], . ., C[N]. KÕt qu¶ ghi ra file OUT.BL3 gåm hai dßng: dßng thø nhÊt ghi hiÖu qu¶, dßng thø hai ghi c¸c c«ng viÖc lµm. Bµ× 75. Cho mét h×nh vu«ng cã c¹nh ®é dµi N nguyªn d¬ng, N<=100 ®îc chia thµnh NxN « vu«ng b»ng nhau b»ng mét líi ®êng song song víi c¸c c¹nh. §Ó ®Þnh vÞ, ta quy íc h×nh vu«ng ®îc ®Æt trong gãc phÇn t thø nhÊt (X>=0, Y>=0) cña mét hÖ trôc to¹ ®é OXY víi hai ®Ønh n»m trªn hai trôc to¹ ®é vµ mét ®Ønh trïng víi gèc to¹ ®é. Giao ®iÓm cña hai ®êng cña líi ®îc gäi lµ mét nót cã to¹ ®é nguyªn kh«ng ©m (X,Y), 0<=X,Y<=N. Cã tÊt c¶ S= (N+1)2 nót. C¸c nót nµy ®îc ®¸nh sè tõ 1 ®Õn S lÇn lît theo tæng c¸c to¹ ®é, nhá tríc, lín sau. NÕu cïng tæng, thø tù u tiªn theo thµnh phÇn X, Y. Nh vËy tr×nh tù ®¸nh sè c¸c nót lµ nót 1 lµ (0,0), nót 2 lµ (1,0), nót 3 lµ (0,1), nót 4 lµ (0,2), . . . . Cho tríc hai nót cã sè hiÖu t¬ng øng lµ H vµ K, mét ngêi cã thÓ theo c¸c c¹nh (cña líi ®êng) ®Ó ®i tõ H ®Õn K. H·y chän cho ngêi ®ã mét hµnh tr×nh tõ nót H ®Õn nót K sao cho mçi nót trªn hµnh tr×nh kh«ng xuÊt hiÖn qu¸ mét lÇn vµ sao cho sè nót ph¶i ®i qua Ýt nhÊt cã thÓ ®îc. D÷ liÖu vµo nhËp tõ bµn phÝm gåm sè nguyªn d¬ng N vµ hai sè H, K lµ sè hiÖu cña hai nót. KÕt qu¶ ghi ra file OUT.B2, dßng thø nhÊt ghi sè lîng nót cña hµnh tr×nh, dßng thø hai ghi c¸c sè hiÖu cña c¸c nót lÇn lît trªn hµnh tr×nh, b¾t ®Çu tõ H vµ kÕt thóc lµ K, hai sè hiÖu liªn tiÕp c¸ch nhau mét ký tù rçng.

- 19 – Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

Bµi 76. Cã N qu¶ c©n víi c¸c träng lîng t¬ng øng lµ 1kg, 3kg, . . ., 3N-1kg vµ mét c©n bµn. Ta muèn chØ dïng c©n bµn vµ N qu¶ c©n nµy ®Ó c©n tói ®êng cã träng lîng M kg trong mét lÇn c©n. LiÖu ta cã thÓ c©n dîc kh«ng. NhËp tõ bµn phÝm sè nguyªn d¬ng N<=15 vµ sè nguyªn d¬ng M<=100000000. NÕu kh«ng c©n ®îc, ciÕt ra mµn h×nh ch÷ KHONG. NÕu c©n ®îc, viÕt ra mµn h×nh ch÷ CO vµ trong hai dßng tiÕp theo, dßng thø nhÊt viÕt ra sè hiÖu c¸c qu¶ c©n ®Æt cïng phÝa tói ®êng, dßng thø hai viÕt ra sè hiÖu c¸c qu¶ c©n ®Æt t¹i ®Üa c©n phÝa bªn kia. Bµi 77. Cã N c«ng ty cã tªn tõ 1 ®Õn N, N<=10. Gi÷a hai c«ng ty i vµ j cã thÓ cã hoÆc kh«ng cã mèi quan hÖ khèng chÕ thÓ hiÖn bëi sè C[i,j] mµ C[i,j]=0 nÕu i kh«ng khèng chÕ j vµ C[i,j]=1 nÕu i khèng chÕ j. H·y t×m mét d·y gåm nhiÒu c«ng ty kh¸c nhau nhÊt i 1, . ., im sao cho ik khèng chÕ ik+1, 1<=k<m. D÷ liÖu vµo ®îc cho bëi file CT.TXT trong ®ã dßng thø nhÊt ghi sè N, trong N dßng tiÕp theo, dßng thø i ghi c¸c sè C[i,1], . ., C[i,N]. KÕt qu¶ ghi ra mµn h×nh d·y c¸c c«ng ty cÇn t×m. Bµi 78. Mét mª cung lµ mét h×nh ch÷ nhËt cã kÝch thíc MxN, M vµ N nguyªn d¬ng kh«ng lín h¬n 100. Mª cung ®îc chia thµnh c¸c « vu«ng ®¬n vÞ b»ng c¸c ®êng song song víi c¸c c¹nh. Mçi « vu«ng cã thÓ ®i qua hoÆc kh«ng ®i qua ®îc. Tõ mét « vu«ng, ta cã thÓ ®i ®Õn mét « vu«ng kÒ c¹nh víi nã nÕu « vu«ng ®ã cã thÓ ®i qua ®îc. Mét ngêi ®øng ë « vu«ng [K,L] (thuéc dßng K cét L). H·y xÐt xem liÖu ngêi ®ã cã thÓ ®i ra khái mª cung kh«ng? Ngêi ®ã ®i ra ®îc mª cung nÕu ®i ®îc ®Õn mét « thuéc biªn cña mª cung. D÷ liÖu vµo ®îc cho bëi file INP.B1 trong ®ã dßng thø nhÊt ghi bèn sè M, N, K, L. Trong M dßng tiÕp theo, dßng thø I ghi N sè A[I,1], A[I,2], . ., A[I,N] thÓ hiÖn t×nh tr¹ng c¸c « trong vÖt ngang thø I cña mª cung, A[I,J] = 0/1 tuú theo « [I,J] ®i qua ®îc hay kh«ng ®i qua ®îc. KÕt qu¶ ghi ra file OUT.B1 nh sau: Dßng thø nhÊt ghi ch÷ CO hay KHONG tuú theo ngêi ®ã cã thÓ ®i ra hay kh«ng ®i ra « thuéc biªn. NÕu c©u tr¶ lêi lµ CO, tõ dßng thø hai ghi mçi dßng hai sè lµ chØ sè dßng vµ chØ sè cét cña c¸c « lÇn lît ®i qua b¾t ®Çu tõ « [I,J] ®Õn « thuéc biªn. Bµi 79. Cho N ®iÓm trªn mÆt ph¼ng víi c¸c sè hiÖu t¬ng øng lµ 1, 2, . ., N, N<=100. Gi÷a mét sè cÆp ®iÓm cã ®o¹n th¼ng nèi chóng víi nhau sao cho nÕu ®i theo c¸c ®o¹n th¼ng nµy (tõ ®iÓm ®Çu ®Õn ®iÓm cuèi) ta cã thÓ ®i ®îc tõ mét ®iÓm bÊt kú ®Õn mét ®iÓm bÊt kú kh¸c. LiÖu xuÊt ph¸t tõ mét ®iÓm nµo ®ã ta cã thÓ ®i qua mäi ®o¹n nèi mçi ®o¹n ®óng mét lÇn kh«ng? D÷ liÖu vµo ®îc cho bëi file INP.BL trong ®ã dßng thø nhÊt ghi sè nguyªn d¬ng N, trong c¸c dßng tiÕp theo, mçi dßng ghi hai sè nguyªn d¬ng I, J <= N thÓ hiÖn viÖc ®iÓm I ®îc nèi víi ®iÓm J. - 20 – Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

KÕt qu¶ ghi ra file OUT.BL nh sau: - Dßng thø nhÊt ghi sè 1 hay 0 tuú theo cã thÓ hay kh«ng cã thÓ - NÕu dßng thø nhÊt ghi sè 1, tõ dßng thø hai, mçi dßng ghi 10 sè hiÖu cña c¸c ®iÓm lÇn lît trªn hµnh tr×nh cÇn t×m. Bµi 80. Cho mét ®å thÞ N ®Ønh, N<=100, cã ma trËn träng sè kh«ng ©m C vµ víi mäi i, j, C[i,j]<=100. Cho tríc hai ®Ønh U vµ V. H·y t×m ®êng ®i ng¾n nhÊt tõ ®Ønh U ®Õn ®Ønh V. D÷ liÖu vµo ®îc cho bëi file INP.BL trong ®ã dßng thø nhÊt ghi ba sè N, U, V. Trong N dßng tiÕp theo, dßng thø i ghi N sè C[i,1], . ., C[i,N]. KÕt qu¶ ghi ra file OUT.BL nh sau: dßng thø nhÊt ghi ®é dµi ®êng ®i ng¾n nhÊt tõ U ®Õn V; trong c¸c dßng tiÕp theo, mçi dßng ghi mét ®Ønh cña ®êng ®i tõ U ®Õn V lÇn lît theo thø tù trªn hµnh tr×nh tõ U ®Õn V. Bµi 81. Cho d·y gåm N sè nguyªn kh¸c nhau X1, X2,......, XN. Ta nãi d·y ®ã lµ cã d¹ng h×nh sin bËc M nÕu d·y gåm ®óng M+1 ®o¹n liªn tiÕp lu©n phiªn ®¬n ®iÖu t¨ng - gi¶m hoÆc gi¶m - t¨ng. VÝ dô: D·y sè 1 5 9 13 12 8 4 2 3 7 11 15 14 10 6 lµ d·y h×nh sin bËc M=3, d·y ®ã ®îc ph©n chia thµnh 4 ®o¹n: §o¹n 1: 1 5 9 13 §¬n ®iÖu t¨ng §o¹n 2: 13 12 8 4 2 §¬n ®iÖu gi¶m §o¹n 3: 2 3 7 11 15 §¬n ®iÖu t¨ng §o¹n 4: 15 14 10 6 §¬n ®iÖu gi¶m Cho d·y X gåm N sè nguyªn kh¸c nhau X1, X2,......, XN (2
Bµi tËp c¬ b¶n – TËp I

| | | | | / \ / / / / / / H×nh 1

| | | | | \

| | | | |

\

\

\

\

\

\

Tr¹ng th¸i 1

| | | | | / / \ / /\ \ / / \ \ / / \ \ Tr¹ng th¸i 0

¤ t« m¸t ho¹t ®éng nh sau: khi th¶ mét qu¶ cÇu vµo mét lèi vµo nµo ®ã, sau khi qu¶ cÇu ®i qua mét chi tiÕt nµo ®ã, chi tiÕt ®ã thay ®æi tr¹ng th¸i tõ 0 thµnh 1 hoÆc tõ 1 thµnh 0. Ho¹t ®éng cña « t« m¸t ®îc thÓ hiÖn bëi mét x©u ký tù S chØ gåm c¸c ch÷ c¸i hoa A, B, C mµ mçi ký tù trong x©u S thÓ hiÖn viÖc ta th¶ qu¶ cÇu vµo lèi vµo víi tªn ký tù ®ã. VÝ dô S = AABC cã nghÜa lµ ta lÇn lît th¶ qu¶ cÇu vµo c¸c lèi A, A, B, C. A

/ | | | | | | \

| | | | | | G1 / / \ / /\ \ / / \ \ / / \ \/ / \ | | | | | | | | | | | | \ /\ \ \ / /\ \ \ / / \ \/ / \ / | | | | | | G6 / / \ / /\ \ / / \ \

/

/

/

| | | /

B

/ /\

/ / | | | | | | G4 \ \ \ \ \ \/ \ | | | / / / /\ / /

| | | G2 \ \ \ \ \ \/ \ | | | | | | / / / /\ / / / / | | | G7 \ \ \ \

C | |

| | | | G3 / \ \ / /\ \ / / \ \ / \ \ / \ \ | | | | | | | | | | | | | | | | G5 | | \ / / \ / / \ \ / / \ \/ / \ / | | | | | | G8 / \ \ / /\ \ / / \ \

H×nh 2 - 22 – Lª Ngäc Th¾ng – [email protected]

Bµi tËp c¬ b¶n – TËp I

Bµi to¸n ®Æt ra nh sau: Cho hai tr¹ng th¸i bÊt kú T1 vµ T2 cña « t« m¸t. H·y t×m mét x©u ký tù S ng¾n nhÊt cã thÓ ®îc thÓ hiÖn ho¹t ®éng cña « t« m¸t chuyÓn tõ tr¹ng th¸i T1 ®Õn tr¹ng th¸i T2. C¸c x©u T1 vµ T2 nhËp tõ bµn phÝm vµ viÕt x©u S ra mµn h×nh.

- 23 – Lª Ngäc Th¾ng – [email protected]