Probleme_PIA_2014-2015

Probleme P.I.A. 2014 - 2015

1

PA1. S se genereze toate elementele produsului cartezian { }mn,...2,1 , 1, nm .

PA2. S se determine toate submulimile mulimii { }n,...,2,1 , 1n , n care oricare dou elemente nu sunt numere consecutive

PA3. Se d o mulime cu n elemente numere ntregi. S se genereze toate submulimile acestei mulimi, cu proprietatea c suma elementelor acestora este egal cu o valoare dat s.

PA4. Se d o mulime cu n elemente numere ntregi. S se genereze toate submulimile acestei mulimi, cu proprietatea c suma elementelor acestora este un numr par.

PA5. Se d o mulime cu n elemente numere ntregi. S se genereze toate submulimile acestei mulimi, cu proprietatea c suma elementelor acestora este un numr impar.

PA6. Se d o mulime cu n elemente numere ntregi. S se genereze toate submulimile acestei mulimi, cu proprietatea c produsul elementelor acestora este un numr par.

PA7. Se d o mulime cu n elemente numere ntregi. S se genereze toate submulimile acestei mulimi, cu proprietatea c produsul elementelor acestora este un numr impar.

PA8. Se d un alfabet care conine k vocale i m consoane. S se genereze toate cuvintele de lungime n care nu conin trei vocale sau trei consoane alturate.

PA9. Se dau n melodii de lungimi (durate) naaa ,....,, 21 care trebuie nregistrate pe o caset audio cu dou fee: faa A i faa B. S se determine ce melodii trebuie nregistrate pe fiecare dintre cele dou fee, astfel nct diferena (n valoare absolut) dintre sumele lungimilor melodiilor de pe cele dou fee s fie minim.

PA10. Se dau n obiecte de greuti naaa ,....,, 21 care trebuie transportate cu un rucsac de capacitate C. S se genereze toate variantele de ncrcare a rucsacului pentru primul transport.

PA11. S se determine toate descompunerile unui numr natural n, n sum de numere prime (dac exist).

PA12. S se determine toate descompunerile unui numr natural n, n sum de numere prime distincte (dac exist).

PA13. S se determine toate descompunerile unui numr natural n, n sum de k numere prime distincte (dac exist).

PA14. S se determine toate descompunerile unui numr natural n, n sum de k numere naturale distincte, prime ntre ele (dac exist).

PA15. S se determine toate descompunerile unui numr natural 1n , n sum de termeni distinci ai irului lui Fibonacci.

PA16. S se determine toate descompunerile unui numr natural n, n sum de cuburi ale unor numere naturale.

PA17. S se genereze toate posibilitile de urcare a unei scri cu n trepte tiind c la fiecare pas se poate avansa cu 1, 2 sau 3 trepte.


2

PA18. Pentru un numr natural 0>n dat, s se genereze secvena Farey de ordinul n. Se numete secven Farey de ordinul n irul de perechi )...,(),,(),,( 332211 yxyxyx , unde ii yx , sunt numere naturale care

verific urmtoarele condiii: 1) nyi


3

PA30. S se genereze toate funciile monotone { } { }nnf 2,...,2,1,...,2,1: cu proprietatea c iif 2)( , ni ,1= .

PA31. O funcie XXf : se numete idempotent dac )())(( xfxff = , pentru orice Xx . S se determine toate funciile { } { }nnf ,...,2,1,...,2,1: , idempotente. (Obs.: numrul funciilor idempotente este

=

n

k

kn

kn Ck1

).

PA32. Se consider irul polinoamelor Fibonacci definit astfel: 10 =F , XF =1 i 21 += kkk FFXF , pentru 2k . Pentru n natural dat s se determine coeficienii polinomului nF .

PA33. S se determine coeficienii polinomulului Cebev nP , de grad 0n , dat prin: 10 =P , XP =1 i

11 2 + = kkk PPXP pentru 1k .

PA34. S se determine coeficienii polinomului nP , dat prin: 10 =P , XP =1 i 11 2 + = kkk PXPP pentru 1k .

PA35. S se determine coeficienii polinomului nP , dat prin: 10 =P , 11 += XP i 11 )1( + += kkk PXPP pentru 1k .

PA36. Se consider o matrice de dimensiune nm cu elemente din mulimea { }9,...,2,1,0 . Prin permutri de coloane, s se rearanjeze astfel nct suma numerelor obinute citind cifrele de pe fiecare linie s fie minim.

PA37. Se consider o matrice de dimensiune nm cu elemente din mulimea { }9,...,2,1,0 . Prin permutri de coloane, s se rearanjeze astfel nct suma numerelor obinute citind cifrele de pe fiecare linie s fie maxim.

PA38. S se genereze toate modalitile de plat ale unei sume S, considernd c se dispune de n tipuri de bancnote de valori nvvv ,...,, 21 (dac este posibil).

PA39. S se genereze toate modalitile de plat ale unei sume S, considernd c se dispune de n tipuri de bancnote de valori nvvv ,...,, 21 i pentru fiecare tip de bancnot exist un numr de nbbb ,...,, 21 buci (dac este posibil).

PA40. Se consider mulimea }2,...,4,3,2{ nA = , 8n . S se determine toate submulimile S cu n elemente ale mulimii A, cu proprietatea c pentru orice Sji , avem Sji + . (Obs.: numrul de submulimi este 5+n ).

PA41. Se dau n numere ntregi pozitive. S se rearanjeze aceste numere n irul naaa ,....,, 21 , astfel nct suma 13221 .... aaaaaa n +++ s fie ct mai mare posibil.

PA42. Se dau n numere ntregi pozitive. S se rearanjeze aceste numere n irul naaa ,....,, 21 , astfel nct suma 13221 .... aaaaaa n +++ s fie ct mai mic posibil.


4

PA43. S se genereze toate numerele naturale formate din n cifre distincte, n care s nu existe dou cifre pare alturate.

PA44. S se genereze toate funciile injective { } { }nnf 2,...,2,1,...,2,1: .

PA45. Se consider n numere naturale. S se asocieze acestor numere semnele "+" sau "-" astfel nct modulul sumei obinute s fie minim.

PA46. O caravan format din n camile cltorete prin deert, n ir indian. Pentru a sparge monotonia zilelor lungi de drum, beduinul ef se hotrte s schimbe aezarea cmilelor, astfel nct fiecare cmil s nu mai vad n faa ei aceeai cmil de pn atunci. S se genereze toate posibilitile de aezare a cmilelor, cunoscnd modul de aezare din prima zi.

PA47. Un dresor trebuie s scoat m lei i n tigri din aren, astfel nct s nu scoat doi tigri unul dup altul. Care sunt posibilitile sale de a realiza acest lucru?

PA48. S se determine toate matricele de dimensiune nm cu elemente din mulimea { }1,1 care au produsul elementelor de pe fiecare linie i fiecare coloan egal cu 1 .

PA49. S se genereze toate numerele naturale de n cifre, cu toate cifrele impare.

PA50. S se genereze toate numerele naturale de n cifre, cu toate cifrele distincte i impare.

PA51. S se verifice dac o mulime de numere ntregi pozitive are suma distinct. Spunem c o mulime de

numere ntregi pozitive { }naaa ,...,, 21 are suma distinct dac cele n2 sume posibile =

n

iiia

1, unde

{ }1,0i , sunt numere distincte.

PA52. Se dau n numere ntregi a cror sum este un numr par. S se mpart aceste numere n dou grupe astfel nct sumele numerelor din cele dou grupe s fie egale (dac este posibil).

PA53. Se consider numerele ntregi strict pozitive naaa ,...,, 21 i nbbb ,...,, 21 . S se determine n fracii de

forma ji

ba

, nji ,1, = , astfel nct suma acestora s fie maxim.

PA54. Se consider numerele ntregi strict pozitive naaa ,...,, 21 i nbbb ,...,, 21 . S se determine n fracii de

forma ji

ba

, nji ,1, = , astfel nct suma acestora s fie minim.

PA55. Se consider 2n numere ntregi strict pozitive naaa 221 ,...,, . Utiliznd toate cele 2n numere, s se

determine n fracii de forma ji

a

a astfel nct suma acestora s fie maxim.

PA56. Se consider 2n numere ntregi strict pozitive naaa 221 ,...,, . Utiliznd toate cele 2n numere, s se

determine n fracii de forma ji

a

a astfel nct suma acestora s fie minim.

PA57. S se genereze toate irurile de n2 paranteze (rotunde) care se nchid corect. Exemplu: pentru 2=n , avem irurile de paranteze: ()() i (()).


5

PA58. S se determine numerele naturale mai mici dect un numr n, pentru care suma cifrelor este un termen din irul lui Fibonacci. (irul 0)( nnF al numerelor lui Fibonacci se definete astfel: 00 =F ,

11 =F i 21 += nnn FFF pentru 2n .)

PA59. S se determine numerele naturale mai mici dect un numr n, pentru care suma ptratelor cifrelor este un termen din irul lui Lucas. (irul 0)( nnL al numerelor lui Lucas se definete astfel: 20 =L ,

11 =L i 21 += nnn LLL pentru 2n .)

PA60. S se determine numerele prime mai mici dect n, pentru care suma factorialelor cifrelor este un numr triunghiular. (irul 0)( nnT al numerelor triunghiulare se definete astfel: 2 1+= nn CT , pentru orice 0n .)

PA61. S se genereze toate numerele naturale formate din n cifre, n care oricare dou cifre alturate au paritate diferit.

PA62. Se d ecuaia de gradul al treilea 023 =+++ dcxbxax , Rdcba ,,, , 0a . Pentru n natural dat s se calculeze nnn xxx 321 ++ , unde 321 ,, xxx sunt rdcinile ecuaiei date.

PA63. Se numesc numere superprime, acele numere ale cror prefixe sunt tot numere prime. S se verifice dac un numr dat este superprim i s se afieze prefixele acestuia.

PA64. Se d o matrice ptratic A, de dimensiune n. S se descompun A n sum de dou matrice B i C, astfel nct B s fie simetric, iar C s fie inferior triunghiular cu valorile 1, 2, 3,, n pe diagonala principal.

PA65. S se determine punctele a ale unei matrice ( ) jiijaA ,= , cu m linii i n coloane. Un element ija al matricei se numete punct a, dac valoarea sa este cea mai mic pe linia i i cea mai mare pe coloana j sau este cea mai mare pe linia i i cea mai mic pe coloana j.

PA66. S se determine punctele de extremum ale unei matrice ( ) jiijaA ,= , cu m linii i n coloane. Un element ija al matricei se numete punct de extremum, dac valoarea sa este cea mai mic att pe linia i ct i pe coloana j sau este cea mai mare att pe linia i ct i pe coloana j.

PA67. S se genereze o matrice ptratic de dimensiune n cu elementele 2,...,2,1 n aezate n serpentin. Exemplu pentru o matrice de dimensiune 4:

13121110147891563216541

.

PA68. S se genereze o matrice ptratic de dimensiune n cu elementele 2,...,2,1 n aezate n unghi drept. Exemplu pentru o matrice de dimensiune 4:

13121110147651583216941

.


6

PA69. S se genereze o matrice ptratic de dimensiune n cu elementele 2,...,2,1 n aezate n zig-zag. Exemplu pentru o matrice de dimensiune 4:

13141516121110956784321

.

PA70. S se genereze o matrice ptratic de dimensiune n cu elementele 2,...,2,1 n aezate n spiral. Exemplu pentru o matrice de dimensiune 4:

78910615161151413124321

.

PA71. S se genereze o matrice ptratic de dimensiune n cu elementele irului de numere ntregi ,....5,3,4,2,3,1,2,,1 2222 nnnn , aezate n spiral.

Exemplu pentru o matrice de dimensiune 4:

41431513810259716

126111

.

PA72. S se determine toate mutrile pe care trebuie s le efectueze un cal pe o tabl de ah astfel nct s treac prin toate poziiile o singur dat, pornind dintr-o poziie oarecare.

PA73. S se genereze o matrice ptratic de dimensiune n cu elementele irului de numere ntregi

,....5,,4,,3,,2,,1 4321 xxxx , aezate n spiral, unde 12 += kxk , ,...2,1=k .


53742158937175113611

.


,....10,7,8,5,6,3,4,1,2 aezate n spiral.


91078121516511141362143

.


7

PA75. Pentru un numr natural n dat, s se genereze ntr-o matrice ptratic de dimensiune 12 +n , un romb care s conin numere naturale consecutive, 1,2,3...., aranjate pe linii, ca n exemplul de mai jos. Celelalte elemente ale matricei vor fi completate cu 0.

Exemplu: pentru 2=n , n matricea de dimensiune 5122 =+ , se va genera rombul:

00130001011120567890234000100

.

PA76. Pentru un numr natural n dat, s se genereze ntr-o matrice ptratic de dimensiune 12 +n , un romb care s conin numere naturale consecutive, 1,2,3...., aranjate pe coloane, ca n exemplul de mai jos. Celelalte elemente ale matricei vor fi completate cu 0.


00500010620

131173101284000900

.

PA77. Se consider n perechi de numere reale, ],[ 11 ba , ],[ 22 ba ,., ],[ nn ba , cu ii ba pentru ni ,1= , care reprezint capetele a n intervale nchise. S se determine intersecia celor n intervale.

PA78. S se genereze toate numerele naturale formate din cifre distincte, astfel nct suma cifrelor s fie s.

PA79. S se genereze toate permutrile mulimii },...,2,1{ n , ,1n n care elementele pare sunt puncte fixe (adic se afl pe poziii egale cu valoarea lor).

PA80. Se consider polinomul de gradul nti, baXXP +=)( . Pentru n natural dat, s se determine coeficienii polinomului

444 3444 21ori de

)...)))((...((n

XPPPP .


,....5,3,4,2,3,1,2,,1 +++ kkkk , aezate n spiral, unde 12

12+

+=

nk , iar [x] este partea ntreag

a lui x. Exemplu pentru o matrice de dimensiune 4:

412513118166315714

10291

.


8

PA82. S se genereze o matrice ptratic de dimensiune n cu elementele 2,...,2,1 n aezate ncepnd cu diagonala principal i continund apoi cu celelalte diagonale paralele cu aceasta. Completarea celoralate diagonale se va face alternativ, deasupra i apoi dedesubtul diagonalei principale.


410141673913

12628151151

.

PA83. Pentru un numr natural n dat, s se genereze ntr-o matrice ptratic de dimensiune 12 +n , un romb care s conin numere naturale consecutive, 1,2,3...., aranjate n spiral, ca n exemplul de mai jos. Celelalte elemente ale matricei vor fi completate cu 0.


00700061280511139104102000300

.

PA84. La curtea regelui Arthur s-au adunat n cavaleri numerotai de la 1 la n. Despre ei se cunosc relaii de dumnie de forma (x,y) cu semnificaia c x i y se dumnesc. S se afieze toate modurile n care Arthur i poate aranja la o mas rotund cu n scaune astfel nct s nu stea unul lng altul doi cavaleri care dumnesc.

PA85. Un student trebuie s susin n sesiune n examene, numerotate 1,2,...,n, avnd creditele nccc ,...,, 21 . Pentru a promova sesiunea el trebuie s acumuleze cel puin c credite. Gsii toate modalitile de alegere a unui numr minim de examene, astfel nct studentul s obin creditele necesare promovrii. (Se presupune c fiecare examen ales a fi susinut va fi promovat.)

PA86. S se implementeze operaia de nmulire a dou numere mari, cu mai mult de 15 cifre.

PA87. S se genereze toate numerele naturale formate din n cifre distincte, n care s nu existe dou cifre pare alturate.

PA88. S se genereze matricele ptratice de ordinul n, cu elemente 0 i 1, cu proprietatea c pe fiecare linie i pe fiecare coloan exist un singur element egal cu 1.

PA89. Se d o mulime cu n elemente numere naturale. S se genereze toate submulimile acestei mulimi, cu proprietatea c suma elementelor acestora este un numr prim.

PA90. Se consider un numr natural k i o matrice ptratic A de dimensiune n. S se calculeze kA . Pentru micorarea numrului de operaii se va ine seama de urmtoarea observaie:

=

impar. pentru ,

par pentru ,

2

21

2

2

kAA

kA

Ak

k

k


9

PA91. Se dau n numere ntregi nenule naaa ,...,, 21 . S se determine n numere ntregi, nxxx ,...,, 21 , astfel nct cel mai mare divizor comun al numerelor naaa ,...,, 21 s se scrie sub forma

nnaxaxax +++ ...2211 .

PA92. S se genereze un ptrat magic de ordin impar. (Ptratul magic este o matrice ptratic de dimensiune n, care conine toate numerele naturale de la 1 la 2n i n care sumele pe linii, coloane i pe diagonale au aceeai valoare.)

PA93. Se consider n puncte n plan, 3n , date prin coordonatele lor carteziene, ),( 111 yxP , ),( 222 yxP ,, ),( nnn yxP . Dintre toate triunghiurile care se pot forma cu aceste puncte, s se

determine triunghiul de arie maxim.

PA94. n sistemul de axe xOy se consider dou dreptunghiuri cu laturile paralele cu axele Ox i, respectiv, Oy, date prin coordonatele carteziene ale vrfurilor stnga sus i dreapta jos. S se calculeze aria determinat de reuniunea celor dou dreptunghiuri. S se rezolve, apoi, problema pentru situaia cnd se dau n dreptunghiuri.

PA95. n sistemul de axe xOy se consider dou dreptunghiuri cu laturile paralele cu axele Ox i, respectiv, Oy, date prin coordonatele carteziene ale vrfurilor stnga sus i dreapta jos. S se calculeze aria determinat de intersecia celor dou dreptunghiuri. S se rezolve, apoi, problema pentru situaia cnd se dau n dreptunghiuri.

PA96. Se consider n plan n puncte, date prin coordonatele lor carteziene, ),( 11 yx , ),( 22 yx , , ),( nn yx . S se determine ordinea de parcurgere a acestora, astfel nct s poat fi unite printr-o linie poligonal deschis, care s treac prin toate punctele o singur dat i ale crei segmente s nu se intersecteze.

PA97. S se calculeze aria unui poligon convex dat prin coordonatele carteziene ale vrfurilor sale, ),( 111 yxP , ),( 222 yxP ,, ),( nnn yxP , 3n .

PA98. Se consider o mulime finit },...,2,1{ nG = i o lege de compoziie GGG : , definit matriceal. S se verifice: 1) dac lege este comutativ; 2) dac legea este asociativ; 3) dac legea are sau nu element neutru; 4) dac fiecare element admite un invers; 5) dac ),( G este grup abelian.

PA99. Se consider irul ...,...,,,....,,4,4,4,4,3,3,,3,2,2,1ori de43421

k

kkk . Pentru n dat, s se determine termenul aflat pe

poziia n, fr a citi sau construi efectiv irul.

PA100. S se implementeze operaia de adunare a dou numere mari, cu mai mult de 15 cifre, numerele fiind reprezentate ca vectori.

PA101. S se implementeze operaia de scdere a dou numere mari, cu mai mult de 15 cifre, numerele fiind reprezentate ca vectori.

PA102. S se implementeze operaia de nmulire a dou numere mari, cu mai mult de 15 cifre, numerele fiind reprezentate ca vectori.

PA103. S se implementeze operaia de mprire a dou numere mari, cu mai mult de 15 cifre, numerele fiind reprezentate ca vectori.

Probleme_PIA_2014-2015

Documents

Transcript of Probleme_PIA_2014-2015