67 De Pagini De Probleme Rezolvate Si Teorie In Pascal

CUPRINS PREFA

................................................................................................................................................9

Capitolul 1. PROBLEME SIMPLE 1.1. Ghid de lucru................................................................................................................................... 11 1.2. Numere pitagorice .......................................................................................................................... 14 1.3. Probleme propuse .......................................................................................................................... 15 Capitolul 2. PROBLEME CU IRURI DE NUMERE 2.1. Numere distincte ............................................................................................................................ 21 2.2. ir derivat din numerele naturale ................................................................................................... 23 2.3. Probleme propuse .......................................................................................................................... 25 Capitolul 3. PROBLEME REZOLVATE FOLOSIND VECTORI 3.1. Num rul punctelor din cerc ........................................................................................................... 35 3.2. Interclasare ..................................................................................................................................... 36 3.3. Probleme propuse .......................................................................................................................... 38 Capitolul 4. PROBLEME CU MATRICE 4.1. Construirea unei matrice ................................................................................................................ 41 4.2. Generarea unei matrice dintr-un ir ............................................................................................... 42 4.3. Probleme propuse .......................................................................................................................... 43 Capitolul 5. SUBALGORITMI 5.1. Reuniunea unor mul imi ................................................................................................................. 51 5.2. Numere prime ................................................................................................................................ 54 5.3. Probleme propuse .......................................................................................................................... 55 Capitolul 6. PROBLEME REZOLVATE CU MATRICE 6.1. Rela ii între persoane ..................................................................................................................... 63 6.2. P trate magice ................................................................................................................................ 64 6.3. Probleme propuse .......................................................................................................................... 66

5

PREFA

Culegerea de probleme de fa se dore te a fi un ghid io colec ie de probleme pentru înv area program rii. Diversitatea problemelor propuse i gradul diferit de dificultate fac culegerea util nu numai studen ilor, ci i elevilor de liceu. Ini ial ea a fost conceput ca ghid pentru lucr rile de laborator ale studen ilor anilor întâi i doi de la sec ia de Informatic a Facult ii de Matematic i Informatic . Problemele sunt grupate în 16 capitole, în func ie de specificul i gradul lor de complexitate. Succesiunea capitolelor din culegere vizeaz o abordare gradual a problematicii, atât din punctul de vedere al complexit ii algoritmilor, specifica i în limbaj Pseudocod, cât i al înv rii unui limbaj de programare, în particular limbajul Pascal. Fiecare capitol con ine cel pu in dou exemple de probleme rezolvate, pentru care sunt preciza i atât algoritmii de rezolvare, cât i programele surs Pascal. Inten ia autorilor este de a sugera un anumit stil de rezolvare a problemelor cu calculatorul, acordându-se o importan deosebit etapelor de analiz a problemei i de proiectare a algoritmilor, etape în care limbajul de programare nu este implicat. Din acest punct de vedere, problemele propuse sunt generale, implementarea solu iilor putând fi f cut i în alte limbaje de programare. Problemele de acela i tip sunt grupate în acela i capitol, iar un capitol acoper toat gama de probleme pentru tema abordat . Astfel, capitolul I con ine probleme elementare, a c ror rezolvare nu cere folosirea vectorilor sau a matricelor. Capitolul doi con ine probleme referitoare la vectori, în timp ce capitolul trei con ine probleme a c ror rezolvare cere folosirea vectorilor. Capitolul patru con ine probleme cu matrice. Capitolul cinci cere folosirea subalgoritmilor. Capitolul ase con ine probleme a c ror rezolvare cere folosirea matricelor. Urmeaz un capitol de exemple i probleme pentru programarea în limbaj ma in . Capitolul opt con ine probleme referitoare la tipurile mul ime i enumerare din Pascal. Capitolul nou con ine probleme referitoare la iruri de caractere. Capitolul zece se refer la recursivitate. Urmeaz un capitol de probleme privind folosirea fi ierelor. Capitolul 12 con ine probleme care cer folosirea tipului referin în Pascal. Urm torul capitol con ine probleme de grafic cu calculatorul. Capitolul 14 con ine mai multe probleme date la diferite concursuri de programare. Tipurile abstracte de date sunt obiectul capitolului 15. În sfâr it, ultimul capitol con ine probleme despre grafe. De i la selectarea problemelor au contribuit to i autorii, fiecare capitol a fost elaborat de unul sau doi autori, dup cum urmeaz : Cap.1 - Prof. S.Groze i Prof. M.Fren iu; Cap.2 - Prof. M.Fren iu; Cap.3 - Lect. Robu J. i Prof. M.Fren iu; Cap.4 - Asist. S. Motogna; Cap.5 - Asist. E.Iacob; Cap.6 - Conf. Kasa Z. i Asist. S.Motogna; Cap.7 - Conf. F.Boian; Cap.8 - Lect. V.Ciobanu; Cap.9 - Asist. S.Iurian; Cap.10 - Asist. S.Iurian; Cap.11 - Asist. H.Pop; Cap.12 - Lect. V.Prejmereanu; Cap.13 - Lect. V.Prejmereanu; Cap.14 - Asist. S.Motogna; Cap.15 - Conf. B.P rv i Prof. M.Fren iu; Cap.16 - Conf. T.Toadere. Eventualele erori nu se pot imputa numai celor de mai sus, to i autorii participând la corectarea final a acestei culegeri. Sper m ca prezentul material s - i ating scopul propus, cel de dezvoltare la cititori a gustului de programare întrun limbaj evoluat, în particular în limbajul Pascal. Con tien i c exist posibilit i de îmbun t ire a con inutului prezentei lucr ri, autorii mul umesc anticipat pe aceast cale tuturor celor care vor face observa ii i propuneri de îmbun t ire, de care se va ine seama la o nou editare a culegerii de probleme.

6

CAPITOLUL 1

PROBLEME SIMPLE 1.1. GHID DE LUCRU Rezolvarea unei probleme cu ajutorul calculatorului presupune parcurgerea urm toarelor faze: - precizarea complet a problemei de rezolvat; - proiectarea algoritmului de rezolvare a problemei; - programarea propriu-zis (implementarea); - testarea programului ob inut; - exploatarea i între inerea programului. Aceste faze constituie ciclul de via al programului. De foarte multe ori, atunci când beneficiarul discut cu executantul despre problema care trebuie rezolvat , acesta d un enun vag, incomplet, dac nu chiar inexact sau contradictoriu, pentru problema de rezolvat. Urmeaz mai multe discu ii, uneori întinse în timp, în urma c rora se ajunge la un enun relativ complet i exact al problemei. Întrucât problemele propuse sunt luate din domeniul matematicii sarcina noastr va fi mult mai u oar . Dup enun area problemei urmeaz modelarea matematic i c utarea unei metode de rezolvare a ei. Uneori sunt posibile mai multe moduri de rezolvare, caz în care se va alege metoda considerat cea mai potrivit scopului urm rit. Modelarea matematic i alegerea unei metode de rezolvare se îmbin aproape întotdeauna cu conceperea algoritmului, fiind greu s se separe una de cealalt . Activit ile de mai sus constituie ceea ce numim proiectarea programului. Pe toat durata proiect rii trebuie men ionate în scris toate deciziile luate, întrucât este posibil ca ulterior s fie necesar o reproiectare i deci, s se revin asupra acestor decizii. Documenta ia realizat este necesar în primul rând pentru urm toarea faz a ciclului de via al programului, implementarea. De asemenea, în faza de între inere a programului este posibil modificarea unor module, modificare în care sunt necesare s fie cunoscute i aceste decizii. E bine ca proiectarea s fie astfel f cut încât s permit o între inere cât mai u oar . Faza urm toare, implementarea sau codificarea, const în traducerea algoritmului într-un limbaj de programare. Evident, prima decizie ce trebuie luat const în alegerea limbajului de programare în care va fi scris programul. În cele ce urmeaz vom folosi în acest scop limbajul Pascal. De multe ori se vor folosi mai multe limbaje pentru aceast activitate. De exemplu, pot exista unele module a c ror scriere se poate face numai în limbajul de asamblare. Urmeaz testarea programului elaborat, care uneori pune în eviden erori grave de programare, erori care au dus în unele situa ii la refacerea (par ial sau integral ) a activit ilor anterioare. Sigur c este de dorit s nu se ajung la astfel de situa ii i, dac proiectarea i implementarea au fost f cute corect, în faza de testare nu ar trebui s întâlnim erori. Urm toarea faz din via a programului const în exploatarea propriu-zis a acestuia, faz în care execu ia se face cu date reale. Aceast activitate se întinde în timp pe mai mul i ani i cere adeseori schimb ri în program, motiv pentru care este cunoscut sub numele de între inerea programului. Este faza cea mai costisitoare i cea mai important din via a unui produsul real. Toat activitatea de realizare a programului trebuie s in seama de acest fapt i programul s fie astfel conceput încât s se permit modific ri în ceea ce face programul cu un num r minim de modific ri în textul acestuia. Documentarea programului presupune elaborarea unor materiale scrise în care se precizeaz toate informa iile utile despre programul realizat. Pentru proiectarea algoritmilor vom folosi limbajul Pseudocod. Avantajele folosirii acestui limbaj pentru proiectarea algoritmilor constau în faptul c permit programatorului s - i îndrepte complet aten ia asupra logicii rezolv rii problemei i s uite de restric iile impuse de limbajul de programare i calculatorul folosit. În aceast faz este necesar o analiz atent a problemei în vederea g sirii unui algoritm corect proiectat. De asemenea, proiectarea algoritmului permite evitarea duplic rii unui grup de instruc iuni în mai multe p r i ale programului. Identificarea unui astfel de grup permite definirea lui ca un singur subalgoritm i folosirea acestui subalgoritm ori de câte ori este necesar. În descrierea unui algoritm deosebim urm toarele activit i importante: - specificarea problemei; - descrierea metodei alese pentru rezolvarea problemei; - precizarea denumirilor i semnifica iilor variabilelor folosite;

7

- descrierea algoritmului propriu-zis. Astfel, dac ni se cere s calcul m radicalul de ordinul 2 din x, în partea de specificare a problemei vom men iona: Se d un num r real nenegativ, notat prin x. Se cere s g sim un alt num r pozitiv r astfel încât r2=x. Pentru un informatician este clar c un astfel de num r nu se poate g si în general prin nici un procedeu finit. Este îns posibil s g sim o aproximare oricât de bun a lui r. Deci specificarea f cut nu este corect , neputând g si un algoritm care s rezolve problema în forma enun at . Vom modifica aceast specifica ie, cerând s se calculeze aproximativ r cu o eroare ce nu dep e te un num r real eps oricât de mic. Specifica ia problemei este: DATE eps,x; REZULTATE r;

{eps,xR, eps>0 i x0} {r-rad(x)<eps}

unde prin rad(x) am notat radicalul de ordinul 2 din x definit în matematic . r:

Urmeaz s preciz m metoda de rezolvare a problemei. Se tie c exist cel pu in dou posibilit i de a calcula pe

- ca limit a unui ir (definit printr-o rela ie de recuren ) convergent la r; - prin rezolvarea ecua iei r2=x. Preciz m c -l vom calcula pe r rezolvând ecua ia r2=x. Dar i rezolvarea acestei ecua ii se poate face prin mai multe metode. Decidem c o vom rezolva prin metoda njum t irii. Aceast metod const în njum t irea repetat a intervalului [a,b] care con ine r d cina r la intervalul [a',b'], care este jum tatea stâng , sau jum tatea dreapt a intervalului [a,b], cea care con ine r d cina. Variabilele folosite în descrierea algoritmului sunt: - a i b = capetele intervalului în care se afl r d cina; - m mijlocul intervalului (a,b). În momentul în care b-a<eps, m va fi chiar valoarea c utat pentru r. Algoritmul propriu-zis este descris în continuare: *Ini ializeaz pe a i b; REPET FIE m:=(a+b)/2; * Dac r d cina se afl în [a,m] atunci b:=m altfel a:=m. P N C ND b-a<eps SF-REPET FIE r:=(a+b)/2; În textul de mai sus apar dou propozi ii nestandard care sugereaz îns foarte bine ce ac iuni trebuiesc întreprinse. Prima stabile te intervalul ini ial în care se afl r d cina, care depinde de m rimea lui x: (x,1) când x este mai mic decât 1 sau (1,x) în caz contrar. Deci ea se va transcrie în propozi ia standard DAC x<1 ATUNCI ATRIBUIE a:=x; b:=1 ALTFEL ATRIBUIE a:=1; b:=x SF-DAC A doua propozi ie înjum t e te intervalul. Condi ia ca r d cina s se afle în jum tatea stâng a intervalului este (a2-x)*(m2x)<0. Se ajunge la urm toarea variant final : ALGORITMUL RADICAL ESTE: DATE eps,x; DAC x<1 ATUNCI FIE a:=x; b:=1 ALTFEL FIE a:=1; b:=x

8

{Calculeaz radical din x} {eps,xR, eps>0 i x0} {Ini ializeaz pe a i b}

SF-DAC REPET DAC (a2-x)*(m2-x)<0 ATUNCI b:=m ALTFEL a:=m SF-DAC P N C ND b-a<eps SF-REPET FIE r:=(a+b)/2; REZULTATE r; SF-ALGORITM

{r d cina în stânga} {r d cina în dreapta}

{r-rad(x)<eps}

Programul Pascal corespunz tor este dat în continuare. PROGRAM RADICAL; {Programul 1.1. Calculeaz radical din x} VAR eps, {eps= precizia cu care se calculeaz } x, {radical din x, eps>0 si x>=0} r, {valoarea radicalului x} a,b, {capetele intervalului ce con ine pe r} m : REAL; {mijlocul intervalului [a,b]} BEGIN WRITELN('Se calculeaz radical din x cu precizia eps:'); WRITE('eps='); READLN(eps); WRITE(' x ='); READLN(x); IF x<1 THEN BEGIN a:=x; b:=1 END {Ini ializeaz pe a si b} ELSE BEGIN a:=1; b:=x END; REPEAT m:=(a+b)/2; IF (a*a-x)*(m*m-x)<0 THEN b:=m {r d cina în stânga} ELSE a:=m; {r d cina in dreapta} UNTIL b-a<eps; r:=(a+b)/2; WRITELN; WRITELN; WRITELN('Radical(',x:6:1,') = ',r:6:3); {r-rad(x)<eps} READLN END. 1.2. NUMERE PITAGORICE. Numerele a,b,c, se numesc pitagorice dac a 2 + b2 = c 2 1. S se tip reasc toate tripletele (a,b,c) de numere pitagorice, cu 0
{nN; pentru n<12 nu exist triplete}

9

Dac n<12 atunci Tip re te "Nu exist numerele cerute" altfel Pentru S=12,n execut Pentru a=3,S/3 execut Pentru b=a+1,(S-a)/2 execut Fie c:=S-a-b; Dac c =a +b atunci Tip re te(a,b,c) Sf-dac Sf-pentru Sf-pentru Sf-pentru Sf-dac Sf-algoritm. Programul Pascal corespunz tor este dat în continuare. PROGRAM NRPITAGORICE; VAR n, S, a,b,c, k : integer; BEGIN WRITELN('Se tip resc tripletele(a,b,c) de numere pitagorice'); WRITELN('cu proprietatea: a+b+c<=n, pentru n dat'); WRITE('Da i valoarea lui n:'); READLN(n); For k:=1 to 4 do writeln; k:=0; IF n<12 THEN WRITELN('Nu exista numerele cerute') ELSE FOR S:=12 TO n DO FOR a:=3 TO S DIV 3 DO FOR b:=a+1 TO (S-a) DIV 2 DO BEGIN c:=S-a-b; IF c*c=a*a+b*b THEN BEGIN k:=k+1; WRITELN('Tripletul (a,b,c)',k:3,'= ',a:3, b:3,c:3); END {IF} END; READLN; END.

{Programul 1.1.2. Numere pitagorice} } { nN; a+b+cn { S = a+b+c } {(a,b,c) triplet de numere pitagorice} { 0
1.3. PROBLEME PROPUSE 1.1. Fie i,j,k . S se determine restul împ r irii num rului natural ij la k. 1.2. S se tip reasc toate tripletele (i,j,k) de numere naturale care verific condi iile i2 + j2 = k2 1
10

este perfect. (Un num r n este perfect dac este egal cu suma divizorilor lui

diferi i de n; exemplu: 6=1+2+3). 1.4. S se determine numerele perfecte din intervalul [a,b], pentru a,b date. 1.5. Dou numere întregi x i y sunt "prietene" dac suma divizorilor num rului x este egal cu suma divizorilor num rului y. S se g seasc numerele "prietene" din intervalul [a,b]. 1.6. S se calculeze i s se tip reasc primii n termeni din irul Fibonacci, ir definit de rela ia de recuren t i+1 = t i + t i-1 2, i=1,2,... având

t 0 = t 1 = 1 3. 1.7. Fie n,k Z+ , n k. S se scrie un algoritm pentru calculul num rului combin rilor de n elemente luate câte k.

lui a.

1.8. Fie a N. S se scrie un algoritm pentru calculul mediei aritmetice, geometrice i armonice a tuturor divizorilor

1.9. Fie func ia lui Euler : N N, unde tip reasc valorile (k), k=1,2,...,m, pentru mN dat.

(n) este num rul numerelor relativ prime cu n i mai mici ca n. S se

1.10. Fie n,k Z, n k. S se scrie un algoritm pentru calculul sumei

S = Akn + C kn + Pn 4. abc 5 cu proprietatea abc = a 3 + b3 + c3 6.

1.11. S se determine toate numerele întregi de trei cifre

nostru.

1.12. Se dau numerele z,l,a

. S se determine dac tripletul (z,l,a) reprezint o dat calendaristic a secolului

1.13. Se d o zi (z,l,a) dintr-un an. Se cere s se determine a câta zi din acel an este aceast zi. 1.14. Se consider ( z n , l n , a n ) 7 data na terii unei persoane i vârsta, în zile, a persoanei respective.

( z c ,l c , a c ) 8 o dat curent . S se determine

1.15. Se dau datele de na tere ( z 1 , l 1 , a1 ) si ( z 2 , l 2 , a 2 ) 9 a dou persoane. Se cere s se precizeze care din cele dou persoane este mai tân r , prin indicatorul r {0,1,2} (0 dac au aceea i vârst , 1 dac prima persoan este mai tân r ). 1.16. Cunoscând în ce zi din s pt mân a fost 1 ianuarie, s se scrie un algoritm ce determin ziua din s pt mân în care este a n-a zi a anului. 1.17. Anumite numere prime i p streaz proprietatea de a r mâne prime pentru toate permut rile cifrelor lor. Ex. 13 i 31; 131,113 i 311, etc.). S se scrie un algoritm care determin numerele prime "permutabile", mai mici decât un num r m dat. 1.18. O formul de generare a unui ir de numere (yi) este

y n = n2 - 79n + 1601 10. Se cere algoritmul care determin pentru un num r n {1,...,90} câte dintre primele n numere din acest ir sunt prime. 1.19. S se scrie un algoritm care s exprime orice sum de lei S, în minimum de monede de 1 leu, 3 lei, 5 lei, 10 lei , 20 lei, 50 lei i 100 lei.

11

1.20. Fiind date numerele a,b,c,d Z, se cere un algoritm care s stabileasc cea mai mare dintre frac iile a/b i c/d. 1.21. S se g seasc solu iile întregi i pozitive ale ecua iei ax + by = c, cu proprietatea x+y0. 1.22. Se cere valoarea func iei f:[-9,9]

f (x) =

în punctul x, dac

1, 3-x ,

pentru x ≤ 1 pentru -1<x ≤ 0

x 2+2 , 10,

pentru 0<x ≤ 0 pentru x>1

1.23. S se determine solu iile întregi ale sistemului

y ≤ x2 y ≥ 2 x 2 - 16 1.24. Se d n

11

. S se calculeze

k 1 1 C (1+ +...+ ) 12 n 2 k k=1 n

1.25. Fie a,b,c

+.

S se scrie un algoritm pentru rezolvarea ecua iei

x 2 + dx + p = 0 13 unde d = (a,b) este cel mai mare divizor comun al numerelor a i b, iar p este probabilitatea ca un num r n condi ia nc, luat la întâmplare, s fie prim.

ce verific

1.26. Se cere un algoritm pentru determinarea numerelor impare succesive a c ror sum este egal cu n3, pentru n=1,...,20. (Ex.

13 = 1, 23 = 3+ 5, 33 = 7 + 9 + 11 14, etc).

1.27. S se scrie un algoritm care cite te succesiv p perechi de numere întregi (m,n), cu 0 m n i care calculeaz , pentru fiecare pereche coeficientul binomial bn,m definit de rela ia recursiv

bn,m =

1,

daca m = 0 sau m = n,

bn-1,m-1 + bn-1,m ,

in caz contrar .

15

1.28. S se afle toate punctele de coordonate întregi situate în interiorul p tratului cu diagonala determinat de punctele A(a,b) i C(c,d). 1.29. Fie a,b elipsei de ecua ie

. S se scrie un algoritm pentru calculul num rului punctelor de coordonate întregi interioare 2 x2 y + = 1 16 a 2 b2

1.30. Fie dreapta d determinat

12

de punctele A(a1,a2) i B(b1,b2). S se determine pozi ia punctelor A i B fa de

dreapta d, prin indicatorul R definit astfel: R=0, dac punctele A(a1,a2) i B(b1,b2) se afl în acela i semiplan determinat de dreapta d ; R=1, dac punctele A i B apar in dreptei d; R=2, dac punctele A i B se afl în semiplane diferite fa de dreapta d. 1.31. Se d un triunghi prin coordonatele vârfurilor sale i un punct M în planul s u. S se determine pozi ia punctului M fa de laturile triunghiului, marcându-se cu R {1,2,3} trei situa ii posibile: interior triunghiului, pe una din laturi, exterior triunghiului. 1.32. Se d un p trat P1 de latur 1 c ruia i se circumscrie un cerc C1. Cercului ob inut i se circumscrie un nou p trat P2, acestuia un nou cerc C2, etc. S se calculeze aria p tratului Pn i aria cercului Cn ob inute dup un num r de n pa i, prin metoda de mai sus. 1.33. Se dau trei puncte Mi (xi,yi), i=1,2,3, în plan. S se determine parametrul k care s ia valoarea 0 dac punctele sunt coliniare, respectiv 1 în caz contrar. 1.34. Se dau a,b,c,d,e,f

. S se determine pozi ia dreptelor

ax + by + c = 0 dx + ey + f = 0

17

i unghiul dintre ele, exprimat în grade. 1.35. Se cunosc lungimile laturilor unui triunghi. Se cere s se calculeze perimetrul, unghiurile i aria triunghiului. 1.36. Se consider segmentele de dreapt cu extremit ile în punctele A(a1,a2), B(b1,b2), respectiv C(c1,c2), D(d1,d2). S se determine un algoritm de calcul pentru coordonatele punctului de intersec ie a segmentelor date. În cazul în care acest punct nu exist , se va tip ri un mesaj. 1.37. O fabric de mobil prime te comenzi pentru producerea unei diversit i de biblioteci, având: - lungimea cuprins între 2-9 m; - în l imea cuprins între 1-3 m; - un num r de 2,4,6,9 sau 12 corpuri. Costul unei biblioteci este de a lei pentru fiecare metru cub de volum, la care se adaug b lei pentru fiecare corp. Construc ia unei biblioteci trebuie s respecte anumite condi ii impuse de normele de fabrica ie: - lungimea trebuie s fie de 2-3 ori mai mare decât în l imea; - l imea trebuie s fie 1/3 pân la 1/2 din în l ime; - num rul de corpuri trebuie s fie în raportul de 1/2 pân la 1 fa de produsul dintre lungime i în l ime. Se cere algoritmul de acceptare al unei comenzi i de calcul al pre ului. 1.38. Fie func ia f:[a,b]

, dat de

ax 2 + bx , daca a ≤ x ≤ (a + b) / 2 f(x) =

18 ax 2 + bx , daca (a + b) / 2 < x ≤ b x+2

S se calculeze valoarea lui f pentru x [a,b].

13

1.39. Se cere un algoritm pentru calculul aproximativ al r d cinii unei ecua ii f(x)=0, unde f:(a,b) continu

i monoton , folosind metoda combinat a coardei i a tangentei. Cu metoda dedus , s se calculeze Indica ie. Se va lua f(x) = xn - M, iar intervalul (a,b), se înlocuie te cu [0,M].

n

este

M 19.

1.40. Dintr-o urn cu m bile (m>1), numerotate de la 1 la m, se extrage la întâmplare o bil . S se scrie un algoritm pentru calculul probabilit ii ca num rul înscris pe bila extras s fie prim. 1.41. Un mobil efectueaz o mi care oscilatorie armonic . tiind c pentru elonga iile x1=2 cm i x2=3 cm, mobilul are vitezele v1=5m/s i respectiv v2=4m/s, s se calculeze amplitudinea i perioada mi c rii oscilatorii a mobilului. Indica ie. Se tie c PI=3.14 i se ine seama c amplitudinea, respectiv perioada mi c rii oscilatorie a mobilului sunt date de

A=

x12 v 22 - x 22 v12 x12 - x 22 ; T = 2PI 20 v 22 - v12 v 22 - v12

1.42. Se dau punctele A, B, C, D prin coordonatele lor în plan. Citindu-se coordonatele acestor puncte, s se stabileasc dac ele sunt vârfurile unui dreptunghi sau nu sunt. 1.43. Se dau punctele A, B, C prin coordonatele lor rectangulare. S se determine punctul D tiind c el este piciorul perpendicularei dus din A pe BC. 1.44. Se dau punctele A, B, C, D prin coordonatele lor în plan. S se determine punctul E pe segmentul AB i punctul F pe segmentul CD astfel încât distan a dintre E i F s fie minim . 1.45. Se dau punctele A, B, C, D prin coordonatele lor în plan. Dreapta ce trece prin A i B, cercul de centru (0,2) i raz 5 i parabola de ecua ie y=x2+1 determin o împ r ire a planului în opt regiuni interioare. S se determine dac punctele C i D se afl în aceea i regiune sau nu. 1.46. Se dau n {1,2,...,366} i a num r de an al secolului nostru. S se precizeze data corespunz toare celei de a na zi a anului a sub forma (lun , zi). 1.47. Se d num rul n 2020.

. S se tip reasc acest num r în sistemul de numera ie roman.

1.48. tiind c 1 ianuarie 1994 a fost într-o zi de sâmb t , s se determine în ce zi a s pt mânii va fi 1 ianuarie

1.49. Se consider trei rezervoare cilindrice care con in benzin de trei calit i. Se cere situa ia livr rilor s pt mânale, livr rile zilnice înregistrându-se secven ial. S se precizeze beneficiarul c ruia i s-a livrat cantitatea maxim de benzin .

14

15

CAPITOLUL 2

PROBLEME CU IRURI DE NUMERE 2.1. NUMERE DISTINCTE Se dau n i numerele întregi x1,x2, ...,xn. Se cere s se re in într-un vector Y toate numerele, dar f r a repeta vreunul, deci Y are numai componente distincte. Specificarea problemei: DATE n, (xi, i=1,n); REZULTATE (yj, j=1,k);

{ xiZ, pentru i=1,2,...,n } { X=Y, unde X este } { mul imea ce con ine toate numerele xi, i=1,n, } { iar Y =mul imea ce con ine pe yj, j=1,k i yl yj pentru l j}

Variabilele intermediare folosite i semnifica ia lor, precum i metoda folosit vor fi rezultatul rafin rilor succesive i vor fi în elese din textul versiunilor respective. ALGORITMUL DISTINCTE ESTE: DATE n, (xi, i=1,n); FIE y1:=x1; k:=1; *Examineaz celelalte numere i dac este cazul pune-le în Y. REZULTATE (yj, j=1,k); SF-ALGORITM

{ Versiunea 1 }

Pentru a parcurge celelalte numere avem nevoie de un contor, fie el i, i de folosirea propozi iei PENTRU. Ajungem la: ALGORITMUL DISTINCTE ESTE: DATE n, (xi, i=1,n); FIE y1:=x1; k:=1; PENTRU i:=2,n EXECUT *Verific dac xi apar ine lui Y. *Dac nu apar ine atunci adaug pe xi la Y. SF-PENTRU REZULTATE (yj, j=1,k); SF-ALGORITM

{ Versiunea 2 }

Decizia ce trebuie luat este cum s verific m apartenen a unui element u la mul imea Y. Pentru aceasta vom re ine în indicatorul ind cele dou situa ii posibile: 0 pentru apartenen i pozitiv în caz contrar. Acest calcul se poate face folosind urm toarele propozi ii: ind:=1; C TTIMP (ind1) i (ind<=k) EXECUT DAC xi=yind ATUNCI ind:=0 ALTFEL ind:=ind+1 SF-DAC SF-C TTIMP

17

Cu acestea ajungem la versiunea final a algoritmului dorit. ALGORITMUL DISTINCTE ESTE: DATE n, (xi, i=1,n); FIE y1:=x1; k:=1; PENTRU i:=2,n EXECUT ind:=1; C TTIMP (ind1) i (ind<=k) EXECUT DAC xi=yind ATUNCI ind:=0 ALTFEL ind:=ind+1 SF-DAC SF-C TTIMP DAC ind>0 ATUNCI k:=k+1; yk:=xi SF-DAC SF-PENTRU REZULTATE (yj, j=1,k); SF-ALGORITM

{ Versiunea final } { xiZ, pentru i=1,2,...,n } {Verific dac xi apar ine lui Y}

{Dac nu apar ine atunci adaug pe xi la Y}

{X=Y, unde X este mul imea ce con ine } { toate numerele xi, i=1,n, iar Y este mul imea } { ce con ine pe yj, j=1,k i yl yj pentru l j }

Programul Pascal corespunz tor este: PROGRAM DISTINCTE; VAR n, i,j, k, ind : integer; X, Y : array[1..100] of integer; BEGIN Writeln('Se da vectorul X cu n componente reale'); Writeln('Se pun in Y toate valorile ce apar in X'); Write(' n='); readln(n); For i:=1 to n do begin write('x(',i,')='); readln(x[i]) end; y[1]:=x[1]; k:=1; For i:=2 to n do begin ind:=1; While (ind>0) and (ind<=k) do If x[i]=y[ind] then ind:=0 else ind:=ind+1; IF ind>0 then begin k:=k+1; y[k]:=x[i] end; end; Writeln; Writeln(' Numerele distincte sunt'); For j:=1 to k do write(y[j]:5); readln

18

{ Programul 2.1. Retine valorile distincte } { num rul numerelor date } { contor - variabile de lucru } { num rul valorilor distincte g site } { indicator; retine daca x[i] este in Y } { Vector cu numerele date } { Vector cu numerele distincte }

{ Verifica daca } { x[i] apar ine lui Y }

{ Dac nu apar ine lui Y } { atunci adaug pe x[i] la Y } { Tip re te rezultatele }

END.

2.2. IR DERIVAT DIN NUMERELE NATURALE Se consider

irul 1,2,1,3,2,1,4,2,2,5,4,3,2,1,6,2,2,3,3,3,7,6,...

ob inut din irul numerelor naturale prin înlocuirea fiec rui num r natural n printr-un grup de numere, dup urm toarele reguli: num rul prim p este înlocuit prin numerele p,p-1,...3,2,1, iar num rul compus c este înlocuit prin c urmat de to i divizorii s i proprii, un divizor d repetându-se de d ori. Dându-se num rul natural n, se cere s se tip reasc primele n numere din irul dat. Specificarea problemei. Se d un num r natural n i irul de numere naturale descris mai sus. Se cere tip rirea primelor n numere din irul dat. Aparent problema este complet specificat , ceea ce nu e complet adev rat. Ne d m seama de acest lucru dac încerc m s preciz m ce rezultate se vor re ine în memoria calculatorului. Este posibil ca în memorie s re inem toate numerele cerute într-un vector X sub forma Y = ( y1 , y 2 ,..., y n ) 21, sau s nu le re inem în memorie ci doar s le afi m pe ecran. De fapt exist o variant simplificat a problemei de mai sus în care se cere s se ob in doar al n-lea num r din irul dat. Specificarea problemei, pentru tip rirea celor n numere, f r re inerea lor în memorie. DATE n; REZULTATE afi area primelor n numere din irul men ionat.

{ nN, n>0 }

Pentru a concepe un algoritm de rezolvare, în ambele variante se parcurge irul dat, re inând sub numele t termenul curent al irului, iar sub numele i pozi ia acestui termen în vector. Prin k vom nota num rul natural din care se ob ine grupul de termeni din care face parte t, iar prin j indicele lui t în acest grup. Indicatorul ind va primi valoarea 1 dac num rul k este prim i 0 în caz contrar. Algoritmul pentru rezolvarea problemei este dat în continuare. Algoritmul GENERARE1 este: DATE n; Fie i:=1; t:=1; tip re te t; k:=2; ind:=1; Câttimp i
{ varianta1 } { nN, n>0 }

{ Pentru cazul k este prim }

Pentru a genera urm torul termen din ir va trebui s inem seama de valoarea lui ind, prin care tim dac num rul k este prim sau nu este prim. Pentru a decide dac un num r k este prim sau nu, vom verifica dac k se divide cu un num r

19

mai mic decât el i diferit de 1. Secven a de propozi ii prin care se calculeaz valoarea lui ind este urm toarea: Fie ind:=0; Pentru j:=2,k/2 execut Dac k mod j = 0 atunci ind:=1 sf-dac sf-pentru inând seama de cele men ionate mai sus ajungem la urm toarea variant a algoritmului: Algoritmul GENERARE1 este : DATE n; Fie i:=1; t:=1; Tip re te t; k:=2; ind:=1; Cât timp id sf-repet sf-dac d:=d+1 sf-cât timp; sf-dac k:=k+1; Fie ind:=1; Pentru j:=2,k-1 execut Dac k mod j = 0 atunci ind:=0 sf-dac sf-pentru sf-cât timp sf-algoritm.

{ varianta final } { nN, n>0 }

Pentru a re ine termenii dori i într-un ir Y este suficient s înlocuim propozi ia "Tip re te t" prin propozi ia " Y i 22:=t". Transcriind în Pascal se ob ine urm torul program: Program SIR; Var n, i, j, k, d, t, ind : integer;

20

{ Programul 2.2. Tip re te n termeni dintr-un ir } { Num rul termenilor ce trebuie tip ri i } { Contor = num rul termenilor tip ri i } { Contor = de cate ori s-a tip rit d ! } { Num r natural din care se ob in ultimii termeni } { d va lua ca valori divizorii lui k } { t = termenul curent din ir } { indicator ce retine daca este k prim }

Begin for i:=1 to 20 do writeln; Writeln('Se tip resc n termeni dintr-un ir'); write('Da i n='); Readln(n); i:=1; t:=1; write(t); k:=2; ind:=1; While i=1) do begin i:=i+1; write(t:5); t:=t-1; end else begin d:=2; i:=i+1; write(k:5); while (dd; end; d:=d+1 end; end; k:=k+1; ind:=1; For j:=2 to k-1 do If k mod j = 0 then ind:=0; end {while}; readln(d); end. 2.3. PROBLEME PROPUSE. Pentru problemele propuse mai jos se cere s se descrie în limbajul Pseudocod un algoritm de rezolvare, precizând i semnifica ia variabilelor folosite. De asemenea, s se scrie programul Pascal corespunz tor. 2.1. Se d num rul natural n > 1. S se genereze to i divizorii pozitivi

d 1 ,d 2 ,...,d m 23 ai num rului n.

2.2. S se genereze toate numerele prime mai mici decât num rul natural n dat. 2.3. Se dau m,n

+.

S se determine primele n cifre din scrierea frac iei 1/m ca frac ie zecimal .

2.4. Se d num rul natural m > 1. S se formeze vectorul ale c rui componente sunt primele m numere din irul lui Fibonacci, definit prin n1=n2=1 i nk+1=nk+nk-1 pentru k=2,3,... . 2.5. Se d num rul natural n > 1. S se tip reasc triunghiul lui Pascal, având în linia m toate combin rile C(m,k) de m obiecte luate câte k, k=0,m, pentru m=1,2,...,n. Se va folosi rela ia de recuren : C(m,k) = C(m-1,k)+C(m-1,k-1) deci elementele liniei m se calculeaz din elementele liniei m-1 (precedente). 2.6. Se dau m,k

+.

S se determine num rul n al cifrelor i cele n cifre din scrierea num rului întreg mk =

21

(c1c2c3...cn)10. 2.7. Se dau num rul natural n > 1 i X maxime din X.

n

. S se determine indicele componentei minime i indicele componentei

2.8. Se dau num rul natural n > 1 i numerele x1, x2, ..., xn. S se g seasc toate pozi iile care se afl valoarea maxim .

p1 , p2 ,..., p k 24 pe

2.9. Se dau num rul natural n > 1 i numerele x1, x2, ..., xn. S se verifice dac numerele date sunt în progresie aritmetic sau geometric , calculând indicatorul Ind definit astfel: Ind = 1, dac numerele sunt în progresie aritmetic , Ind = 2, dac numerele sunt în progresie geometric , Ind = 3, în caz contrar. 2.10. Se dau num rul natural n > 1 i numerele x1, x2, ..., xn. S se g seasc media numerelor date, num rul valorilor pozitive, produsul valorilor negative i s se tip reasc numerele mai mari decât 100. 2.11. Se dau num rul natural n > 1 i numerele x1, x2, ..., xn. S se ordoneze cresc tor primele k numere i descresc tor celelalte numere, pentru k dat, k{1,2,...,n}.

y1 ,

2.12. Se dau num rul natural n > 1 i numerele x1, x2, ..., xn. S se g seasc toate numerele distincte y 2 ,..., y m 25 din irul X precum i frecven ele acestor numere între numerele date.

2.13. Se dau num rul natural n > 1 i numerele x1, x2, ..., xn. S se calculeze yj=x1*x1+x2*x2+...+xj*xj, pentru j=1,2,...,n i M = max{xj*yj j=1,n }. 2.14. Se dau num rul natural n > 1 i numerele x1, x2, ..., xn. S se determine cel mai mare num r negativ i pozi iile pe care se afl el în irul dat. 2.15. Se dau num rul natural n > 1 i numerele x1, x2, ..., xn. S se calculeze

yi =

max{ x j | x j > 0, j = 1,i }, daca i este par ( x1 + x 2 +...+ x i ) / i,

daca i este impar

26

pentru i=1,2,...,n. 2.16. Se dau num rul natural n > 1 i numerele x1, x2, ..., xn. S se formeze vectorul Y=(y1,y2,...,yn), unde yi ia valoarea 1 dac xi, xi+1, xi+2 pot fi lungimile laturilor unui triunghi i 0 în caz contrar, pentru i=1,2,...,n. Numerele xn+1, xn+2 se iau egale cu xn. 2.17. Se dau num rul natural n > 1 i numerele x1, x2, ..., xn. S se determine

yi =

max{ x j | j = i,n }, daca i este par mi ,

daca i este impar

27

unde mi este num rul componentelor vectorului X egale cu xi, pentru i=1,2,...,n. 2.18. Se dau num rul natural n > 1 i numerele x1, x2,..., xn.

22

S se calculeze componentele vectorului

Y = ( y1 , y 2 ,..., y n ). 28 Componenta yi este media aritmetic a componentelor pozitive de rang mai mic sau egal cu i ale vectorului X, în cazul în care exist componente pozitive, respectiv -1 în caz contrar. 2.19. Se dau num rul natural n > 1 i numerele x1, x2, ..., xn. S se calculeze yi pentru i=1,n, tiind c y1 = (x1+x2)/2, y2 = (x1+x2+x3)/3, yn = (xn-1+xn)/2, yn-1 = (xn-2+xn-1+xn)/3, iar yk este media numerelor xk-2, xk-1, xk, xk+1, xk+2, pentru k=3,4,...,n-2. 2.20. Se dau num rul natural n > 1 i numerele x1, x2,..., xn. S se determine num rul k al numerelor negative din irul X i mediile vi pentru i=1,2,...,k-1. Prin vi s-a notat media numerelor pozitive cuprinse între al i-lea i al i+1-lea num r negativ, dac exist numere pozitive, respectiv 0 în caz contrar. 2.21. Se dau num rul natural n > 1 i numerele x1, x2,..., xn. S se re in toate numerele distincte y1,y2,...,yk i s se calculeze frecven ele de apari ie ale acestor numere în irul dat. 2.22. Se dau num rul natural n > 1 i numerele x1, x2,..., xn. S se determine vectorul Y=(y1,y2,...,yn), unde yi este egal cu num rul valorilor din irul dat mai mari decât xi, pentru i=1,n. 2.23. Se dau num rul natural n > 1 i numerele x1, x2,..., xn. Dac yi este num rul termenilor mul imii {xjxj<xi ,j 1 i X n. S se determine vectorul Y=(y1,y2,...,yn), unde yi este pozi ia valorii minime în secven a de numere x1,x2,...,xi (cea mai mic dac exist mai multe pozi ii). 2.25. Se dau num rul natural n > 1 i numerele x1, x2,..., xn. S se calculeze primele k momente m1, m2,..., mk. Prin momentul de ordinul j, notat mj, se în elege media aritmetic a puterilor de exponent j ale numerelor date. 2.26. Se dau num rul natural n > 1 i numerele x1, x2,..., xn. Dac m1 i m2 sunt primele dou momente (vezi problema 2.25) s se calculeze s, unde s2=m2-m1*m1 i fj, j=1,9, dac fk este num rul elementelor mul imii { x i | m1 - k * s < x i < m1 + k * s} 29. 2.27. Se dau num rul natural n > 1 i numerele x1, x2,..., xn. Secven a xi, xi+1,..., xi+p se nume te scar (de lungime p) dac xi<xi+1<...<xi+p. Se cere s se tip reasc cea mai lung scar din irul dat i pozi ia i din ir la care începe aceast scar . 2.28. Se dau num rul natural n > 1 i numerele x1, x2,..., xn. S se g seasc permutarea o1, o2,..., on a indicilor 1,2,...,n astfel încât x o1 ≥ x o2 ≥ ... ≥ x o n . 30 2.29. Se dau a

,n

i numerele reale x1, x2,..., xn. S se determine cardinalul (num rul elementelor) mul imii

{ i | x i ≥ a } 31 i indicatorul r definit astfel:

r = i, dac exist i pentru care a=xi, (cel mai mic i) r = 0, în caz contrar. 2.30. Se dau a , n i numerele reale x1, x2,..., xn. S se determine indicele i (cel mai mic, dac exist mai mul i) pentru care valoarea xi este cea mai apropiat de a. 2.31. Se dau a , n i numerele reale x1, x2,..., xn. S se rearanjeze aceste numere astfel încât toate numerele mai mici decât a s fie înaintea tuturor numerelor egale cu a sau mai mari decât a, cu cât mai pu ine schimb ri, deci f r a ordona tot irul. 2.32. Se dau a

,n

i numerele reale x1, x2,..., xn. S se determine vectorul Z cu componentele

23

zi =

2.33. Se dau a

x1 + x 2 +...+ x i , daca x i > a, 32 max{ x i , x i+1 ,..., x n }, daca x i ≤ a.

,n

i numerele reale

x1 , x 2 ,..., x n 33. S se elimine din irul X toate elementele mai mici

decât a. 2.34. Se dau a ,n distan a lor fa de num rul real a.

i numerele reale

x1 , x 2 ,..., x n 34. S se ordoneze numerele date cresc tor dup

2.35. Se dau n , numerele reale a, b, a
x 2 ,..., x n 35. S se (i, x i ) 36 pentru care

x i 37 [a,b]. 2.36. Se dau n , numerele reale a, b, a
x1 , x 2 ,..., x n 38. S se re in în

, numerele reale a, b, a
x i , y i 40, i=1,n. d = | x1 - y1|+| x 2 - y 2 |+...+| x n - y n | 41 i v = max { min{ x i , y i }| i = 1,n} 42. 2.38.

Se

dau

n

i

numerele

reale

S

se

calculeze

2.39. Se dau n care xp=yp.

i numerele reale

x i , y i 43, i=1,2,...,n. S se re in în i1 , i2 ,..., ik 44 toate pozi iile p pentru

2.40. Se dau n

i numerele reale

x i , y i 45, i=1,2,...,n. S se calculeze

zi =

max{ x i + y i }, max{ x i + y i },

daca x i ≤ 0 , daca x i > 0,

46

pentru i=1,2,...,n.

x i , y i 47, i=1,2,...,n. S se calculeze m = ( x1 + x 2 +...+ x n ) / n 48 i d = ( x1 * x1 + x 2 * x 2 +...+ x n * x n ) / n 49 i s se tip reasc to i indicii i pentru care | x i - m|< 3d 50. 2.41. Se dau n

2.42. Se dau n

i numerele reale

i numerele reale

zi = pentru i=1,2,...,n i

24

x i , y i 51, i=1,2,...,n. S se calculeze

daca i este impar , xi + yi , 52 max{ x1 ,x 2 ,...,x i }, daca i este par ,

v = min{ z1 , z 2 ,..., z n } 53.

2.43. Se dau n

i numerele reale

ci =

x i , y i 54, i =1,2,...,n. S se calculeze

x i , daca x i < y i , 0 , daca x i = y i , 55 y i , daca x i > y i ,

pentru i=1,2,...,n. 2.44. Se dau n

i numerele reale

x i , y i 56, i=1,2,...,n. S se calculeze

daca x i < y i , 0, daca x i = y i , 57 max{| y i |,...,| y n | }, daca x i > y i ,

( x1 + x 2 +...+ x i ) / i, zi =

pentru i=1,2,...,n.

x i , y i 58, i=1,2,...,n. S se calculeze E = min{| x1|,| y1| } + ...+ min{| x n |,| y n | }, 59 i s se determine elementele mul imii { i | x i * x i > E} 60. Se dau n i numerele reale x i , y i 61,i=1,2,...,n. S se calculeze 2.45. Se dau n

i numerele reale

s1 = ( y1 + y 2 + ... + y n ), s2 = ( y1 * x1 + y 2 * x 2 +...+ y n * x n ) / s1, 62 s3 = ( y1 * x1 * x1 + y 2 * x 2 * x 2 +...+ y n * x n * x n ) / s1, i m = cardinalul mul imii 2.47. Se dau n

zi = pentru i=1,2,...,n. 2.48. Se dau n

{ x i | 3(s3 - s2* s2) > | x i - s2| } 63. i numerele reale

x i , y i 64, i=1,2,...,n. S se formeze vectorul Z cu componentele

max{ x1 + x 2 +...+ x i ) / i, y i }, daca y i ≥ 0, 65 min{ x i ,( y1 + y 2 +...+ y i ) / i}, daca y i < 0, i numerele reale

x i , y i 66, i=1,2,...,n. S se calculeze

25

daca x i < y i , max{ min{ x1 , x 2 ,..., x i }, 0}, daca x i = y i , 67 max{ x1 , x 2 ,..., x i },

zi =

min{ y i , y i+1 ,..., y n },

daca x i > y i ,

pentru i=1,2,...,n. 2.49. Se dau n

i numerele reale

ci =

x i , y i 68, i=1,2,...,n. S se calculeze

( x1 + x 2 +...+ x i ) / i, max{ x i , y1 , y 2 ,..., y i },

daca x i y i < 0, daca x i y i = 0, 69

min{ x i , x i+1 ,..., x n , y i },

daca x i y i > 0,

pentru i=1,2,...,n. 2.50. Se dau n i numerele reale x i , y i 70, i=1,2,...,n. S se re in pozi iile vectori coincid. S se elimine din vectorii X i Y termenii de pe aceste pozi ii. 2.51. Se dau n

i numerele reale

i1 , i2 , ... , i k 71, pe care cei doi

x i , y i 72, i=1,2,...,n. S se determine vectorul M = ( m1 , m2 ,..., mn ) 73,

mi 74 este pozi ia componentei maxime a vectorului ( x1 , x 2 ,..., x i , y i , y i+1 ,..., y n ) 75 (dac exist mai multe, pozi ia primei valori maxime).

unde

2.52. Se dau n i X,Y n. S se determine pozi iile i0 i j0 cu urm toarea proprietate: exist m componente consecutive din cei doi vectori, începând cu pozi iile i0, respectiv j0, care coincid i m este cel mai mare posibil. În cazul în care nu exist pozi ii cu aceast proprietate, i0 i j0 vor fi n+1. 2.53. Se dau n

x i , y i 76, i=1,2,...,n. S se calculeze E = | x1 - y1| + | x 2 - y 2 | + ... + | x n - y n | 77 i numerele reale

i

ci =

daca |x i - y i | < E, x i / ( y i * y i + 1), max{ x i , y1 , y 2 ,..., y i }, daca | x i - y i | = E, 78 min{ x i , x i+1 ,..., x n , y i },

daca | x i - y i | > E,

pentru i=1,2,...,n. 2.54. Se dau n i numerele reale x i , y i , 79 i=1,2,...,n. Dac se depun direct toate numerele distincte în irul Z ordonat cresc tor: z1 < z 2 < ... < z k 81, deci f r a mai fi necesar ordonarea irului Z.

x1 < x 2 <...< x n si y1 < y 2 <...< y n 80 s

2.55. Se dau a , n i perechile ( x i , y i ) 82, i=1,2,...,n de numere reale. S se determine num rul punctelor (xi,yi) din plan care se afl în interiorul cercului de raz a i centru (0,0).

26

2.56. Se dau a

, n

i perechile

( x i , y i ), 83 i=1,2,...,n de numere reale. S se determine indicii

i1 ,i2 ,...,ik 84 pentru care punctele ( x i , y i ) 85 din plan se afl în interiorul cercului de raz a i centru (0,0). , n 2.57. Se dau a valorilor yi mai mari decât a i

zi =

( x i , y i ) 86, i=1,2,...,n de numere reale. S se calculeze num rul m al

i perechile

( x1 + x 2 +...+ x i ) / i, max{0, x i , y i },

daca i < m, daca i = m,

87

| x1 - y1|+| x 2 - y 2 |+...+| x i - y i |, daca i > m. pentru i=1,2,...,n. 2.58. Se dau m,n

i cifrele zecimale

a i , 88 i=1,2,...,m i b j , 89 j=1,2,...,n. Dac numerele întregi A i B au

reprezent rile în baza 10 date de aceste cifre, deci

A = ( a1 a 2 ... a m )10 si

90

B = ( b1 b2 ...bn )10 ci , 91 i=1,2,...,r, ale reprezent rii num rului întreg C=A+B. 2.59. Se dau m,n i cifrele zecimale a i , 92 i=1,2,...,m i b j , 93 j=1,2,...,n. Dac A i B sunt numerele definite

s se calculeze cifrele

în problema 2.58, s se determine indicatorul kod definit astfel: kod = -2, dac cel pu in o valoare a i 94 nu este corect , kod = kod = kod = kod =

-1, 0, 1, 2,

dac dac dac dac

cel pu in o valoare A = B, A < B, A > B.

2.60. Se dau m,n reprezent rile în baza 10:

bi 95 nu este corect ,

i cifrele zecimale

a i , 96 i=1,2,...,m i b j , 97 j=1,2,...,n. Dac numerele reale A i B au

A = ( a1 a 2 ...a r ,a r+1 ...a m )10 98 B = ( b1 b2 ...bs ,bs+1 ...bn )10 99

pentru r<m i s B. 2.61. Se d n

, n>1. Dac X este irul: 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, ... ob inut din irul numerelor naturale prin înlocuirea fiec rui num r natural k cu secven a de numere 1, 2, 3, ..., k, s se construiasc vectorul V = ( v1 , v 2 ,... v n ) 100 tiind c cele n componente ale sale sunt primii n termeni ai irului X. 2.62. Se d n

, n>1. Dac X este irul: 3, 5, 5, 7, 11, 13, 17, 19, ... ob inut prin scrierea tuturor numerelor prime p i q, unde p i q sunt gemeni, adic numere prime cu q-p=2, s se construiasc vectorul V = ( v1 , v 2 ,... v n ) 101 tiind c cele n componente ale sale sunt primii n termeni ai irului X.

27

2.63. Se d n , n>1. S se construiasc vectorul V = ( v1 , v 2 ,... v n ) 102 tiind c cele n componente ale sale sunt primii n termeni ai irului: 3, 4, 5, 5, 12, 13, 6, 8, 10, ... ob inut prin scrierea consecutiv a tuturor tripletelor de numere pitagorice p, q, r, p
p2 + q2 = r 2 103.

2.64. Se dau m,n , n>1. S se construiasc vectorul V = ( v1 , v 2 ,... v n ) 104 tiind c cele n componente ale sale sunt primii n termeni consecutivi ai irului X: 1, 2, 3, 4, 2, 5, 6, 2, 3, 7, 8, 2, ... ob inut prin scrierea numerelor naturale i a divizorilor proprii ai acestor numere, începând cu x m 105 (f r a re ine

x i 106 în calculator). 2.65. Se dau m,n , n>1. S se construiasc vectorul V = ( v1 , v 2 ,... v n ) 107 tiind c cele n componente ale vectorului V sunt termeni consecutivi ai irului X: 1,1,2,1,2,3,4,4,4,4,1,2,3,4,5,6,6,... ob inut din irul numerelor naturale prin înlocuirea fiec rui num r natural prim p prin secven a 1,2,...,p i a num rului neprim c prin scrierea lui de c ori, începând cu x m 108 (f r a re ine termenii x i 109 în calculator). termenii

2.66. Se dau m,n , n>1. S se construiasc vectorul V = ( v1 , v 2 ,... v n ) 110 tiind c cele n componente ale vectorului V sunt termeni consecutivi ai irului X: 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 6, 7, ... ob inut din irul numerelor naturale prin înlocuirea fiec rui num r prim p cu un grup de p numere toate egale cu p, începând cu x m 111 (f r a re ine termenii x i 112 în calculator). 2.67. Se dau m,n , n>1. S se construiasc vectorul V = ( v1 , v 2 ,... v n ) 113 tiind c cele n componente ale vectorului V sunt termeni consecutivi ai irului X: 1, 2, 3, 4, 2, 2, 5, 6, 2, 3, 3, 3, 7, 8, 2, ... ob inut prin scrierea numerelor naturale i a divizorilor proprii ai acestor numere, ultimul divizor d repetându-se de d ori, începând cu x m 114 (f r a re ine termenii x i 115 în calculator). 2.68. Se dau m,n , n>1. S se construiasc vectorul V = ( v1 , v 2 ,... v n ) 116 tiind c cele n componente ale vectorului V sunt termeni consecutivi ai irului X: 1, 2, 3, 2, 5, 2, 3, 7, 2, 4, 3, 2, 5, 11, ... ob inut prin scrierea numerelor naturale i înlocuirea fiec rui num r compus prin to i divizorii s i proprii, începând cu x m 117 (f r a re ine termenii x i 118 în calculator). 2.69. Se dau n

i seria ∞

1 1 1 . 119 n=1 3n - 2 3n - 1 3n V = ( v1 , v 2 ,..., v n ) 120 tiind c cele n componente ale vectorului V sunt sume par iale ale acestei serii, v1 = s20 , v i = s20+5i , 121 i=2,3,...,n, unde sk 122 este suma primilor k termeni. S se construiasc vectorul

2.70. Se d n

i seria ∞

n=1

28

n-1

(-1 )

4 1 1 2n-1 + 2n-1 123 2n - 1 2 3

V = ( v1 , v 2 ,..., v n ) 124 tiind c cele n componente ale vectorului V sunt sume par iale ale acestei serii, v1 = s20 , v i = s20+5i , 125 i=2,3,...,n, unde sk 126 este suma primilor k termeni. S se construiasc vectorul

2.71. Se dau n

i se cunoa te seria

3

3 1 1* 2 1* 2* 3 (1+ + + +... ) 127 2 6 6* 10 6* 10* 14

V = ( v1 , v 2 ,..., v n ) 128 tiind c cele n componente ale vectorului V sunt sume par iale ale = , = v1 s20 v i s20+5i , 129 i=2,3,...,n, unde sk 130 este suma primilor k termeni.

S se construiasc vectorul acestei serii,

2.72. Se dau n,m

i se cunoa te seria

1 1* 2 1* 2* 3 2 1+ + + +... 131 3 3* 5 3* 5* 7 V = ( v1 , v 2 ,..., v n ) 132 tiind c cele n componente ale vectorului V sunt sume par iale ale acestei serii, v1 = s20 , v i = s20+mi , 133 i=2,3,...,n, unde sk 134 este suma primilor k termeni. S se construiasc vectorul

2.73. Se dau n,m

i se cunoa te seria

ui = 1+

1 1 1 1 1 1 + + +... 135 3 9 5 92 7 93

V = ( v1 , v 2 ,..., v n ) 136 tiind c cele n componente ale vectorului V sunt sume par iale ale acestei serii, v1 = s20 , v i = s20+mi , 137 i=2,3,...,n, unde sk 138 este suma primilor k termeni. S se construiasc vectorul

2.74. Se dau n,m,l

i se cunoa te seria

1 1* 2 1* 2* 3 1* 2* 3* 4 1+ + + + +... 139 3* 3 3* 5* 5 3* 5* 7 * 7 3* 5* 7 * 9* 9 V = ( v1 , v 2 ,..., v n ) 140 tiind c cele n componente ale vectorului V sunt sume par iale ale acestei serii, v1 = sm , v i = sm+l*i , 141 i=2,3,...,n, unde sk 142 este suma primilor k termeni. S se construiasc vectorul

2.75. Se dau n,m,l

1+

i se cunoa te seria

1 1* 2 1* 2* 3 1* 2* 3* 4 + + + +... 143 3* 3 3* 5* 5 3* 5* 7 * 7 3* 5* 7 * 9* 9

V = ( v1 , v 2 ,..., v n ) 144 tiind c cele n componente ale vectorului V sunt sume par iale ale v1 = sl , v i = sl+mi , 145 i=2,3,...,n, unde sk 146 este suma primilor k termeni.

S se construiasc vectorul acestei serii,

2.76. Se cunoa te seria convergent din problema 2.69. S se determine suma par ial sn a primilor n termeni pentru care | sn - sn-1| < ε 147 pentru dat, n fiind cel mai mic num r natural posibil.

29

2.77. Se cunoa te seria convergent din problema 2.70. S se determine suma par ial sn a primilor n termeni pentru care | sn - sn-1| < ε 148 pentru dat, n fiind cel mai mic num r natural posibil. 2.78. Se cunoa te seria convergent din problema 2.71. S se determine suma par ial sn a primilor n termeni pentru care | sn - sn-1| < ε 149 pentru dat, n fiind cel mai mic num r natural posibil. 2.79. Se cunoa te seria convergent din problema 2.72. S se determine suma par ial sn a primilor n termeni pentru care | sn - sn-1| < ε 150 pentru dat, n fiind cel mai mic num r natural posibil. 2.80. Se cunoa te seria convergent din problema 2.73. S se determine suma par ial sn a primilor n termeni pentru care | sn - sn-1| < ε 151 pentru dat, n fiind cel mai mic num r natural posibil. 2.81. Se cunoa te seria convergent din problema 2.74. S se determine suma par ial sn a primilor n termeni pentru care | sn - sn-1| < ε 152 pentru dat, n fiind cel mai mic num r natural posibil. 2.82. Se cunoa te seria convergent din problema 2.75. S se determine suma par ial sn a primilor n termeni pentru care | sn - sn-1| < ε 153 pentru dat, n fiind cel mai mic num r natural posibil. 2.83.

S

se

tip reasc

primii

n

termeni

ai

irului

(xk)

definit

de

rela ia

de

recuren

x k = ( x k-1 + a / x k -1 ) / 2, 154 pentru a i x0 numere reale date, pentru care | x n - x n-1|< 0.00001, 155 n fiind cel mai mic posibil. 2.84. S se tip reasc primii n termeni ai irului (xk) definit de rela ia de recuren

xk = pentru m

i a, x0

1 a * (m - 1) x k-1 + m-1 , 156 m x k -1

da i, pentru care | x n - x n-1|< 0.00001, 157 n fiind cel mai mic posibil.

2.85. S se tip reasc primii n termeni ai irului (xk) pentru care posibil, în cazul irului

xn = x pentru x

dat.

x3 x5 x 2n+1 n + - ...+(-1 ) * 159 3 5 2n + 1

2.86. S se tip reasc primii n termeni ai irului (xk) pentru care

30

| x n - x n-1|< 0.00001, 158 n fiind cel mai mic

| x n - x n-1|< 0.00001, 160 n fiind cel mai mic

posibil, în cazul irului

x n = 1+ x +

xn x2 +...+ 161 2! n!

2.87. S se tip reasc primii n termeni ai irului (xk) pentru care posibil, în cazul irului

x n = 1+ x + pentru x

dat.

xn x2 +...+ 163 2! n!

2.88. S se tip reasc primii n termeni ai irului (xk) pentru care posibil, în cazul irului

xn = x pentru x

| x n - x n-1|< 0.00001, 162 n fiind cel mai mic

| x n - x n-1|< 0.00001, 164 n fiind cel mai mic

x3 x 2n+1 2n+1 + ... + (-1 ) * 165 3! (2n + 1)!

dat.

2.89. Se d f C2[a,b]. tiind c ecua ia f(x) = 0 admite o solu ie unic r în intervalul [a,b] i c f' i f" nu- i schimb semnul pe [a,b], s se aproximeze r folosind metoda tangentei (a lui Newton), deci folosind faptul c r = lim xn n unde x n+1 = x n - f( x n ) / f ′( x n ), 166 n=0,1,2,... iar x0 este ales unul din capetele intervalului [a,b], notat cu c, i anume cel pentru care f(c)*f"(c)>0. 2.90. Fie f:[a,b] --> o func ie continu . Se tie c ecua ia f(x) = 0 are o singur r d cin în intervalul [a,b]. S se construiasc irul de intervale [ x i , y i ] 167, i =1,2,...,n, definit astfel:

[ x 0 , y0 ] = [a,b] 168 ; 2. [ x i , y i ] 169 se ob ine împ r ind intervalul [ x i-1 , y i-1 ] 170 în trei p r i egale

1.

i luând partea care con ine r d cina; 3. n este cel mai mic num r natural pentru care

y n - x n 171<eps, pentru eps num r pozitiv dat.

31

32

CAPITOLUL 3

PROBLEME REZOLVATE CU AJUTORUL VECTORILOR 3.1. NUM RUL PUNCTELOR DIN CERC Se dau n puncte în plan i un cerc. Se cere num rul punctelor care se afl în interiorul cercului. Rezolvare Punctele se dau prin coordonatele (xi,yi), i=1,2,...,n. Variabila nr va con ine num rul punctelor din interiorul cercului, care se d prin centrul O(a,b) i raza r. Deci specificarea problemei este: DATE n,

(xi,yi, i=1,n), a,b, r; REZULTATE nr;

{ num rul punctelor date } { coordonatele celor n puncte } { coordonatele centrului cercului } { raza cercului dat } { num rul punctelor aflate în interiorul cercului }

Pentru a calcula valoarea lui nr se ini ializeaz cu 0 acest num r i se verific care dintre punctele (xi,yi) au distan a fa de (a,b) mai mic decât r, deci se afl în cerc. Pentru fiecare r spuns afirmativ valoarea lui nr se m re te cu 1. Algoritmul pentru rezolvarea problemei este dat în continuare. Algoritmul PUNCTE_IN_CERC este : DATE n, (xi,yi, i=1,n), a,b, r; Fie nr:=0; Pentru i:=1,n execut 2

Dac ( x i - a) + ( sf-pentru REZULTATE nr; sf-algoritm.

{ num rul punctelor date } { coordonatele celor n puncte } { coordonatele centrului cercului } { raza cercului dat }

y i - b)2 < r 2 172 atunci nr:=nr+1 sf-dac { num rul punctelor aflate în interiorul cercului }

Programul PASCAL este dat în continuare. Program Nr_Puncte_în_cerc; var n, i, nr : integer; a,b, r : real; x,

{Programul 3.1 Nr. puncte într-un cerc} { num rul punctelor date } { variabila de lucru - contor } { num rul punctelor aflate in cerc } { coordonatele centrului cercului } { raza cercului dat } { x[i] = abscisa iar }

33

y:array [1..50] of real;

{ y[i] = ordonata punctului "i" }

begin clrscr; writeln('Programul num r câte dintre n puncte date'); WRITELN('se afla in interiorul unui cerc dat'); for i:=1 to 3 do writeln; repeat write('n='); readln(n) until (n in [1..50]); for i:=1 to n do begin write('x[',i:2,']='); read(x[i]); write(' y[',i:2,']='); readln(y[i]); end; writeln; writeln('Datele privitoare la cerc:'); write('abscisa='); readln(a); write('ordonata='); readln(b); repeat write('raza (>0)=?'); readln(r) until r>0; writeln; { determinarea nr. de puncte interioare cercului } nr:=0; for i:=1 to n do if (x[i]-a)*(x[i]-a)+(y[i]-b)*(y[i]-b)
{ Tip re te rezultatele }

3.3. PROBLEME PROPUSE 3.1. Se d un polinom P(X) cu coeficien i reali. S se calculeze valoarea polinomului P(X) într-un punct x0 dat. 3.2. Se d un polinom P(X) cu coeficien i reali. S se verifice dac un num r dat r este r d cina acestui polinom. 3.3. Se d un polinom P(X) cu coeficien i reali. S se calculeze derivata acestui polinom. 3.4. Se d un polinom P(X) cu coeficien i reali. S se calculeze derivata de ordinul k a polinomului dat. 3.5. Se d un polinom de gradul n cu coeficien i întregi. S se g seasc r d cinile întregi ale polinomului dat. 3.6. Se d un polinom de gradul n cu coeficien i întregi. S se g seasc r d cinile ra ionale ale acestui polinom. 3.7. Se dau dou polinoame P(X) i Q(X). S se calculeze suma lor. 3.8. Se dau dou polinoame P(X) i Q(X). S se calculeze produsul lor. 3.9. Se dau dou polinoame P(X) i Q(X).S se calculeze T(X)=P(Q(X)). 3.10. Se dau m,n

i mul imile

A = { a1 , a 2 ,..., a m } 173 B = { b1 , b2 ,..., bn } S se calculeze C = A B. 3.11. Se dau m,n

i mul imile

A = { a1 , a 2 ,..., a m } 174 B = { b1 , b2 ,..., bn } S se calculeze C = A

B.

3.12. Se dau m,n

36

i mul imile

A = { a1 , a 2 ,..., a m } 175 B = { b1 , b2 ,..., bn } S se calculeze C = A - B. 3.13. Se dau dou numere scrise în baza b. S se calculeze suma i diferen a celor dou numere. 3.14. Se dau dou numere scrise în baza b. S se calculeze produsul celor dou numere. num r.

3.15. Se dau dou numere scrise în baza b. S se g seasc câtul i restul împ r irii primului num r la al doilea 3.16. S se transforme un num r din baza p în baza q. 3.17. Se d o mul ime M de n puncte în plan. S se g seasc punctul cel mai dep rtat de origine. 3.18. Se d o mul ime M de n puncte în plan. S se ordoneze în func ie de distan a lor fa de axa OX.

3.19. Se d o mul ime M de n puncte în plan. S se ordoneze în func ie de distan a lor la originea axelor de coordonate. 3.20. Se d o mul ime M de n puncte în plan. S se g seasc triunghiul de arie minim care are vârfurile în M. M.

3.21. Se d o mul ime M de n puncte în plan. S se g seasc num rul triunghiurilor care au vârfurile în mul imea 3.22. Se d o mul ime M de n puncte în plan. S se determine submul imea maxim de puncte coliniare.

3.23. Se d o mul ime M de n puncte în plan. S se determine submul imea maxim de puncte cu proprietatea c oricare trei sunt necoliniare. 3.24. Se dau n puncte în plan, un cerc i o elips . S se g seasc punctele care sunt în interiorul cercului, dar nu se afl în interiorul elipsei. 3.25. Se dau n puncte în plan i un cerc. S se elimine punctele care se afl în interiorul cercului. 3.26. Se dau n puncte P1,P2,...,Pn în plan i un punct M. S se g seasc câte puncte sunt la o distan de punctul M mai mic decât un num r real r dat. 3.27. Se dau n puncte P1,P2,...,Pn în plan i un punct M. S se calculeze indicatorul Kod definit astfel: Kod = 0, dac poligonul P1P2...Pn nu este convex; Kod este pozitiv dac poligonul este convex: Kod = 1, dac M este interior poligonului; Kod = 2, dac M este pe una din laturile poligonului; Kod = 3, dac M este exterior poligonului. 3.28. Se dau coordonatele vârfurilor unui poligon convex, în ordinea lor. S se g seasc diagonala cea mai lung . 3.31. Se dau n puncte în plan i ecua ia unei drepte. S se numere câte puncte se afl pe dreapt punctul de distan maxim fa de dreapt .

i s se afle

37

3.32. Se dau n cercuri concentrice. S se g seasc inelul de arie maxim delimitat de dou cercuri consecutive. 3.33. Se dau n puncte pe un cerc. S se ordoneze în ordine trigonometric invers . 3.34. O func ie f : {1,2,...,m} ---> {1,2,...,n} se poate reprezenta în calculator printr-un vector F=(F1,F2,...,Fm) cu m componente, unde Fi = f(i). S se verifice dac func ia f, dat prin vectorul F este injectiv . 3.35. Se d o func ie f : {1,2,...,m} ---> {1,2,...,n} reprezentat a a cum se men ioneaz în problema 3.34. S se verifice dac func ia f, dat prin vectorul F este surjectiv . 3.36. Se dau func iile f:{1,2,...,m} --->{1,2,...,n} i g:{1,2,...,n}---> {1,2,...,p}, reprezentate a a cum se men ioneaz în problema 3.34. S se determine compunerea celor dou func ii date. 3.37. O aplica ie f : {1,2,...,n} ---> {1,2,...,n} bijectiv se nume te permutare. Ea se poate reprezenta în calculator a a cum s-a ar tat în problema 3.34. Se d o permutare f. S se determine num rul inversiunilor permut rii f. 3.38. Se d o permutare f a a cum s-a ar tat în problema 3.37. S se determine ordinul permut rii date. Prin ordinul permut rii f se în elege cel mai mic întreg k pentru care fk este aplica ia identic . 3.39. Se d o permutare f a a cum s-a ar tat în problema 3.37. S se calculeze inversa permut rii f. 3.40. Se dau dou permut ri f i g a a cum s-a ar tat în problema 3.37. S se determine compunerea celor dou permut ri date. 3.41. La un concurs de patinaj artistic se cunosc cele n note ob inute de un concurent. S se calculeze punctajul lui, tiind c la calculul mediei nu se ia în considerare nota cea mai mic i cea mai mare ob inut (o singur dat în cazul c sunt dou note egale, deci se face media aritmetic a n-2 note). 3.42. Pentru cei n studen i ai anului întâi se cunosc notele mi, i=1,n, la primul examen. Se cere s se determine num rul studen ilor cu nota 10, num rul studen ilor cu note de 8 i 9 i s se tip reasc lista studen ilor nepromova i. 3.43. Pentru cele 365 de zile ale unui an se cunosc cantit ile de precipita ii zilnice pi, i=1,365. Se cere s se determine num rul zilelor f r precipita ii, mediile lunare i media anual a precipita iilor i s se listeze zilele cu precipita ii ce dep esc cantitatea a. 3.44. Se dau m,n , intervalele [ai-1,ai], i = 1,m i numerele reale x1,x2, ... , xn. Prin frecven a fi se în elege num rul valorilor xj care se afl în intervalul [ai-1,ai]. S se determine frecven ele f1,f2,... ,fm i s se listeze indicii j pentru care xj
38

CAPITOLUL 4

PROBLEME CU MATRICE 4.1. CONSTRUIREA UNEI MATRICE Se dau numerele naturale m i n i un ir de numere reale X(i),i=1,2,...,m x n. S se genereze matricea A, cu m linii i n coloane, definit prin : i• j

xk a(i, j) =

k=1

(i • j - i + 1)

,

(4.1) 176

pentru i=1,m i j=1,n. Pentru rezolvarea problemei, algoritmul pe care-l vom descrie folose te un tablou unidimensional pentru irul X i un tablou bidimensional pentru matricea A. Deci specificarea problemei este: DATE m, n, X; REZULTATE A

{num rul liniilor matricei A} (num rul coloanelor matricei A} {vector ce con ine cele m*n numere date} {Matrice de dimensiune m*n definit de (4.1)}

Deoarece în expresia ce define te elementele matricei A numitorul este întotdeauna nenul (j=1,n este natural i i rel="nofollow">0, natural) nu vom avea probleme la generarea matricei. Pentru a calcula suma elementelor x(k) pentru k de la 1 la i*j vom folosi o variabil auxiliar sum. Variabilele i,j,k sunt variabile de ciclare. Algoritmul pentru rezolvarea problemei este dat în continuare: Algoritmul MATRICE este : Date m, n, X; Pentru i:=1 la m execut Pentru j:=1 la n execut sum:=0; Pentru k:=1 la i*j execut sum:=sum+X(k) sf-pentru; A(i,j):=sum/(i*j-i+1) sf-pentru sf-pentru Rezultate A; sf-algoritm

{Se calculeaz A conform formulei 4.1} {m*n este dimensiunea matricei cerute} {X=(X(i),i=1,m*n) este un vector cu m*n componente date}

{Matrice de dimensiune m*n definit de (4.1)}

Programul PASCAL corespunz tor este urm torul: Program matrice; Type sir=array[1..100] of real;

{ Programul 4.1. Construirea unei matrice A }

39

mat=array[1..10,1..10] of real; Var m,n, {m*n este dimensiunea matricei cerute} i,j,k:integer; {variabile auxiliare} X:sir; {X este un vector cu m*n componente date} A:mat; {Matrice de dimensiune m*n definit de (4.1)} sum:real; {variabil auxiliar ; va con ine o suma} begin Writeln('Se calculeaz o matrice A de dimensiune m*n'); writeln('dandu-se un vector X cu m*n componente'); write(' Da i num rul liniilor matricei : '); readln(m); write(' Dati num rul coloanelor matricei: '); readln(n); writeln(' Da i termenii irului X'); for i:=1 to m*n do begin write('x(',i,')=?'); readln(x[i]) end; for i:=1 to m do for j:=1 to n do begin sum:=0; for k:=1 to i*j do sum:=sum+x[k]; a[i,j]:=sum/(i*j-i+1) end; writeln; writeln; Writeln(' Matricea rezultat este:'); writeln; for i:=1 to m do begin for j:=1 to n do write(a[i,j]:8:1); writeln end; readln end. 4.2. GENERAREA UNEI MATRICE DINTR-UN IR Se dau m,n,k i numerele întregi x1,x2,...,xk. Se cere s se construiasc o matrice A cu m linii i n coloane astfel încât elementele matricei s fie elementele irului în urm toarea ordine: (consider m m=3 i n=4) x1 x6 x7 x12 x2 x5 x8 x11 x3 x4 x9 x10 În cazul în care nu exist suficiente elemente în vectorul X, deci matricea nu se poate construi, se va da un mesaj de eroare. Specificarea problemei este: DATE m,n, k, X; REZULTATE A

{dau dimensiunea matricei} {num rul componentelor irului X} {vector de dimensiune k} {matrice de dimensiune m*n}

Se observ c elementele irului sunt puse în ordine pe coloane i anume pe o coloan de sus în jos, iar pe urm toarea coloan de jos în sus. Pentru a deosebi cele dou cazuri vom folosi o variabil de control notat kod care ia dou valori posibile 0 i 1. Dac valoarea lui kod este 0 atunci pe acea coloan elementele din ir se pun începând cu prima linie i pân la linia a m-a, iar dac valoarea lui kod este 1 atunci pe acea coloan elementele irului se pun începând cu linia a ma i pân la prima linie. Variabile folosite: X - vector ce con ine numerele date, de lungime k;

40

A - matricea cerut ; m,n - dimensiunile matricei; l - indice în ir; kod - variabila de control. Algoritmul corespunz tor este dat în continuare. Algoritmul MATRICE2 este: DATE m,n, k, X; Dac m*n>k atunci Tip re te('Prea pu ine elemente în ir') altfel Fie j:=1; l:=1; kod:=0; Repet Dac kod=0 atunci kod:=1; Pentru i:=1,m execut aij:=xl; l:=l+1 sf-pentru altfel kod:=0; Pentru i:=m,1,-1 execut aij:=xl; l:=l+1 sf-pentru sf-dac pân când j>n sf-repet REZULTATE A sf-dac

{dau dimensiunea matricei} {num rul componentelor irului X} {vector de dimensiune k}

{matrice de dimensiune m*n}

Programul Pascal este: Program matrice2; {Programul 4.2. Matrice dintr-un vector} Type sir = array[1..100] of integer; mat = array[1..10,1..10] of integer; Var m, n, {dimensiunile matricei} i, j, {indici linie-coloana in matricea A} k, {num r natural dat} l, {indice în ir} kod : integer; {variabila de control} X : sir; {vector ce con ine numerele date, de lungime k} A : mat; {matricea cerut } Begin Writeln{'Se constuie te o matrice dintr-un ir de numere'); write('Da i dimensiunile matricei:'); readln(m,n); write('Da i dimensiunea irului:'); readln(k); { Dac elementele irului nu } if m*n > k { "umplu" matricea se } { semnaleaz eroare } then write('Prea pu ine elemente in ir') else begin for i := 1 to k do begin write('x(',i,')='); readln(x[i]) end; j:=1; l:=1; kod:=0; repeat if kod = 0 then begin for i:=1 to m do { pe coloan de sus in jos } begin a[i,j]:= x[l]; l:=l+1 end; kod:=1 {se schimba valoarea lui kod}

41

end end.

end else begin for i:=m downto 1 do begin a[i,j]:=x[l]; l:=l+1 end; kod := 0 end; j := j+1 until j>n; for i:= 1 to m do begin for j := 1 to n do write(a[i,j]:5); writeln end

{ pe coloana } { de jos in sus } { se schimba valoarea lui kod} {se repeta pana când s-a completat coloana n} { tip re te linia i a matricei }

4.3. PROBLEME PROPUSE În cele ce urmeaz vom nota prin Mm,n(D) mul imea matricelor cu m linii i n coloane având toate elementele din domeniul D. În cazul m=n, deci al matricelor p trate, vom nota Mn,n(D) = MPn(D). Prin Z vom nota mul imea numerelor întregi, iar prin R mul imea numerelor reale. Prin Vn(D) se noteaz mul imea vectorilor cu n componente, toate elemente din domeniul D. matricei.

4.1. Se d o matrice A Mm,n(R+). S se calculeze raportul dintre cel mai mic element i cel mai mare element al 4.2. Se d o matrice A Mm,n(R). S se adauge a (n+1)-a coloan acestei matrice, definit prin: n

A(i, j) 177 , pentru i=1,m.

A(i,n+1)= j=1

4.3. Se d o matrice A Mm,n(R+). S se formeze un vector cu n componente, astfel încât componenta a i-a s fie egal cu elementul maxim din coloana a i-a a matricei. 4.4. Se d o matrice A Mm,n(R). S se determine linia i coloana care con in cel mai mic element pozitiv. 4.5. Se d o matrice A Mm,n(R+). Dac vi este valoarea maxim din linia i s se calculeze: w = min{ v i | i = 1,m} 178. 4.6. Se d o matrice A Mm,n(R). S se tip reasc indicii liniilor care con in elemente negative. S se formeze apoi matricea B, ob inut din matricea A prin eliminarea acestor linii. 4.7. Se d o matrice A Mm,n(R+). S se schimbe între ele liniile matricei A astfel ca prima coloan s devin ordonat cresc tor. 4.8. Se d o matrice A Mm,n(R+) i un interval [,]. S se re in într-un vector X toate elementele matricei aflate în intervalul [,]. linie.

4.9. Se d o matrice A Mm,n(R+). Pentru fiecare linie s se scad din elementele sale valoarea minim din acea 4.10. Se d o matrice A Mm,n(R). S se construiasc vectorul X =

42

( x1 , x 2 , ..., x k ) 179 ce reprezint indicii liniilor care con in valori nule. 4.11. Se d o matrice A Mm,n(R). S se tip reasc matricea A completat cu o nou coloan în care elementul din linia a i-a este egal cu cel mai mare num r negativ din linia a i-a, dac exist elemente negative, respectiv cu 10 când nu exist elemente negative. 4.12. Se d o matrice A Mm,n(R+) i numerele naturale l i k (1
o matrice A

Mm,n(R+). S

s1 , s2 ,..., sm 180 s fie ordonat descresc tor, unde

se schimbe între ele liniile matricei astfel încât irul sumelor

n

si =

a ij , i = 1,m 181. j=1

4.19. Se d o matrice A Mm,n(B2), unde B2 ={0,1} i se consider c elementele unei linii sunt cifrele unui num r întreg scris în binar. S se g seasc numerele întregi corespunz toare liniilor matricei. 4.20. Se d o matrice A Mm,n(R+). Pozi ia

( i0 , j 0 ) 182 se nume te punct a dac :

a i0 , j0 183 este maxim pe coloana j0; b) a i0 , j 0 184 este minim pe linia i0 185.

a)

S se tip reasc toate punctele a dac exist astfel de puncte sau un mesaj corespunz tor în caz contrar. 4.21. Se d

o matrice A

Mm,n(R+). S

se formeze matricea B cu m linii

i n coloane unde

2

bij = ( a ij - max ) 186, unde max este cel mai mare element al matricei A. 4.22. Se d o matrice A Mm,n(R+). S se formeze matricea B cu m linii i n coloane unde

bij =

daca i < j a ij , 187 ( a i 1+ a in + a1j + a mj ) / 4, altfel .

4.23. Se d o matrice A Mm,n(R+). Se dau numerele x i y. S se formeze matricea B cu m linii i n coloane unde

43

- 1, daca a ij ∈(x, y) 0, daca a ij ∈{x, y} 188

bij =

1, daca a ij ∉ [x, y]. 4.24. Se d A Mm,n(R). S se formeze matricea B cu m linii i n coloane unde: bij = | max{ a ik | k = 1,2,...,n}| - a ij 189. 4.25. Se d A Mm,n(R+). S se formeze matricea B cu m linii i n coloane, în care elementul bij se define te ca suma elementelor matricei A aflate pe linia i, mai pu in elementul aflat pe coloana j. 4.26. Se d A Mm,n(Z). S se formeze matricele B i C cu m linii i n coloane unde

bij =

a ij , daca a ij este par 190 0, altfel ,

cij =

a ij , daca a ij este impar 191 0, altfel .

4.27. Se d A Mm,n(R+). Se dau numerele reale x, y, z, cu x < y < z. S se formeze matricea B cu m linii i n coloane, unde

0 , daca a ij < x 1 , daca x ≤ a ij < y

bij =

2 , daca y ≤ a ij < z 3 , daca a ij ≥ z.

192

4.28. Se d A Mm,n(R+). S se determine vectorii B i C defini i astfel :

bi = max{ a ij | j = 1,2,...,n } , i = 1,2,...,m m

cj =

a ij bi ,

j = 1,2,...,n.

193

i=1

4.29. Se d A Mm,n(Z). Fiind dat un num r natural p, s se formeze vectorul X cu m componente, unde xi reprezint num rul elementelor din linia a i-a a matricei A care sunt divizibile cu p. 4.30. Se d A MPn(R). S se determine linia l ce con ine cel mai mare element al diagonalei principale i apoi s se schimbe linia i coloana l cu linia, respectiv coloana întâi. 4.31. Se d A Mm,n(R+). S se formeze un vector de n componente, în care componenta vi a vectorului s fie egal cu raportul dintre suma elementelor din linia i i suma elementelor din coloana i.

44

4.32. Se d A MPn(R). S se calculeze E=MDP-MDS, unde MDP este maximul dintre sumele elementelor aflate pe diagonale paralele cu diagonala principal , iar MDS este minimul dintre sumele elementelor aflate pe diagonalele paralele cu diagonala secundar . 4.33. Se d A MPn(R). S se ordoneze liniile i coloanele matricei astfel încât elementele de pe diagonala principal s fie ordonate cresc tor. 4.34. Se d A MPn(R). În fiecare linie s se schimbe între ele elementele care se g sesc pe diagonala principal cu cele care se g sesc pe cea secundar . 4.35. Se d A MPn(R). S se determine vectorii X i Y cu n componente, unde: X(i) = num rul elementelor pozitive din linia i; Y(i) = num rul elementelor negative din coloana i . 4.36. Se d AMPn(R). S se calculeze suma primelor n puteri ale matricei A. 4.37. Se d A MPn(R). S se calculeze matricea P = A*AT, unde AT reprezint transpusa matricei A. 4.38. Se d X Vn(R). S se genereze o matrice A MPn(R) astfel încât elementele matricei s reprezinte elementele vectorului X scrise în urm toarea ordine: X(1) X(2) ... X(n-1) X(n) X(4n-4) X(4n-3) ... X(.) X(n+1) . . ... . . X(3n-2) X(3n-3) ... X(2n) X(2n-1). 4.39. Se d X Vn(R). S se genereze o matrice p trat A de ordin maxim posibil, astfel încât elementele matricei s reprezinte elementele vectorului X scrise în urm toarea ordine: X(1) X(2) X(5) X(10) ... X(4) X(3) X(6) X(11) ... X(9) X(8) X(7) X(12) ... X(16) X(15) X(14) X(13) ... . . . 4.40. Se d X Vn(R). S se genereze o matrice A p trat de ordinul m, cu m maxim posibil, astfel încât elementele matricei s reprezinte elementele vectorului X scrise în urm toarea ordine: X(1) X(2) X(4) X(7) ... X(3) X(5) X(8) ... X(6) X(9) ... X(10) ... 4.41. Se d X Vn(R). S se genereze o matrice p trat A de ordinul m, cu m maxim posibil, astfel încât elementele matricei s reprezinte elementele vectorului X scrise în urm toarea ordine: X(1) X(2) X(6) X(7) X(15) ... X(3) X(5) X(8) X(14) ... X(4) X(9) X(13) ... X(10) X(12) ... X(11) ... 4.42. Se dau m

i X Vn(R) pentru n=m2. S se construiasc o matrice p trat de ordinul m, dac este posibil,

astfel: - deasupra diagonalei principale elementele matricei sunt elementele irului începând cu x1, scrise în ordine pe linii; - elementele de pe diagonala principal sunt ai,i = xi*i; - elementele de sub diagonala principal se calculeaz astfel:

45

ai,j = max{ xj, ... , xi }. 4.43. Se d X V2n(R). S se construiasc o matrice p tratic de ordinul n astfel: se completeaz diagonala principal de sus în jos cu elemente consecutive din ir începând cu x1; deasupra diagonalei principale se completeaz matricea paralel cu diagonala principal , de sus în jos, cu elemente succesive din ir, începând cu xn+1, iar sub diagonala principal elementul din linia i i coloana j a matricei este egal cu elementul xj+i al irului. 4.44. Se d X V2n(R). S se construiasc o matrice p tratic de ordinul n astfel încât:

a i, j =

min{ x i ,..., x n },

daca i este par

max{ x k |x k < 0,k = 1 , j}, daca i este impar .

194

4.45. Se dau m, n

. S se formeze matricea A Mm,n(R) din elementele irului 1,1,2,4,3,9,27,1,4,16,5,25,125,... scrise în ordine pe linii. (Se va observa c irul este ob inut din irul numerelor naturale prin înlocuirea fiec rui num r par p cu o secven format din numerele 1,p,p2 i a num rului impar i>1 cu o secven format din numerele i,i2,i3) . 4.46. Se dau m, n . S se formeze matricea A Mm,n(R) din elementele irului 1, 2,2, 1,2,3, 4,4,4,4, 1,2,3,4,5, 6,6,6,6,6,6, 1,2, 3,4,5,6,7, 8,8,8,8,8,8,8,8, 1,2,... scrise în ordine pe coloane. (Se va observa c irul este ob inut din irul numerelor naturale prin înlocuirea fiec rui num r par p cu o secven format din p numere toate egale cu p i a num rului impar i cu o secven format din numerele 1,2,...,i). 4.47. Se dau m,n

a ij =

i X Vm*n(R). S se genereze o matrice A Mm,n(R) definit astfel:

( x i + x i+1 +...+ x ij ) / (ij - i + 1) , daca x i > 0 195 max{ x i , x i+1 ,..., x ij } , daca x i ≤ 0

pentru i=1,2,...,m i j=1,2,...,n. 4.48. Se dau m,n

i X Vm*n(R). S se genereze o matrice A Mm,n(R) definit astfel: (i-1)n+ j

a ij

=

x l 196 l=(i-1)n+1

pentru i=1,2,...,m i j=1,2,...,n. 4.49. Se dau 2 numere naturale m i n. S se construiasc matricea AMm,n(R) definit astfel : 0 , dac i +j este num r prim A(i,j) = 1 , dac i +j este num r perfect neprim 2 , în caz contrar, pentru i=1,2,...,m i j=1,2,...,n. 4.50. Fie B o matrice definit astfel: 0 , dac i +j este num r prim B(i,j) = 1 , altfel, pentru i=1,2,...,m i j=1,2,...,n i fie matricea C de acelea i dimensiuni, în care linia i reprezint num rul 2i+1 scris în baza 2. S se determine matricea A = B + C, adunare modulo 2. 4.51. S se construiasc matricea A definit prin : cos(i*j) , dac i*j < m*n/2 A(i,j) = sin(i+j) , în caz contrar,

46

pentru i=1,2,...,m i j=1,2,...,n. 4.52. Se d M(1) M(12) M(2) M(13) M(3) M(14) M(4) M( 5)

a R i fie M(1)=a. S se formeze matricea p trat A de ordinul n de forma M(11) M(10) M(16) M( 9) M(15) M( 8) M( 6) M( 7)

M(k) = I 2M(k -1) + 10 197 pentru k = 2,3,...,n*n, unde I p 198 reprezint r sturnatul num rului p (exemplu: r sturnatul num rului 123 este num rul (în cazul n=4) dac

321) 4.53. Un labirint în care exist numai drumuri (poteci, alei) orizontale i verticale, se reprezint cu ajutorul unei matrice, în care un ir de zerouri reprezint un drum, un ir de 1 un zid. Se d o pozi ie ini ial în interiorul labirintului. S se g seasc cel mai scurt drum pe care se poate ie i din labirint. cuvinte:

4.54. Se d o matrice cu elemente cuvinte de maximum 30 de litere sau spa ii. S se afle frecven a vocalelor în - pe linii; - pe coloane; - în matrice. 4.55. Se dau vectorii A Vm(R) i B Vn(R). S se formeze matricea CMm,n(R) dac i

a(k) c(i, j) =

k=1 n

199

b(k) k= j

În cazul în care numitorul este nul, c(i,j)=-1. 4.56. Se dau vectorii A Vm(R) i B Vn(R). S se formeze matricea CMm,n(R) dac

cij =

ai * b j 200 max{ a1 ,...,a m ,b1 ,...,bn }

În cazul în care numitorul este nul se ia cij = min{ai, bj}. 4.57. Se dau vectorii A Vm(R) i B Vn(R). S se formeze matricea CMm,n(R) dac cij = max{ a i , bi , a j + b j }, i = 1,2,...,m, j = 1,2,..n 201. 4.58. Se dau vectorii A Vm(R) i B Vn(R). S se formeze matricea CMm,n(R) dac i

cij = k=1

ak•

j

b p 202 p=1

4.59. Se dau dou matrice A,B Mm,n(R). S se determine matricea C Mm,n(R) unde

cij = max{ a ij ,bij } , i = 1,m j = 1,n 203. 4.60. Se dau dou matrice A,B MPn(R). S se determine matricea C MPn(R) definit prin: cij = min{ a ik + bkj | k = 1,2,...,n}. 204

47

4.61. Se dau dou matrice A,B Mm,n(R). S se determine matricea CMm,n(B2) unde

0 , daca a ij ≠ bij 205 1 , daca a ij = bij .

cij =

4.62. Se dau dou matrice A,B Mm,n(R). S se g seasc mul imea indicilor i pentru care: n

n

a ij < j=1

bij . 206 j=1

4.63. Se cere s se genereze matricea A, p tratic de ordinul n, definit astfel: C(j,i), dac i<j A(i,j) = C(i,j), în caz contrar. Prin C(n,k) s-a notat "combin ri de n luate câte k". S se verifice dac matricea este simetric . 4.64. Se dau n obiecte i o matrice D = d(i,j) simetric , d(i,j) > 0 reprezentând distan a de la obiectul i la obiectul j (m sur a gradului de disimilaritate dintre obiectele i i j). S se determine toate mul imile nevide de perechi de obiecte pentru care k-1 < d(i,j) k ( k , 0 k max{d(i,j) i,j=1,...,n}). 4.65. S se tip reasc toate matricele p trate de ordinul 4 care au un singur 1 pe fiecare linie i pe fiecare coloan iar în rest 0. 4.66. Fie A,B,C MPn(R) trei matrice diagonale, iar D MP2n(R) o matrice cu structura:

D =

A B B C

207

X i P fiind 2 vectori coloan de dimensiune 2n cu componente reale, s se întocmeasc un algoritm i s se scrie un program pentru rezolvarea sistemului D X = P. 4.68. Se dau numerele întregi x1 , x 2 ,..., x n ∈ [0, 2 n ) . 208 S se tip reasc matricea p trat de ordinul n care are proprietatea c linia a i-a a acestei matrice reprezint num rul xi în baza doi. 4.69. Se d A Mm,n(B2). S se determine numerele a c ror reprezent ri în baza 2 sunt date de coloanele matricei. 4.70. Se d X Vn(R). S se formeze matricea A MPn(R) cu elementele:

max{ x k |k ≥ j si k ≤ i} , a ij =

min{ x 2k | j ≤ k ≤ i},

daca j ≤ i si ∃ x l > 0, l = j, j + 1,...,i

daca j ≤ i si ∃ x l ≤ 0, l = j, j + 1,...,i 209 ( x i + x i+1 +...+ x j ) / (j - i + 1), daca j > i .

48

CAPITOLUL 5

SUBALGORITMI 5.1. REUNIUNEA UNOR MUL IMI Se consider , trei mul imi A, B, C. Se cere un program care afi eaz : - elementele mul imii A în ordine cresc toare; - elementele mul imii B în ordine cresc toare; - elementele mul imii C în ordine cresc toare; - elementele mul imii A B în ordine cresc toare; - elementele mul imii B C în ordine cresc toare; - elementele mul imii C A în ordine cresc toare. Rezolvare. Pentru realizarea programului este necesar construirea a patru proceduri specificate în continuare: - o procedur pentru citirea unei mul imi: CIT(n,A); REZULTATE n,A {primesc valori prin citire} - o procedur pentru ordonarea unui ir: ORDON(r,X); DATE {de intrare} r, {num rul componentelor vectorului X} X; {vector cu n componente} REZULTATE X {la ie irea din subalgoritm vom avea: } { x1 < x2 < ... < xn } - o procedur pentru calculul reuniunii a dou mul imi: DATE {de intrare} n, m, A, B; REZULTATE nm, AUB

REUN(n,m,A,B,nm,AUB); {num rul elementelor mul imii A} {num rul elementelor mul imii B} {mul imea {a1, a2, ... , an } } {mul imea {b1, b2, ... , bm } } {num rul elementelor reuniunii } {AUB = A B }

- o procedur pentru tip rirea unei mul imi: TIPAR(n,A,ch); DATE {de intrare} n, {num rul elementelor mul imii A} A, {mul imea {a1, a2, ... , an } } ch; {caracter considerat numele mul imii} REZULTATE afi area elementelor mul imii - o procedur pentru ordonarea i apoi tip rirea unui ir: TIPORDON(r,X,ch); DATE {de intrare} r, {num rul componentelor vectorului X} X, { vector cu n componente arbitrare } ch; {caracter considerat numele mul imii} REZULTATE *ordonarea componentelor vectorului X i * afi area elementelor ordonate cresc tor

49

- o procedur pentru calculul reuniunii a dou mul imi, cu ordonarea TIPREUN(n,m,A,B,nm,AUB). aceea i semnifica ie ca la procedura REUN, dar, în plus, se tip re te AUB.

i tip rirea rezultatului:

Algoritmul pentru rezolvarea problemei, descris în limbajul PSEUDOCOD, este urm torul: Algoritmul Exemplu1 este: Cheam CIT(n,A); Cheam CIT(m,B); Cheam CIT(p,C); Cheam TIPORDON(n,A); Cheam TIPORDON(m,B); Cheam TIPORDON(p,C); Cheam TIPREUN(n,A,m,B,n1,AB); Cheam TIPREUN(m,B,p,C,m1,BC); Cheam TIPREUN(p,C,n,A,p1,CA); Sf-algoritm.

{ A e vectorul care con ine în componentele } { sale cele n elemente ale mul imii A} { Cite te mul imea B} { Cite te mul imea C}

{ Tip re te pe AB := A U B}

Subalgoritmii apela i mai sus sunt descri i în continuare: {Ordoneaz componentele lui X} {examineaz toate componentele} {ipoteza c sunt ordonate}

Subalgoritmul ORDON(r,X) este: Repet Fie sch:= 0; Pentru i:= 1, r-1 execut Dac x i > x i+1 210 atunci Fie xx:= x i ; 211 Fie x i := x i+1 ; 212 Fie x i+1 := xx; 213 Fie sch:=1;

{re ine c n-au fost ordonate}

sf-dac sf-pentru pân când sch=0 sf-repet sf-ORDON

Subalgoritmul REUN(n,A,m,B,n1,AUB) este: Pentru i:=1, n execut AUBi := Ai ; 214 sf-pentru Fie n1:=n; Pentru j=1, m execut Fie i:=1; Câttimp ( B j ≠ Ai ) si (i ≤ n) 215 execut i:=i+1 sf-câttimp

{AUB := A

B}

Dac i>n atunci Fie n1:=n1+1; 216 sf-dac sf-pentru sf-REUN Subalgoritmul TIPORDON(r,X,ch); Cheam ORDON(p,X); Cheam TIPAR(r,X,ch); sf-REUN Subalgoritmul TIPREUN(n,A,m,B,n1,AUB,ch) este:

50

{Ordoneaz i apoi tip re te} { cele n componente ale vectorului X} {ch=numele mul imii reprezentat în vectorul X}

{ AUB:= A

B}

{Ordoneaz

Cheam REUN(m,B,p,C,m1,BC); Cheam TIPORDON(r,X,ch); sf-TIPREUN

i tip re te pe AUB}

Traducerea algoritmului în limbajul PASCAL este urm toarea: Program exemplu1; Type sir = array [1..30] of real; s3 = string[3]; Var n, m, p, n1, m1, p1 : integer; a, b, c, ab, bc, ca : sir;

{ Programul 5.1 } {opera ii cu mul imi reprezentate ca vectori}

{a,b,c con in elementele a trei mul imi de numere }

Procedure cit(var n: integer; var a: sir; ch: s3); var i: integer; begin write('nr. elementelor mul imii ', ch, ' este:'); readln(n); for i := 1 to n do begin write(ch, '[', i, ']='); readln(a[i]) end; end; Procedure tipar(n: integer; a: sir; ch: s3); var i: integer; begin writeln('elementele mul imii ', ch, ' sunt:'); for i := 1 to n do writeln(ch, '[', i, ']=', a[i]); end; Procedure ordon(r: integer; var x: sir); var xx: real; i, sch: integer; begin repeat sch := 0; for i := 1 to r-1 do if x[i] > x[i+1] then begin xx := x[i]; x[i] := x[i + 1]; x[i + 1] := xx; sch := 1 end; until sch = 0; end;

{Cite te n si } { mul imea a cu n elemente} {ch=numele mul imii citite}

{Tip re te mul imea a cu} {numele ch având n elemente}

{Ordoneaz cresc tor elementele} {vectorului X cu r componente}

Procedure tipordon(r: integer; var x: sir; nume:string);

51

var xx: real; i, sch: integer; begin ordon(r, x); tipar(r, x, nume); end; Procedure reun(n, m: integer; A,B: sir; var n1:integer; var AUB:sir); var i, j: integer; begin n1 := n ; for i := 1 to n do AUB[i] := A[i]; for j := 1 to m do begin i := 1; while (B[j]<>A[i]) and (i<=n) do i := i+1; if i > n then begin n1 := n1+1; AUB[n1] := B[j]; end; end; end; Procedure tipreun(n, m: integer; A,B: sir; var n1: integer; var AUB:sir; nume:string); var xx: real; i, sch: integer; begin reun(n, m, A, B, n1, AUB, nume); ordon(n1, AUB); tipar(n1, AUB, nume); end; Begin cit(n, a, 'A'); cit(m, b, 'B'); cit(p, c, 'C'); tipordon(n, a,'A'); tipordon(m, b,'B'); tipordon(p, c,'C'); tipreun(n, m, a, b, n1, ab,'AUB'); tipreun(m, p, b, c, m1, bc,'BUC'); tipreun(p, n, c, a, p1, ca,'AUC'); end.

{Calculeaza A

B}

{Calculeaz reuniunea,} {ordoneaz elementele i} {tip re te rezultatul}

{programul principal}

5.2. NUMERE PRIME S se scrie un program care determin primele n numere prime (n>3), folosind o func ie care stabile te dac un num r este prim sau nu. Specificarea problemei: DATE n; REZULTATE (pj,j=1,n);

52

{nN, n>3} {p1,p2,...,pn sunt primele n numere prime}

Pentru rezolvarea problemei vom utiliza o func ie de tip boolean "PRIM(n)" care întoarce "true" dac num rul natural n este prim i "false" în caz contrar. Algoritmul func iei are la baz ideea de a c uta divizori ai lui n între primele n/2 numere naturale. Algoritmul poate fi util în multe probleme, motiv pentru care l vom descrie ca subalgoritm ce poate fi apelat oricând este nevoie de el. Vectorul P va re ine cele n numere prime. În variabila i vom avea urm torul candidat, num r natural care uneori este prim. Primele dou numere prime fiind 2 i 3, la început vom ini ializa pe i cu 5. Prin k s-a notat num rul numerelor prime g site. Subalgoritmul NRPRIME este urm torul: Subalgoritmul NRPRIME(n,P) este: Fie i:=5; p1:=2; p2:=3; k:=2; Repet Dac prim(i) atunci Fie k:=k+1; pk:=i; sf-dac ; Fie i:=i+2; pân când k=n sf-repet sf-NRPRIME

{Se caut n numere prime}

Func ia PRIM(n) este: prim:=true; Pentru i:=2, n/2 execut Dac n mod i = 0 atunci prim:=false sf-dac sf-pentru Sf-PRIM Programul PASCAL cerut este urm torul: Program exemplu2; Type vector = array[1..999] of integer; Var n, i : integer; P : vector; function prim(n: integer): boolean; var i: integer; begin prim := true; for i := 2 to n div 2 do if n mod i = 0 then prim := false; end; Procedure NRPRIME(n:integer; Var P:vector); Var k:integer; begin i := 5; k := 2; P[1]:=2; p[2]:=3; repeat if prim(i) then begin k:= k+1; P[k]:=i end; i:= i+2; until k > n;

{Programul 5.2. G se te primele n numere prime } { num rul numerelor g site } { variabila contor in P } { Vectorul numerelor prime } {Dac n e prim atunci TRUE}

{ In vectorul P se ob in } { primele n numere prime }

53

end; begin write('cate numere prime va intereseaz ?'); readln(n); NRPRIME(n,P); writeln('primele ', k, ' numere prime sunt urm toarele:'); For i:=1 to n do begin write(P[i]:4); If i mod 5 = 0 then writeln end end.

{programul principal}

5.3. PROBLEME PROPUSE 5.1. S se calculeze valoarea într-un punct a unui polinom i a tuturor derivatelor sale, folosind pentru aceasta - o procedur de derivare a unui polinom; - o func ie care întoarce ca rezultat valoarea polinomului într-un punct x dat. 5.2. Se dau polinoamele P, Q, R : P = pmXm + ... + p1X + p0, Q = qnXn + ... + q1X + q0, R = rkXk + ... + r1X + r0. S se tip reasc produsele P • Q, Q • R, R • P 217 în ordinea indicat . 5.3. Folosind un subalgoritm pentru efectuarea produsului P = Q polinoamele (x + 1)n pentru n = 1,2,...,12.

• R 218 a dou polinoame Q i R, tip ri i

5.4. Se cere programul care, folosind cel mult trei iruri, determin rezultatul: a) reuniunii a n mul imi; b) intersec iei a n mul imi. 5.5. Se cere programul pentru calculul: a) produsului a n matrice p tratice; b) puterii a n-a a unei matrici p tratice. 5.6. Se cere programul de calcul al produsului a n polinoame. 5.7. Se cere un program care calculeaz , cu ajutorul unui subalgoritm, media aritmetic a elementelor maxime corespunz toare fiec rei linii a unei matrici, iar apoi afi eaz aceast valoare pentru trei matrice distincte A, B, C. 5.8. Fie f1, f2, ..., fn n polinoame. Se cere un program care calculeaz valoarea sumei celor n polinoame într-un punct dat folosind: - o procedur de calcul a sumei a dou polinoame; - o func ie de calcul a valorii unui polinom într-un punct folosind schema lui Horner. 5.9. Fie f i g dou polinoame. Se cere s se calculeze valoarea func iilor fg i gf într-un punct dat, folosind o func ie de calcul a valorii unui polinom într-un punct. 5.10. Folosind dezvoltarea în serie:

54

1 x3 1 • 3 x5 1 • 3 • 5 x7 arcsin x = x + • + • + • + ... 219 2 3 2•4 5 2•4•6 7 s se defineasc o func ie PASCAL care calculeaz arcsin x cu precizia

ε = 10-6 . 220 S

se tip reasc apoi valorile:

1 v i = arcsin , i = 2,3,...,m 221. i

5.11. Fie irul x1,x2,...,xn. Se cere un program care determin i tip re te cea mai lung secven din irul dat care are o anumit proprietate P folosind: - o func ie care descrie proprietatea P i întoarce lungimea secven ei care are proprietatea P i începe cu x k 222 - o procedur care determin secven a cerut . (De exemplu, proprietatea P poate cere ca doi termeni vecini s aib semne diferite). 5.12. Folosind un subalgoritm care rezolv ecua ia f(x) = 0 (care are o solu ie unic în intervalul [a,b]) prin metoda înjum t irii, tip ri i tabelul de mai jos:

Observa ie. Radicalul

r =

n

i

3

2

...

...

3

...

...

. . .

. . .

. . .

10

...

...

i 223

5

i 224

m 225 se calculeaz prin rezolvarea ecua iei t n = m 226.

5.13. Se dau m,n,p N i trei iruri X: x1,x2,...,xn; Y: y1,y2,...,ym; Z: z1,z2,...,zp de numere întregi. Pentru fiecare ir se cere s se calculeze i s se afi eze frecven ele de apari ie ale cifrelor 0,1, ..., 9 în scrierea numerelor din irurile date. 5.14. Fie o grup de studen i care au sus inut 5 examene într-o sesiune. S se scrie programul care afi eaz : - primii 6 studen i în ordinea mediei generale ob inute; - studen ii care nu au promovat cel pu in trei examene. 5.15. S se scrie un program care genereaz un ir aleator de m numere întregi i care stabile te frecven a de apari ie în acest ir a: - numerelor prime; - numerelor divizibile cu 13. Observa ie. Pentru generarea unui num r aleator se vor folosi func ia i respectiv procedura predefinit RANDOM i RANDOMIZE. 5.16. Fie nN i x1, x2,..., xn un ir de numere naturale date. S se scrie un program care g se te: a) media aritmetic a acestor numere; b) maximul din irul y1,y2,...,yn unde yi se ob ine în felul urm tor: y1 = x1 , y i = ( x i div x i-1 ) * ( x i + x i-1 ) , i = 1,2,...,n. 227. c) S se scrie o func ie boolean care stabile te dac cele dou iruri au i alte elemente comune în afara primului. 5.15. Dou numere prime p, q se numesc gemeni dac p = q + 2. S se determine primele n perechi de gemeni.

55

5.18. Trei numere întregi a, b, c, a < b < c se numesc pitagorice dac ( a1 ,b1 ,c1 ) 229 i ( a 2 , b2 , c2 ) 230 sunt considerate a fi asemenea dac

c2 = a 2 + b2 228, iar dou triplete

a1 b1 c1 = = 231. a2 b2 c2 Se d nN i mul imea de numere întregi X = {xii=1,2,...,n}. Se cere s se afi eze mul imea tripletelor pitagorice din mul imea dat i clasele determinate de rela ia de asem nare pe aceast mul ime. 5.19. Fie

A1 , A2 , ..., An 232 n mul imi de numere. S se scrie programul care determin mul imea: A = (...( A1 ∆ A2 ) ∆ A3 ) ∆ ... ∆ An-1 ) ∆ An 233,

folosind pentru aceasta o procedur de calcul a mul imii:

A ∆ B = (A - B) ∪ (B - A) 234. Observa ie. Pentru rezolvarea problemei se vor utiliza cel mult trei iruri. 5.20. Fie I o mul ime de subintervale ale intervalului [a,b]. a) S se formeze o diviziune X a intervalului [a,b]

a = x 0 < x1 < x 2 < ... < x n = b 235

care are ca puncte capetele subintervalelor din I; b) S se calculeze valorile v i = f( x i ) 236, unde

f( x i ) 237 este num rul de subintervale din I în care se afl

x i 238. 5.21. tiind c

irul X:

4,2,6,2,3,8,2,4,9,3,10,... este ob inut din irul numerelor naturale prin eliminarea numerelor prime i scrierea dup fiecare num r compus a divizorilor s i proprii, s se genereze urm toarea matricea de ordinul n:

A =

S se tip reasc în final

x1

x n+1

.

. .

.

.

.

x 2n

x2

x n+2

. .

.

.

.

x 3 x n+3 .

.

.

.

.

.

.

. x 2n+1 .

.

.

. .

.

.

.

. . x 3n-3

.

.

.

. .

239.

x n-1 x 2n-1

. x 3n-2

xn

A, A2 , ..., An . 240

5.22. Se dau nN i numerele x1 , x 2 , ..., x n 241. Se cere programul care genereaz matricea de dimensiune mxk 242 care are pe liniile sale în ordine elemente din irul: x1 , x 2 , ..., x n , x1 , x 2 , ..., x n , ... . 243 5.23. tiind c

irul

{ x n } 244:

1,2,3,2,5,2,3,7,2,4,3,2,5,11,... este format din irul numerelor naturale în care fiecare num r compus este înlocuit prin divizorii s i proprii, s se genereze matricea:

56

x1 A =

x m+1 .

x2 . . .

xm

x m+2 . . . x 2m . . . .

.

245.

x(m-1)•m+1 x(m-1)• m+2 . . . x m2 5.24. S se scrie un program care rezolv ecua ia matriceal : A • X + B = C 246, unde A,B,C ∈247 M 3x3 248 i X este vectorul necunoscut . 5.25. S se scrie un program pentru rezolvarea unui sistem liniar de patru ecua ii cu patru necunoscute folosind metoda lui Kramer. Programul va stabili mai întâi dac sistemul este compatibil i unic determinat. 5.26. Se dau nN i vectorii X, Y cu n componente numere reale. S se calculeze valorile:

v i = f( x i ) =

g( x i ), daca x i < 0, l( x i ), daca x i = 0, 249 h( y i ), daca x i > 0,

pentru i=1,2,...,n, unde:

g( x i ) = max{ x1 , x 2 , ..., x i},

h( y i ) = min{ y i , ..., y n} ,

250

pentru i=1,2,...,n, iar l( x i ) 251 este media aritmetic a numerelor pozitive din irul { x n 252} cu valoare mai mic decât

| y i | 253. 5.27. Se dau m,nN i o matrice Amxn ( n ≥ 10) 254 ale c rei elemente sunt cifre de la 0 la 9 i în care fiecare linie a matricei reprezint un num r în baza zece. S se scrie un program care face o permutare a liniilor matricei astfel încât în final cele m numere reprezentate pe liniile matricei s fie în ordine cresc toare. 5.28. S se scrie un program care calculeaz sumele: n-1

a)

3 C1n - 7 C2n + 11C3n - ... + (-1 ) (4n - 1)C nn ; 255

b)

3 3 3 ( C0n ) ( C1n ) ( C nn ) + + ... + 256. 0! 1! n!

5.29. S se scrie un program pentru calculul sumei:

S = unde

{

an

1 1 1 + + ... + , 257 a1 • a 2 •...• a k a 2 • a 3 •...• a k+1 a n-k+1 •...• a n

} 258 e o progresie aritmetic

pentru care ra ia i primul termen se cer utilizatorului.

57

5.30. Dac numerele a1 , a 2 , ..., a n+1 259 sunt primii n+1 termenii ai unei progresii geometrice, s se calculeze, printr-un program, sumele: a)

Sn =

b) S n ′ =

1 + a - a1p p 2

1 a

p 3

a1 + a 2 - a1

-a

p 2

+ ... +

a

p n-1

1 260 - a np

a2 + ... + a3 - a2

an 261. a n+1 - a n

Observa ie. Ra ia i primul termen al progresiei vor fi furnizate programului de c tre utilizator. 5.31. Se dau nN i numerele reale a1 < a 2 < ... < a n 262. S se scrie programul care tip re te permutarea

σ ∈ Sn 263 pentru care suma

n

2

( a i - aσ (i) ) 264

Sn = i=1

este maxim , respectiv minim . 5.32. Fie f(X) = a 0 • X n + a1 • X n-1 +...+ a n-1 • X + a n • I m , 265 unde

a i ∈_ , i = 0,n, 266 iar X,Im

M mxm 267 i fie matricele A,B ∈ M mxm 268. S se scrie un program care calculeaz f(A) + f(B) i f(A+B). 5.33. Se dau R i nN. S se scrie un program care calculeaz suma: n

cos kα

sin kα

k=1

cos2 kα

sin 2 kα

269

x1 , x 2 270 sunt r d cinile reale ale ecua iei de gradul doi (cu coeficien i reali): a1 • x + a 2 • x + a 3 = 0 271, s se scrie programul care calculeaz suma: 5.34. Dac

2

n

x1k

x 2k 2

x13k

k=1

x 3k 2

x12k

x 2k

S =

. 272

În cazul în care ecua ia de gradul doi nu are r d cini reale se va da un mesaj de eroare corespunz tor. prin:

5.35. Se dau m,nN. S se scrie programul care genereaz

58

i tip re te matricea A cu m linii i n coloane definit

daca i + j < min(m,n)

P(i + j), a ij =

2

R( i , j ), daca min(m,n) ≤ i + j ≤ max(m,n) 273 2

daca max(m,n) < i + j

Q(i + j),

unde P(k) este num rul prim cel mai apropiat de k, Q(k) este num rul p tratelor perfecte mai mici decât k, iar R(a,b) este cmmdc(a,b). 5.36. S

primele m numere naturale n ∈ Ν 274 cu proprietatea

se scrie un program care determin

n

cmmdc ( n, 2 - 1 ) > 1 275. proprii.

5.37. S se scrie un program care determin cel mai mic num r natural n ∈ Ν care are exact m divizori primi 5.38. Fie n ∈ Ν 276 S se scrie un program care calculeaz suma: *

m • ϕ (d) 277 d

S = d|m

unde însumarea se face dup divizorii naturali d ai lui m (inclusiv 1 i m), iar

ϕ (n) =

279 num rul numerelor naturale mai mici decât n i prime cu n, ∀ n

ϕ 278

este indicatorul lui Euler,

∈ Ν 280 (cu conven ia ϕ (1) = 1 281 *

). n

k k • C2n 282 unde nN, n1. S se scrie un program care

5.39. Fie m = k=0

calculeaz valoarea pe un punct x dat a func iei:

f(x) =

1 • m

n

2

(k - x ) • c2k 2n . 283

k=0

5.40. Fie ( p1 , p2 , p3 ) ( p1 < p 2 < p3 ) 284 un triplet format din numere prime aflate la acea i distan

p3 - p2 = p2 - p1 = d > 0, 285. S se determine primele n triplete pentru care d este n ≤ 10 multiplu de 2 ( 286). unul fa de altul, adic

5.41. Se dau m,nN i o matrice AMm,n(N) care are ca elemente numere naturale. S se scrie un program care genereaz vectorul V ce con ine drept componente toate elementele matricei care sunt prime între ele dou câte dou . 5.42. S se scrie un program care determin primele n numere prime pentru care suma cifrelor este un num r divizibil cu 11. 5.43. Se d o matrice A având ca elemente caractere alfabetice. S se scrie programul care stabile te dac un cuvânt dat apare pe vreuna din liniile sau coloanele matricei, iar în caz afirmativ tip re te pozi iile din matrice unde începe i respectiv se termin cuvântul c utat. 5.44. Se dau nN i func ia

59

n

f(n) =

C kn ( k 2 + 1), n par

k=0 n k=1

1 , k!

287

n impar

a) Se cere programul care genereaz primele m elemente ale irului xi = f(g(i)), i=1,2,...,n, unde g(n) reprezint suma cifrelor num rului n din scrierea sa în baza zece. b) S se afi eze frecven a de apari ie a fiec rei valori din irul xi.

60

61

CAPITOLUL 6

PROBLEME REZOLVATE CU MATRICE 6.1. RELA II ÎNTRE PERSOANE Se dau n persoane i matricea AMPn(B2) unde

a ij =

1, daca persoanele i si j se cunosc 0, i n caz contrar

288

S se g seasc persoanele care nu au nici o cuno tin . Rezolvare. Specificarea problemei este: DATE n, A; REZULTATE k,P;

{ n = num rul persoanelor } { A = matrice p trat de ordinul n } {k = num rul persoanelor care nu au nici o} {cuno tin . P = un vector cu k componente} {P re ine cele k persoane f r cuno tin e }

Pentru rezolvarea problemei, în matricea dat se caut liniile care au numai zerouri. În aceast c utare este nevoie de dou variabile auxiliare i i j, indici în matricea A. Algoritmul pentru rezolvarea acestei probleme este dat în continuare. Algoritmul PERSOANE este: Date n, A; Fie k:=0; Pentru i := 1,n execut Fie j:=1; Câttimp (jn) i (aij=0) execut j:=j+1 sf-câttimp Dac j>n atunci k:=k+1; pk:=i sf-dac sf-pentru Rezultate k,P; sf-algoritm.

{n = num rul persoanelor } {A = matrice p trat de ordinul n }

La scrierea programului Pascal este necesar s verific m corectitudinea datelor, respectiv faptul c dac persoanele i i j se cunosc vom avea aij=1, dar atunci i aji=1, deci matricea A trebuie s fie simetric . Aici s-a optat pentru o alt solu ie: nu se cite te matricea A ci perechile de persoane care se cunosc, matricea A fiind construit în program. Program CUNOSTINTE; Var n, k, i,j : byte; P : array[1..20] of byte;

{Programul 6.1.} { Rela ia de cuno tin e intre persoane} { n = num rul persoanelor } {k = nr. pers. care nu au nici o cuno tin a} { P = vector cu k componente ce} {re ine cele k persoane f r cuno tin e}

63

a : array[1..20,1..20] of byte;

{ A = matrice de ordinul n }

BEGIN writeln ('Programul g se te persoanele care intr-un grup de n'); writeln ('persoane nu au nici o cuno tin a.'); writeln; repeat write ('Da i num rul persoanelor:'); readln (n) until n in [1..20];

{ CITIRE NR. PERSOANE }

{ INITIALIZARE MATRICE } for i := 1 to n do for j := 1 to n do a[i,j] := 0; writeln ('Da i perechile de persoane care se cunosc intre ele.'); writeln ('Persoanele se codifica prin numerele 1,2,...,n.'); writeln ('Introduce i cate doua numere pe o linie (separate', 'prin spa iu)'); writeln ('Pentru terminarea introducerii tasta i: 0 0 '); { CITIREA DATELOR, CU ELIMINAREA CELOR ERONATE } write ('* '); readln (i,j); while (i>0) and (j>0) do begin if (i<=n) and (j<=n) then begin a[i,j] :=1; a[j,i] :=1 end {if}; write ('* '); readln (i,j); end{while}; { CAUTARE PERSOANE CARE NU AU CUNOSTINTE } k:=0; for i := 1 to n do begin j := 1; while (j<=n) and (a[i,j]=0) do j := j+1; if j > n then begin k:=k+1; P[k]:=i end{if}; end{for}; { TIPARIREA REZULTATELOR } writeln; write ('Persoanele care nu au cuno tin e: '); if k>0 then for i:=1 to k do write(p[i]:5) else writeln (' nu exista '); END. 6.2. PATRATE MAGICE S se realizeze un p trat magic de ordin impar. Rezolvare. Prin p trat magic se în elege o matrice p trat de ordin n cu elementele {1, 2, ..., n2} a ezate astfel încât suma elementelor de pe fiecare linie, coloan sau diagonal este aceea i. Cu aceast precizare specifica ia problemei este urm toarea: DATE n; REZULTATE A;

64

{ nN, n>1, reprezint ordinul matricei } {A=matrice de ordinul n, care reprezint } {p tratul magic; deci suma elementelor pe } { fiecare linie, coloan sau diagonal este aceea i }

În general algoritmul de construire a unui p trat magic este complicat. Dac n = 2k+1 atunci exist mai mul i algoritmi care ob in p tratul magic. Vom folosi urm toarea metod : - se începe cu a1k:= 1. - Dac aij = k atunci ai-1,j+1 := k+1, dac locul este liber, altfel ai+1,j := k+1. - irul indicilor se consider circular, adic dup n urmeaz 1, înaintea lui 1 este n. Excep ie de la regul : dac a1n = k atunci a2n:= k+1. Exemplu: 17 23 4 10 11

24 1 8 15 5 7 14 16 6 13 20 22 12 19 21 3 18 25 2 9

Pentru trecerea la noua pozi ie se recomand s se foloseasc formulele: m1:= (i+n-2) modulo n + 1 m2:= j modulo n + 1. Algoritmul P_MAGIC este:

DATE n; Pentru i:=1,n execut Pentru j:=1,n execut Fie a[i,j] := 0 sf-pentru sf-pentru Fie i:=1; j:=n div 2 +1; a[i,j]:=1; Pentru k := 2,n*n execut m1 := (i+n-2) mod n + 1; m2 := j mod n + 1; Dac a[m1,m2] 0 atunci Dac (m1=n) i (m2=1) atunci m1 := 2; m2 := n altfel m1 := i+1; m2 := j sf-dac Fie a[m1,m2]:=k; Fie i:=m1; j:= m2; sf-dac sf-pentru REZULTATE A; sf-algoritm

{ Se calculeaz un p trat magic } { Acesta este o matrice p trat de ordinul n } { care are suma elementelor pe fiecare linie, } {coloan sau diagonal aceea i } { nN, n>1, reprezint ordinul matricei } { ini ializare matrice } { fixare locul de pornire} { calculul pozi iei urm toare}

{ atribuire noua valoare } { i noua pozi ie }

Programul Pascal echivalent este urm torul: Program magic;

Uses Crt;

{ Programul 6.1.} { Se calculeaz un p trat magic. } { Acesta este o matrice p trata de ordinul n } { care are suma elementelor pe fiecare } { linie, coloan sau diagonal aceea i }

65

Var n, m1, m2, i, j, k : integer; a : array[1..19,1..19] of integer; Begin Writeln('Se construie te un p trat magic cu n linii'); Repeat write ('n='); readln (n) until (n in [1..19]) and Odd(n); for i := 1 to n do for j := 1 to n do a[i,j] := 0; i:= 1; j:= n div 2 + 1; a[i,j]:=1; for k := 2 to n*n do begin m1 := (i+n-2) mod n + 1; m2 := j mod n + 1; if a[m1,m2] <> 0 then if (m1=n) and (m2=1) then begin m1 := 2; m2 := n end else begin m1:=i+1; m2 := j end; a[m1,m2] := k; i := m1; j := m2; end;

{ nN, n>1, reprezint ordinul matricei } { variabile curente pentru noua pozi ie } { dau pozi ia curenta in p trat } { valoarea ce se scrie in p trat } { P tratul magic }

{ Cite te n } { ini ializare matrice } { fixare locul de pornire}

{ calculul pozi iei urm toare }

ClrScr; for i := 1 to n do begin writeln; for j := 1 to n do write (a[i,j]:4); end; writeln; writeln ('Suma magica = ', n*(n*n+1) div 2); readln; END.

{ atribuire noua valoare } { Tip rirea rezultatului } { tip re te linia i }

6.3. PROBLEME PROPUSE 6.1. Se dau n localit i. Într-o matrice A sunt marcate drumurile directe între localit i astfel: a ij = 1, 289 dac exist drum direct între localit ile i i j;

a ij = 0, 290 dac nu exist drum între i i j, pentru i,j=1,2,...,n. 6.1.1. S se determine dac din localitatea x se poate ajunge în localitatea y. 6.1.2. S se determine localit ile în care se poate ajunge din localitatea x. 6.1.3. S se determine toate drumurile de la k la l pentru k i l date.

66

6.2. Se dau n persoane i matricea A cu elementele a ij = 1, 291 dac persoanele i i j se cunosc;

a ij = 0, 292 în caz contrar, pentru i,j=1,2,...,n. 6.2.1. S se determine persoanele care le cunosc pe toate celelalte. 6.2.2. S se determine dac cele n persoane pot fi împ r ite în dou (sau mai multe) grupe astfel încât nici o persoan dintr-o grup s nu cunoasc pe nimeni din celelalte grupe. 6.2.3. S se determine persoana care are cele mai multe cuno tin e. 6.2.4. Dac n6, s se verifice dac exist trei persoane care se cunosc între ele, sau trei care nu se cunosc între ele. 6.3. Se dau n rela ii de rudenie prin matricea A=(aij), i=1,2, ...n, j=1,2, unde a i2 293 este copilul lui a i1 294 pentru fiecare i=1,2,..., n. 6.3.1. S se g seasc : copiii lui k, p rin ii lui k, str mo ii lui k, pentru k dat. 6.3.2. S se g seasc : persoanele care nu au fra i, persoanele care au numai fra i vitregi. 6.3.3. S se g seasc verii primari i secundari ai unei persoane date. 6.3.4. S se g seasc toate familiile (grupele formate din persoanele care sunt rude între ele). 6.4. Se dau n localit i i matricea A cu elementele aij, i,j=1,...,n, unde aij este egal cu costul construirii drumului dintre localit ile i i j, dac se poate construi un drum, respectiv 0 dac nu se poate construi un drum. S se g seasc o re ea de drumuri care leag toate localit ile i este de cost minim. 6.5. Se dau nN, M = {a1,a2,...,an} i * : M x M --> M o opera ie peste mul imea M. Aceast opera ie poate fi identificat cu o opera ie definit pe M' = {1,2,...,n} i reprezentat printr-o matrice O cu elementul oij = k dac i numai dac ai*aj = ak (deci i*'j=k). Deci opera ia *, definit peste o mul ime arbitrar M, poate fi studiat prin intermediul opera iei *' definit pe mul imea M' i reprezentat în calculator prin matricea O. 6.5.1. S se verifice dac : a) opera ia * este comutativ ; b) exist element neutru (stânga i dreapta). 6.5.2. S se rezolve ecua iile: a*X = b i X*a = b. 6.5.3. Dându-se o submul ime de indici H = {i1, i2, ..., im} dac H este parte stabil în raport cu opera ia .

M' i o opera ie

dat prin matricea O, s se verifice

6.5.4. S se verifice dac opera ia dat este asociativ . element. element.

6.5.5. S se verifice dac opera ia admite element neutru la dreapta i în caz afirmativ s se precizeze acest 6.5.6. S se verifice dac opera ia admite un element neutru la stânga i în caz afirmativ s se precizeze acest 6.5.7. S se verifice dac opera ia admite un element neutru.

67

6.5.8. Se tie c opera ia are ca element neutru pe k. Pentru un jM, s se verifice dac acest element are element simetric la dreapta fa de opera ia dat . 6.5.9. Fie k elementul neutru al opera iei. Pentru un jM, s se verifice dac acest element are element simetric la stânga fa de opera ia dat . 6.5.10. Fie k elementul neutru al opera iei. S se determine un vector s, ale c rui componente sunt s1,s2,...,sn, unde si este 0 dac i nu are element simetric i este j dac j este simetricul lui i. 6.5.11. S se verifice dac structura algebric (M ,*) este un grup. 6.6. Se d o rela ie R printr-o matrice cu elementele a ij = 1, 295 dac i este în rela ie cu j (deci iRj),

a ij = 0, 296 dac i nu este în rela ie cu j (deci i Rj), pentru i,j=1,2,...,n. 6.6.1. S se verifice dac rela ia R este reflexiv . 6.6.2. S se verifice dac rela ia R este simetric . 6.6.3. S se verifice dac rela ia R este antisimetric . 6.6.4. S se verifice dac rela ia R este tranzitiv . 6.6.5. S se determine rela ia R' complementar , definit astfel: aR'b dac

i numai dac aRb nu are loc.

6.6.6. S se determine rela ia invers R-1. 6.6.7. S se determine rela ia complementar Rc definit astfel: aRcb prin defini ie dac a Rb. 6.6.8. Dac se dau dou rela ii R1 i R2, s se determine compunerea celor dou rela ii: T = R1 o R2 înseamn c (aTc dac i numai dac exist b astfel ca aR1b i bR2c). 6.7. Se dau mul imile A i B:

A = { a1 , a 2 ,..., a m } 297. B = { b1 , b2 ,..., bn } O rela ie R între A i B poate fi reprezentat printr-o matrice cu elementele:

r ij =

1 , daca a i R b j 298 0 , altfel .

6.7.1. Fiind date dou rela ii R1 i R2 peste acelea i mul imi, s se verifice dac rela ia R1 este inclus în R2 sau nu. 6.7.2. S se verifice dac R1 = R2 . 6.7.3. S se construiasc matricea rela iei R1

R2 (reuniune).

6.7.4. S se construiasc matricea rela iei R1 R2 (intersec ie).

68

6.7.5. Fie R o rela ie omogen peste M. S se construiasc rela ia Rk, unde Rk = Rk-1 R (adic Rk-1 compus cu R). 2

R

6.7.6. Fie R o rela ie omogen peste M. S se determine matricea rela iei R+ de închidere tranzitiv a lui R (R+ = R ... Rn) 6.8. Se dau dou opera ii o1 i o2 peste mul imea M={1,2,...,n}, reprezentate ca în problema 6.5. 6.8.1. S se verifice dac opera ia o1 este distributiv la dreapta fa de opera ia o2. 6.8.2. S se verifice dac opera ia o1 este distributiv la stânga fa de opera ia o2. 6.8.3. S se verifice dac structura algebric (M,o1,o2) este inel.

6.8.4. Dac (M,o1,o2) este inel, o1 opera ia aditiv , o2 opera ia multiplicativ , i1 elementul neutru al opera iei aditive, iar i2 elementul neutru al opera iei multiplicative, s se verifice existen a divizorilor lui zero în inel. 6.8.5. S se verifice dac structura algebric (M,o1,o2) este corp. 6.9. Se dau dou structuri algebrice finite cu câte o opera ie, (M1,o1) i (M2,o2), reprezentate ca în problema 6.5, cu M1 = M2 = {1,2,...,n}. Se d i aplica ia f : M1 --> M2, reprezentat printr-un vector F cu n componente astfel: Fi = j dac i numai dac f(i)=j. a) S se verifice dac f este un morfism. b) S se verifice dac f este izomorfism. 6.10. Fie A, B, C trei mul imi finite i rela iile R1 peste AxB i R2 peste BxC, reprezentate prin matricele lor, ca în problema 6.7. S se construiasc rela ia compus T = R1 R2. 6.11. Se dau n localit i. Într-o matrice A=(aij), i,j=1,2,..., n, sunt marcate lungimile drumurilor directe dintre localit i: a ij = d, 299 dac exist drum direct între i i j i d este distan între i i j;

a ij = 0, 300 dac nu exist drum direct între i i j. 6.11.1. S se determine drumul de lungime minim între dou localit i date. 6.11.2. S se determine matricea D=(dij) a drumurilor, unde dij = distan a minim între localit ile i i j, pentru i,j=1,2,...,n. 6.11.3.

Dac

d(i,j)

este

distan a

minim

între

i

i

δ (i) = max { d(i, j)| j = 1,2,..., n } 301 i localitatea i se nume te cea mai central δ (i) = min { δ (j)| j = 1,2,..., n } 302

j, dac

atunci

not m

prin

S se determine localitatea cea mai central . 6.12. Se dau n intersec ii de str zi într-un ora . Într-o matrice A=(aij), i,j=1,2,...,n, sunt marcate sensurile de circula ie pe str zile ora ului: a ij = 1, 303 dac se poate circula dinspre i spre j,

a ij = 0, 304

în caz contrar. 6.12.1. S se determine dac exist în ora str zi care formeaz un circuit.

69

6.12.2. Dac în fiecare intersec ie num rul sensurilor care intr în intersec ie coincide cu num rul sensurilor care ies din ea, s se determine un circuit care parcurge fiecare sens o singur dat , indiferent din ce intersec ie se porne te. 6.13. Se dau rezultatele la meciurile de fotbal a celor n echipe pe primele m etape. Se cere clasamentul. 6.14. Un pluton de solda i formeaz o coloan de defilare care are m rânduri, cu n solda i pe un rând. De pe fiecare rând este ales cel mai scund soldat, iar dintre cei ale i cel mai nalt prime te primul steag. Al doilea steag este repartizat similar - se aleg din fiecare rând solda ii cei mai înal i, iar dintre cei ale i cel mai scund prime te al doilea steag. În cazul în care exist mai mul i solda i cu aceea i în l ime, se alege primul dintre ei. S se afi eze în l imile purt torilor de steag. Valorile m, n i în l imile solda ilor se dau. 6.15. La un concurs de frumuse e pentru câini sunt n participan i i m criterii de selec ie, iar rezultatele se reprezint într-o matrice X de dimensiune m x n. Pentru fiecare criteriu "i" se cunosc: MAX(i) = punctajul maxim ce se poate ob ine la criteriul "i" i MIN(i) = limita inferioar a punctajului pentru criteriul "i". 6.15.1. S se dea num rul câinilor care nu îndeplinesc condi iile de participare. 6.15.2. S se decid dac exist câine câ tig tor la fiecare criteriu. 6.15.3. S se decid dac exist criterii la care exist mai mul i câ tig tori. 6.15.4. Dându-se un criteriu s se decid dac exist câine perfect dup acest criteriu. 6.15.5. S se decid dac exist câine care nu îndepline te condi iile de participare la nici un criteriu. 6.15.6. S se afi eze lista câ tig torilor la fiecare criteriu. 6.15.7. S se dea lista câ tig torilor la mai multe criterii. 6.15.8. S se decid dac exist câine care are suma punctajului maxim , dar la fiecare criteriu exist un câine mai bun decât el. 6.15.9. S se decid dac exist câini câ tig tori la un criteriu dar exist criterii la care nu sunt admi i. 6.15.10. S se decid dac exist doi câini A i B astfel încât A s fie mai bun decât B la fiecare criteriu. 6.15.11. S se dea lista criteriilor la care exist câini perfec i. 6.16. Se d o matrice A cu 12 linii i n coloane, astfel încât A(i,j) reprezint cantitatea de precipita ii c zut în jude ul j, în luna a i-a. S se elaboreze un program care s rezolve urm toarele cerin e : a) s se stabileasc cantitatea minim i maxim de precipita ii pe fiecare lun ; b) se cunosc vectorii PMAX i PMIN ce reprezint valoarea maxim i minim a cantit ilor de precipita ii înregistrate pe o perioad de 100 de ani. S se precizeze luna i jude ul în care s-a înregistrat o dep ire a uneia din cele dou valori ; c) s se calculeze media de precipita ii pe ar pentru fiecare lun ; d) s se calculeze media de precipita ii anual pentru fiecare jude i media de precipita ii anual pe ar . S se precizeze jude ul care e cel mai aproape de medie i jude ul pentru care abaterea de la medie e cea mai mare. 6.17. La o olimpiad particip n ri. Rezultatele se ob in într-o matrice de dimensiune n x 3. Prima coloan reprezint num rul medaliilor de aur ob inute de fiecare ar , a doua coloan num rul medaliilor de argint, iar a treia coloan num rul medaliilor de bronz. Se mai d un vector W de dimensiune 3, unde W(1) reprezint punctajul acordat pentru o medalie de aur, W(2) pentru o medalie de argint, iar W(3) pentru o medalie de bronz. S se adauge la matrice o nou coloan care s con in punctajul total realizat de fiecare ar participant . Se cere s se afle ara care a realizat

70

punctajul maxim, ara care a ob inut cel mai mare num r de medalii de aur i ara care a primit "lingura de lemn" (cel mai mic punctaj). S se decid dac exist ar care nu a ob inut nici o medalie. La sfâr itul olimpiadei s-a depistat un sportiv la controlul antidopping i i se retrage acestuia medalia de aur. tiind c provine din ara "i" i c medalia nu se acord altcuiva s se afi eze clasamentul rilor participante.

71