67 de Pagini de Probleme Rezolvate Si Teorie in Pascal

5

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

6

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 într-un 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.

7

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;

8

- 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; {eps,x�R, eps>0 �i x�0} REZULTATE r; {�r-rad(x) �<eps} unde prin rad(x) am notat radicalul de ordinul 2 din x definit în matematic�. Urmeaz� s� preciz�m metoda de rezolvare a problemei. Se �tie c� exist� cel pu�in dou� posibilit��i de a calcula pe r: - 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)*(m2-x)<0. Se ajunge la urm�toarea variant� final�: ALGORITMUL RADICAL ESTE: {Calculeaz� radical din x} DATE eps,x; {eps,x�R, eps>0 �i x�0} DAC� x<1 ATUNCI FIE a:=x; b:=1 {Ini�ializeaz� pe a �i b} ALTFEL FIE a:=1; b:=x

9

SF-DAC� REPET� DAC� (a2-x)*(m2-x)<0 ATUNCI b:=m {r�d�cina în stânga} ALTFEL a:=m {r�d�cina în dreapta} SF-DAC� P�N�C�ND b-a<eps SF-REPET� FIE r:=(a+b)/2; REZULTATE r; {�r-rad(x) �<eps} SF-ALGORITM 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� 2 2 2a + b = c 1. S� se tip�reasc� toate tripletele (a,b,c) de numere pitagorice, cu 0<a<b<c �i a+b+cn ordonate dup� suma a+b+c. Specificarea problemei este: DATE n; {n�N; pentru n<12 nu exist� triplete} REZULTATE toate tripletele de numere pitagorice (a,b,c) cu proprietatea 0<a<b<c �i a+b+cn. Vom nota prin S suma a+b+c. Se �tie c� (3,4,5) este primul triplet de numere pitagorice. În acest caz S ia valori de la 12 la n. Întrucât 3a<S variabila a ia valori de la 3 la S/3. Apoi 2b<S-a deci b va lua valori de la a+1 la (S-a)/2. Algoritmul pentru rezolvarea problemei este dat în continuare : Algoritmul NRPITAGORICE este : Date n; {n�N; pentru n<12 nu exist� triplete}

10

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; {Programul 1.1.2. Numere pitagorice} VAR n, { nN; a+b+cn } S, { S = a+b+c } a,b,c, {(a,b,c) triplet de numere pitagorice} { 0 < a < b < c } k : integer; { contor } 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. 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 < i < j < k n 1.3. S� se verifice dac� num�rul n�� este perfect. (Un num�r n este perfect dac� este egal cu suma divizorilor lui

11

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�� i+1 i i-1t = t + t 2, i=1,2,...

având 0 1t = t = 13. 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. 1.8. Fie a � N. S� se scrie un algoritm pentru calculul mediei aritmetice, geometrice �i armonice a tuturor divizorilor lui a. 1.9. Fie func�ia lui Euler � : N � N, unde �(n) este num�rul numerelor relativ prime cu n �i mai mici ca n. S� se tip�reasc� valorile �(k), k=1,2,...,m, pentru m�N dat. 1.10. Fie n,k � Z, n � k. S� se scrie un algoritm pentru calculul sumei

S = A + C + Pnk

nk

n 4.

1.11. S� se determine toate numerele întregi de trei cifre abc 5 cu proprietatea

abc = a + b + c3 3 3 6. 1.12. Se dau numerele z,l,a � �. S� se determine dac� tripletul (z,l,a) reprezint� o dat� calendaristic� a secolului nostru. 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 ,l ,a )n n n 7 data na�terii unei persoane �i ( z ,l ,a )c c c 8 o dat� curent�. S� se determine vârsta, în zile, a persoanei respective. 1.15. Se dau datele de na�tere ( z ,l ,a ) ( z ,l ,a )1 1 1 2 2 2si 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

n2y = n - 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.

12

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+y<n, pentru a,b,c apar�ine lui Z ��i n>0. 1.22. Se cere valoarea func�iei f:[-9,9]�� în punctul x, dac�

f x

x

-x - <x

x + , <x

x>

( ) =

≤≤

≤

�

�

��

�

��

1, pentru , pentru

pentru , pentru

13 1 0

2 0 010 1

2

1.23. S� se determine solu�iile întregi ale sistemului

y x

y 2 x - 16

2

2

≤≥

��

11

1.24. Se d� n � �. S� se calculeze

k=1

n

Ck

n(1+

12

+...+1k

)� 12

1.25. Fie a,b,c � �+. S� se scrie un algoritm pentru rezolvarea ecua�iei

2x + 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 � � ce verific� condi�ia nc, luat la întâmplare, s� fie prim. 1.26. Se cere un algoritm pentru determinarea numerelor impare succesive a c�ror sum� este egal� cu n3, pentru

n=1,...,20. (Ex. 3 3 31 = 1, 2 = 3+ 5, 3 = 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�

n,mn-1,m-1 n-1,m

b = 1, m = 0 m = n,

b + b , .

daca sauin 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 � �. S� se scrie un algoritm pentru calculul num�rului punctelor de coordonate întregi interioare elipsei de ecua�ie

2

2

2

2

xa

+y

b = 1 16

1.30. Fie dreapta d determinat� de punctele A(a1,a2) �i B(b1,b2). S� se determine pozi�ia punctelor A �i B fa�� de

13

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

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

ax + bxx + 2

, (a + b) / 2 < x b

2

2

daca

daca

≤ ≤

≤

�

��

��

18

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

14

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

continu� �i monoton�, folosind metoda combinat� a coardei �i a tangentei. Cu metoda dedus�, s� se calculeze Mn 19. Indica�ie. Se va lua f(x) = xn - M, iar intervalul (a,b), se înlocuie�te cu [0,M]. 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=x v - x v

v - v ; T = 2PI

x - xv - v

12

22

22

12

22

12

12

22

22

12 20

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 n-a zi a anului a sub forma (lun�, zi). 1.47. Se d� num�rul n � �. 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 2020. 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�.

15

17

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); { xi�Z, pentru i=1,2,...,n } REZULTATE (yj, j=1,k); { 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: { Versiunea 1 } 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 Pentru a parcurge celelalte numere avem nevoie de un contor, fie el i, �i de folosirea propozi�iei PENTRU. Ajungem la: ALGORITMUL DISTINCTE ESTE: { Versiunea 2 } 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 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 (ind�1) �i (ind<=k) EXECUT� DAC� xi=yind ATUNCI ind:=0 ALTFEL ind:=ind+1 SF-DAC� SF-C�TTIMP

18

Cu acestea ajungem la versiunea final� a algoritmului dorit. ALGORITMUL DISTINCTE ESTE: { Versiunea final� } DATE n, (xi, i=1,n); { xi�Z, pentru i=1,2,...,n } FIE y1:=x1; k:=1; PENTRU i:=2,n EXECUT� {Verific� dac� xi apar�ine lui Y} ind:=1; C�TTIMP (ind�1) �i (ind<=k) EXECUT� DAC� xi=yind ATUNCI ind:=0 ALTFEL ind:=ind+1 SF-DAC� SF-C�TTIMP {Dac� nu apar�ine atunci adaug� pe xi la Y} DAC� ind>0 ATUNCI k:=k+1; yk:=xi SF-DAC� SF-PENTRU REZULTATE (yj, j=1,k); {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 } SF-ALGORITM Programul Pascal corespunz�tor este: PROGRAM DISTINCTE; { Programul 2.1. Retine valorile distincte } VAR n, { num�rul numerelor date } i,j, { contor - variabile de lucru } k, { num�rul valorilor distincte g�site } ind : integer; { indicator; retine daca x[i] este in Y } X, { Vector cu numerele date } Y : array[1..100] of integer; { Vector cu numerele distincte } 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 { Verifica daca } ind:=1; { x[i] apar�ine lui Y } While (ind>0) and (ind<=k) do If x[i]=y[ind] then ind:=0 else ind:=ind+1; { Dac� nu apar�ine lui Y } IF ind>0 then { atunci adaug� pe x[i] la Y } begin k:=k+1; y[k]:=x[i] end; end; Writeln; { Tip�re�te rezultatele } Writeln(' Numerele distincte sunt'); For j:=1 to k do write(y[j]:5); readln

19

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 = ( y , y ,..., y )1 2 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; { n�N, n>0 } REZULTATE afi�area primelor n numere din �irul men�ionat. 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: { varianta1 } DATE n; { n�N, n>0 } Fie i:=1; t:=1; tip�re�te t; k:=2; ind:=1; { Pentru cazul k este prim } Câttimp i<n execut� * execut� t:=termenul urm�tor din �ir; i:=i+1; Tip�re�te t sf-câttimp; sf-algoritm 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

20

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 : { varianta final� } DATE n; { n�N, n>0 } Fie i:=1; t:=1; Tip�re�te t; k:=2; ind:=1; Cât timp i<n execut� t:=k; Dac� ind=1 atunci Cât timp (i<n) �i (t�1) execut� i:=i+1; Tip�re�te t; t:=t-1 sf-cât timp altfel d:=2; i:=i+1; Tip�re�te k; Cât timp d<k �i i<n execut� Dac� k mod d = 0 atunci j:=1; t:=d; Repet� i:=i+1; Tip�re�te t; j:=j+1; pân� când j>d 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. Pentru a re�ine termenii dori�i într-un �ir Y este suficient s� înlocuim propozi�ia "Tip�re�te t" prin propozi�ia " iY 22:=t". Transcriind în Pascal se ob�ine urm�torul program: Program SIR; { Programul 2.2. Tip�re�te n termeni dintr-un �ir } Var n, { Num�rul termenilor ce trebuie tip�ri�i } i, { Contor = num�rul termenilor tip�ri�i } j, { Contor = de cate ori s-a tip�rit d ! } k, { Num�r natural din care se ob�in ultimii termeni } d, { d va lua ca valori divizorii lui k } t, { t = termenul curent din �ir } ind : integer; { indicator ce retine daca este k prim }

21

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<n do begin t:=k; If ind=1 then while (i<n) and (t>=1) do begin i:=i+1; write(t:5); t:=t-1; end else begin d:=2; i:=i+1; write(k:5); while (d<k) and (i<n) do begin If k mod d = 0 then begin j:=1; t:=d; Repeat i:=i+1; write(t:5); j:=j+1 until j>d; 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 1 2 md ,d ,...,d 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 =

22

(c1c2c3...cn)10. 2.7. Se dau num�rul natural n > 1 �i X � �n. S� se determine indicele componentei minime �i indicele componentei maxime din X. 2.8. Se dau num�rul natural n > 1 �i numerele x1, x2, ..., xn. S� se g�seasc� toate pozi�iile 1 2 kp , p ,..., p 24 pe care se afl� valoarea maxim�. 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}. 2.12. Se dau num�rul natural n > 1 �i numerele x1, x2, ..., xn. S� se g�seasc� toate numerele distincte

1 2 my , y ,..., y 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

i

j j

1 2 i

y = { x |x > 0, j = 1,i }, i

( x + x +...+ x ) / i, i

max daca este par

daca 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

i

j

i

y = { x | j = i,n }, i

m , i

max daca este par

daca 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. S� se calculeze componentele vectorului

23

Y = ( y , y ,..., y ).1 2 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 {xj�xj<xi ,j<i}, s� se determine vectorul Y=(y1,y2,...,yn). 2.24. Se dau num�rul natural n > 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 | m - k* s < x < m + k* s}i 1 i 1 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 1 2 no o ox x ... x .≥ ≥ ≥ 30 2.29. Se dau a � �, n � �i numerele reale x1, x2,..., xn. S� se determine cardinalul (num�rul elementelor) mul�imii { i | x a }i ≥ 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

24

i1 2 i i

i i+1 n iz =

x + x +...+ x , x > a,

{ x ,x ,...,x }, x a.

dacamax daca

�

� ≤��

32

2.33. Se dau a � �, n � � �i numerele reale 1 2 nx , x ,..., x 33. S� se elimine din �irul X toate elementele mai mici decât a. 2.34. Se dau a � �, n � � �i numerele reale 1 2 nx , x ,..., x 34. S� se ordoneze numerele date cresc�tor dup� distan�a lor fa�� de num�rul real a. 2.35. Se dau n � �, numerele reale a, b, a<b, �i vectorul X cu componente reale 1 2 nx , x ,..., x 35. S� se determine media aritmetic� a componentelor lui X aflate în intervalul [a,b] �i s� se listeze perechile (i,x )i 36 pentru care

ix 37 �[a,b]. 2.36. Se dau n � �, numerele reale a, b, a<b, �i vectorul X cu componente reale 1 2 nx , x ,..., x 38. S� se re�in� în vectorul Y= (y1,y2,...,yk), toate componentele vectorului X care apar�in intervalului [a,b]. 2.37. Se dau n � �, numerele reale a, b, a<b, �i vectorul X cu componente reale 1 2 nx , x ,..., x 39. S� se g�seasc� minimul �i maximul numerelor mai mici decât b, apoi s� se elimine din vectorul X toate componentele care nu apar�in intervalului [a,b]. 2.38. Se dau n � � �i numerele reale i ix , y 40, i=1,n. S� se calculeze

d = |x - y |+|x - y |+...+|x - y |1 1 2 2 n n 41 �i v = { { x , y }| i = 1,n}i imax min 42. 2.39. Se dau n � � �i numerele reale i ix , y 43, i=1,2,...,n. S� se re�in� în 1 2 ki , i ,..., i 44 toate pozi�iile p pentru care xp=yp. 2.40. Se dau n � � �i numerele reale i ix , y 45, i=1,2,...,n. S� se calculeze

ii i i

i i iz =

{ x + y }, x ,

{ x + y }, x ,

max daca

max daca

�

�

≤>

��

0

046

pentru i=1,2,...,n. 2.41. Se dau n � �i numerele reale i ix , y 47, i=1,2,...,n. S� se calculeze m= ( x + x +...+ x ) / n1 2 n 48 �i

d = ( x * x + x * x +...+ x * x ) / n1 1 2 2 n n 49 �i s� se tip�reasc� to�i indicii i pentru care |x - m|< 3di 50. 2.42. Se dau n � � �i numerele reale i ix , y 51, i=1,2,...,n. S� se calculeze

ii i

1 2 iz =

x + y , i ,

{ x ,x ,...,x }, i ,

daca este imparmax daca este par

�

�

��

52

pentru i=1,2,...,n �i v = { z , z ,..., z }1 2 nmin 53.

25

2.43. Se dau n � �i numerele reale i ix , y 54, i =1,2,...,n. S� se calculeze

i

i i i

i i

i i i

c =

x , x < y ,

0 , x = y ,

y , x > y ,

daca

daca

daca

�

�

�

�

��

��

55

pentru i=1,2,...,n. 2.44. Se dau n � �i numerele reale i ix , y 56, i=1,2,...,n. S� se calculeze

i

1 2 i i i

i i

i n i i

z =

( x + x +...+ x ) / i, x < y ,

0, x = y ,

{| y | ,... ,| y | }, x > y ,

daca

daca

max daca

�

�

�

�

��

��

57


E = {|x |,| y | } + ...+ {|x |,| y | },1 1 n nmin min 59

�i s� se determine elementele mul�imii { i | x * x > E}i i 60.

��Se dau n � �i numerele reale i ix , y 61,i=1,2,...,n. S� se calculeze ��

s1 = ( y + y + ... + y ),

s2 = ( y * x + y * x +...+ y * x ) / s1,

s3 = ( y * x * x + y * x * x +...+ y * x * x ) / s1,

1 2 n

1 1 2 2 n n

1 1 1 2 2 2 n n n

62

�i m = cardinalul mul�imii { x | 3(s3 - s2* s2) > |x - s2| }i i 63. 2.47. Se dau n � � �i numerele reale i ix , y 64, i=1,2,...,n. S� se formeze vectorul Z cu componentele

i1 2 i i i

i 1 2 i i

z = { x + x +...+ x ) / i, y }, y 0,

{ x ,( y + y +...+ y ) / i}, y < 0,

max daca

min daca

�

�

≥��

65

pentru i=1,2,...,n. 2.48. Se dau n � � �i numerele reale i ix , y 66, i=1,2,...,n. S� se calculeze

26

i

1 2 i i i

1 2 i i i

i i+1 n i i

z =

{ x , x ,..., x }, x < y ,

{ { x ,x ,...,x }, 0}, x = y ,

{ y , y ,..., y }, x > y ,

max daca

max min daca

min daca

�

�

�

�

��

��

67


i

1 2 i i i

i 1 2 i i i

i i+1 n i i i

c =

( x + x +...+ x ) / i, x y < 0,

{ x , y , y ,..., y }, x y = 0,

{ x ,x ,...,x , y }, x y > 0,

daca

max daca

min daca

�

�

�

�

��

��

69

pentru i=1,2,...,n. 2.50. Se dau n � �i numerele reale i ix , y 70, i=1,2,...,n. S� se re�in� pozi�iile 1 2 ki , i , ... , i 71, pe care cei doi vectori coincid. S� se elimine din vectorii X �i Y termenii de pe aceste pozi�ii. 2.51. Se dau n � �i numerele reale i ix , y 72, i=1,2,...,n. S� se determine vectorul M = ( m ,m ,...,m )1 2 n 73,

unde im 74 este pozi�ia componentei maxime a vectorului

( x ,x ,...,x , y , y ,..., y )1 2 i i i+1 n 75 (dac� exist� mai multe, pozi�ia primei valori maxime). 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 � �i numerele reale i ix , y 76, i=1,2,...,n. S� se calculeze

E = |x - y | + |x - y | + ... + |x - y |1 1 2 2 n n 77 �i

i

i i i i i

i 1 2 i i i

i i+1 n i i i

c =

x / ( y * y +1), |x - y | < E,

{ x , y , y ,..., y }, |x - y | = E,

{ x ,x ,...,x , y }, |x - y | > E,

daca

max daca

min daca

�

�

�

�

��

��

78

pentru i=1,2,...,n. 2.54. Se dau n � �i numerele reale i ix , y ,79 i=1,2,...,n. Dac� 1 2 n 1 2 nx < x <...< x si y < y <...< y 80 s� se depun� direct toate numerele distincte în �irul Z ordonat cresc�tor: 1 2 kz < z < ... < z 81, deci f�r� a mai fi necesar� ordonarea �irului Z. 2.55. Se dau a � �, n � �i perechile ( x , y )i 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).

27

2.56. Se dau a � �, n � �i perechile ( x , y ),i i 83 i=1,2,...,n de numere reale. S� se determine indicii

1 2 ki ,i ,...,i 84 pentru care punctele ( x , y )i i 85 din plan se afl� în interiorul cercului de raz� a �i centru (0,0). 2.57. Se dau a � �, n � �i perechile ( x , y )i i 86, i=1,2,...,n de numere reale. S� se calculeze num�rul m al valorilor yi mai mari decât a �i

i

1 2 i

i i

1 1 2 2 i i

z =

( x + x +...+ x ) / i, i < m,

{0, x , y }, i = m,

|x - y |+|x - y |+...+|x - y |, i > m.

daca

max daca

daca

�

�

�

�

��

��

87

pentru i=1,2,...,n. 2.58. Se dau m,n � � �i cifrele zecimale ia ,88 i=1,2,...,m �i jb ,89 j=1,2,...,n. Dac� numerele întregi A �i B au

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

A = ( a a ...a )

si

B = ( b b ...b )

1 2 m 10

1 2 n 10

90

s� se calculeze cifrele ic ,91 i=1,2,...,r, ale reprezent�rii num�rului întreg C=A+B.

2.59. Se dau m,n � � �i cifrele zecimale ia ,92 i=1,2,...,m �i jb ,93 j=1,2,...,n. Dac� A �i B sunt numerele definite

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

kod = -1, dac� cel pu�in o valoare ib 95 nu este corect�, kod = 0 , dac� A = B, kod = 1 , dac� A < B, kod = 2, dac� A > B. 2.60. Se dau m,n � � �i cifrele zecimale ia ,96 i=1,2,...,m �i jb ,97 j=1,2,...,n. Dac� numerele reale A �i B au

reprezent�rile în baza 10: A = ( a a ...a ,a ...a )1 2 r r+1 m 10 98

B = ( b b ...b ,b ...b )1 2 s s+1 n 10 99 pentru r<m �i s<n da�i, s� se calculeze indicatorul kod egal cu -1 dac� datele ini�iale sunt gre�ite, 0 dac� A < B, 1 dac� A = B, respectiv 2 dac� A > 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 = ( v ,v ,...v )1 2 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 = ( v ,v ,...v )1 2 n 101 �tiind c� cele n componente ale sale sunt primii n termeni ai �irului X.

28

2.63. Se d� n � �, n>1. S� se construiasc� vectorul V = ( v ,v ,...v )1 2 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<q<r, triplete ordonate dup� suma

p+q+r. Numerele p, q, r se numesc pitagorice dac� 2 2 2p + q = r 103.

2.64. Se dau m,n � �, n>1. S� se construiasc� vectorul V = ( v ,v ,...v )1 2 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 mx 105 (f�r� a re�ine

termenii ix 106 în calculator). 2.65. Se dau m,n � �, n>1. S� se construiasc� vectorul V = ( v ,v ,...v )1 2 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 mx 108 (f�r� a re�ine termenii ix 109 în calculator). 2.66. Se dau m,n � �, n>1. S� se construiasc� vectorul V = ( v ,v ,...v )1 2 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 mx 111 (f�r� a re�ine termenii ix 112 în calculator). 2.67. Se dau m,n � �, n>1. S� se construiasc� vectorul V = ( v ,v ,...v )1 2 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 mx 114 (f�r� a re�ine termenii ix 115 în calculator). 2.68. Se dau m,n � �, n>1. S� se construiasc� vectorul V = ( v ,v ,...v )1 2 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

mx 117 (f�r� a re�ine termenii ix 118 în calculator). 2.69. Se dau n � � �i seria

n=1

13n - 2

1

3n - 1

13n

.∞

� 119

S� se construiasc� vectorul V = ( v ,v ,...,v )1 2 n 120 �tiind c� cele n componente ale vectorului V sunt sume par�iale ale

acestei serii, 1 20 i 20+5iv = s , v = s ,121 i=2,3,...,n, unde ks 122 este suma primilor k termeni. 2.70. Se d� n � �i seria

n=1

n-12n-1 2n-1(-1 )

42n - 1

12

+1

3

∞

� ��

� 123

29


acestei serii, 1 20 i 20+5iv = s , v = s ,125 i=2,3,...,n, unde ks 126 este suma primilor k termeni. 2.71. Se dau n � �i se cunoa�te seria

33

2 (1+

16

+1* 26* 10

+1* 2* 3

6* 10* 14+... ) 127


acestei serii, 1 20 i 20+5iv = s , v = s ,129 i=2,3,...,n, unde ks 130 este suma primilor k termeni. 2.72. Se dau n,m � �i se cunoa�te seria

2 1+13

+1* 23* 5

+1* 2* 33* 5* 7

+...��

� 131


acestei serii, 1 20 i 20+miv = s , v = s ,133 i=2,3,...,n, unde ks 134 este suma primilor k termeni. 2.73. Se dau n,m � �i se cunoa�te seria

� i 2 3u = 1+13

19

+15

19

+17

19

+...135


acestei serii, 1 20 i 20+miv = s , v = s ,137 i=2,3,...,n, unde ks 138 este suma primilor k termeni. 2.74. Se dau n,m,l � � �i se cunoa�te seria

1+1

3* 3+

1* 23* 5* 5

+1* 2* 3

3* 5* 7* 7+

1* 2* 3* 43* 5* 7* 9* 9

+...139


acestei serii, 1 m i m+l*iv = s , v = s ,141 i=2,3,...,n, unde ks 142 este suma primilor k termeni. 2.75. Se dau n,m,l � �i se cunoa�te seria

1+1

3* 3+

1* 23* 5* 5

+1* 2* 3

3* 5* 7* 7+

1* 2* 3* 43* 5* 7* 9* 9

+...143


acestei serii, 1 l i l+miv = s , v = s ,145 i=2,3,...,n, unde ks 146 este suma primilor k termeni. 2.76. Se cunoa�te seria convergent� din problema 2.69. S� se determine suma par�ial� sn a primilor n termeni pentru care |s - s | < n n-1 ε 147 pentru � dat, n fiind cel mai mic num�r natural posibil.

30

2.77. Se cunoa�te seria convergent� din problema 2.70. S� se determine suma par�ial� sn a primilor n termeni pentru care |s - s | < n n-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 |s - s | < n n-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 |s - s | < n n-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 |s - s | < n n-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 |s - s | < n n-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 |s - s | < n n-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��

k k-1 k-1x = ( x + a / x ) / 2,154 pentru a �i x0 numere reale date, pentru care |x - x |< 0.00001,n n-1 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��

k k-1k-1m-1x =

1m

* (m -1)x + a

x,

��

� 156

pentru m � �i a, x0 � da�i, pentru care |x - x |< 0.00001,n n-1 157 n fiind cel mai mic posibil. 2.85. S� se tip�reasc� primii n termeni ai �irului (xk) pentru care |x - x |< 0.00001,n n-1 158 n fiind cel mai mic posibil, în cazul �irului

n

3 5n

2n+1

x = x - x3

+ x5

- ...+(-1 ) *x

2n+1159

pentru x � dat. 2.86. S� se tip�reasc� primii n termeni ai �irului (xk) pentru care |x - x |< 0.00001,n n-1 160 n fiind cel mai mic

31

posibil, în cazul �irului

n

2 n

x = 1+ x +x2!

+...+xn!

161

2.87. S� se tip�reasc� primii n termeni ai �irului (xk) pentru care |x - x |< 0.00001,n n-1 162 n fiind cel mai mic posibil, în cazul �irului

n

2 n

x = 1+ x +x2!

+...+xn!

163

pentru x � dat. 2.88. S� se tip�reasc� primii n termeni ai �irului (xk) pentru care |x - x |< 0.00001,n n-1 164 n fiind cel mai mic posibil, în cazul �irului

n

32n+1

2n+1

x = x - x3!

+ ... +(-1 ) *x

(2n+1)!165

pentru x � 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 n+1 n n nx = x - f( x ) / f ( x ),′ 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 , y ]i i 167, i =1,2,...,n, definit astfel:

1. [ x , y ] = [a,b]0 0 168 ;

2. [ x , y ]i i 169 se ob�ine împ�r�ind intervalul [ x , y ]i-1 i-1 170 în trei p�r�i egale �i luând partea care con�ine r�d�cina; 3. n este cel mai mic num�r natural pentru care n ny - x 171<eps, pentru eps num�r pozitiv dat.

32

33

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, { num�rul punctelor date } (xi,yi, i=1,n), { coordonatele celor n puncte } a,b, { coordonatele centrului cercului } r; { raza cercului dat } REZULTATE nr; { 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, { num�rul punctelor date } (xi,yi, i=1,n), { coordonatele celor n puncte } a,b, { coordonatele centrului cercului } r; { raza cercului dat } Fie nr:=0; Pentru i:=1,n execut�

Dac� 2

i2

i2( x - a) +( y - b) < r 172 atunci nr:=nr+1 sf-dac�

sf-pentru REZULTATE nr; { num�rul punctelor aflate în interiorul cercului } sf-algoritm. Programul PASCAL este dat în continuare. Program Nr_Puncte_în_cerc; {Programul 3.1 Nr. puncte într-un cerc} var n, { num�rul punctelor date } i, { variabila de lucru - contor } nr : integer; { num�rul punctelor aflate in cerc } a,b, { coordonatele centrului cercului } r : real; { raza cercului dat } x, { x[i] = abscisa iar }

34

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)<r*r then nr:=nr+1; { tip�rirea rezultatelor } writeln('Nr punctelor din interiorul cercului= ',nr); end. 3.2. INTERCLASARE Se dau m,n � � �i vectorii X,Y de componente numere întregi, ordonate nedescresc�tor. Forma�i vectorul Z de dimensiune m+n, având drept componente toate componentele vectorilor X �i Y, de asemenea ordonate nedescresc�tor. Rezolvare Specificarea problemei este: DATE m, { num�rul componentelor lui X } n, { num�rul componentelor lui Y } (xi,i=1,m), {componentele vectorului X: x1 x2 ... xm} (yi,i=1,n); {componentele vectorului Y: y1 y2 ... yn} REZULTATE k, { num�rul componentelor lui Z: k=m+n } (zi, i=1,k), { componentele vectorului Z. Ele sunt toate } { componentele din X �i Y. Avem z1 z2 ... zk } Pentru a forma vectorul Z observ�m mai întâi c� z1 este cel mai mic dintre x1 �i y1. Cât timp mai sunt componente �i în X �i în Y urm�torul z va fi cel mai mic dintre xi �i yj, i, respectiv j, fiind pozi�iile în cei doi vectori pân� la care componentele au fost deja depuse în Z. Evident se va începe cu i=1 �i j=1, iar k - pozi�ia curent� în vectorul Z va fi ini�ial tot 1.

35

Algoritmul pentru rezolvarea problemei este dat în continuare: Algoritmul INTERCLASARE este : { Z := X interclasat cu Y } Date m, { num�rul componentelor lui X } n, { num�rul componentelor lui Y } (xi,i=1,m), {componentele vectorului X. Avem x1 x2 ...xm } (yi,i=1,n), {componentele vectorului Y. Avem y1 y2 ...yn } Fie i:=1; j:=1; k:=0; Câttimp im �i jn execut� Dac� xi<yj atunci k:=k+1; z[k]:=x[i]; i:=i+1 altfel k:=k+1; z[k]:=y[j]; j:=j+1 sf-dac� sf-câttimp Câttimp (i<=m) execut� k:=k+1; z[k]:=x[i]; i:=i+1 sf-câttimp Câttimp (j<=n) execut� k:=k+1; z[k]:=y[j]; j:=j+1 sf-c�ttimp Rezultate k, { k = num�rul componentelor lui Z: k=m+n} (zi, i=1,k), { componentele vectorului Z. Ele sunt toate } { componentele din X �i Y �i z1 z2 ... zk } sf-algoritm Programul PASCAL este dat în continuare. PROGRAM INTERCLASARE; { Programul 3.2. Interclasarea } { componentelor vectorilor X si Y } VAR m, { num�rul componentelor lui X } n, { num�rul componentelor lui Y } i,j, { contori in X, respectiv Y } k: integer; { num�rul valorilor g�site in Z } X,Y, { Vectori cu numerele date } Z : array[1..100] of integer; { Vector rezultat-cu } { componentele din X si Y interclasate} BEGIN { Citesc m, X } Writeln('Se dau doi vectori X �i Y'); Write('Nr.comp. lui X='); readln(m); For i:=1 to m do begin write('x(',i,')='); readln(x[i]) end; { Citesc n, Y } Write('Nr.comp. lui Y='); readln(n); For j:=1 to n do begin write('y(',j,')='); readln(y[j]) end; { Interclasarea } i:=1; j:=1; k:=0; While (i<=m) and (j<=n) do If x[i]<y[j] then begin k:=k+1; z[k]:=x[i]; i:=i+1 end else begin k:=k+1; z[k]:=y[j]; j:=j+1 end; While (i<=m) do

36

begin k:=k+1; z[k]:=x[i]; i:=i+1 end; While (j<=n) do begin k:=k+1; z[k]:=y[j]; j:=j+1 end; Writeln; { Tip�re�te rezultatele } Writeln(' Numerele ordonate sunt'); For j:=1 to k do write(z[j]:5); readln END. 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= { a , a ,..., a }

B = { b , b ,..., b }1 2 m

1 2 n173

S� se calculeze C = A � B. 3.11. Se dau m,n � � �i mul�imile

A= { a , a ,..., a }

B = { b , b ,..., b }1 2 m

1 2 n174

S� se calculeze C = A � B. 3.12. Se dau m,n � � �i mul�imile

37

A= { a , a ,..., a }

B = { b , b ,..., b }1 2 m

1 2 n175

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. 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 num�r. 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. 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 M. 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� �i s� se afle punctul de distan�� maxim� fa�� de dreapt�.

38

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<a1 sau am< xj.

39

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 :

a(i, j)=x

(i j - i+1), (4.1)k=1

i j

k

•

�•

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, {num�rul liniilor matricei A} n, (num�rul coloanelor matricei A} X; {vector ce con�ine cele m*n numere date} REZULTATE A {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>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 : {Se calculeaz� A conform formulei 4.1} Date m, n, {m*n este dimensiunea matricei cerute} X; {X=(X(i),i=1,m*n) este un vector cu m*n componente date} 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; {Matrice de dimensiune m*n definit� de (4.1)} sf-algoritm Programul PASCAL corespunz�tor este urm�torul: Program matrice; { Programul 4.1. Construirea unei matrice A } Type sir=array[1..100] of real;

40

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, {dau dimensiunea matricei} k, {num�rul componentelor �irului X} X; {vector de dimensiune k} REZULTATE A {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 m-a �i pân� la prima linie. Variabile folosite: X - vector ce con�ine numerele date, de lungime k;

41

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, {dau dimensiunea matricei} k, {num�rul componentelor �irului X} X; {vector de dimensiune k} 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 {matrice de dimensiune m*n} sf-dac� 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 } then write('Prea pu�ine elemente in �ir') { semnaleaz� eroare } 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}

42

end else begin { pe coloana } for i:=m downto 1 do { de jos in sus } begin a[i,j]:=x[l]; l:=l+1 end; kod := 0 { se schimba valoarea lui kod} end; j := j+1 until j>n; {se repeta pana când s-a completat coloana n} for i:= 1 to m do { tip�re�te linia i a matricei } begin for j := 1 to n do write(a[i,j]:5); writeln end end end. 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. 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 matricei. 4.2. Se d� o matrice A � Mm,n(R). S� se adauge a (n+1)-a coloan� acestei matrice, definit� prin:

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

n

� 177 , pentru i=1,m.

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 = { v | i = 1,m}imin 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 [�,�]. 4.9. Se d� o matrice A � Mm,n(R+). Pentru fiecare linie s� se scad� din elementele sale valoarea minim� din acea linie. 4.10. Se d� o matrice A � Mm,n(R). S� se construiasc� vectorul X =

43

( x , x , ..., x )1 2 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<l<n, 1<k<m). Prin opera�ii de schimbare a dou� linii între ele s� se ob�in� pe coloana k elementele ordonate cresc�tor pân� la linia l �i apoi descresc�tor. 4.13. Se d� o matrice A � Mm,n(R+) �i numerele naturale l �i k (1<k<n, 1<l<m). Prin opera�ii de schimbare a dou� coloane între ele s� se ob�in� pe linia k elementele ordonate descresc�tor pân� la coloana l �i apoi cresc�tor. 4.14. Se d� o matrice A � Mm,n(R). S� se împart� elementele fiec�rei linii la media aritmetic� a elementelor pozitive din linia respectiv�. Dac� într-o linie nu exist� elemente pozitive, linia r�mâne neschimbat�. 4.15. Se d� o matrice A � Mm,n(R). S� se calculeze media aritmetic� a elementelor matricei aflate deasupra diagonalei principale, precum �i media armonic� a elementelor pozitive care se g�sesc sub diagonala principal�. 4.16. Se d� o matrice A � Mm,n(R+). S� se verifice dac� exist� dou� linii propor�ionale în matricea dat�. 4.17. Se d� o matrice A � Mm,n(R+). S� se construiasc� un vector X de n componente, astfel încât X(i) s� fie num�rul elementelor distincte din coloana a i-a, pentru i=1,2,...,n. 4.18. Se d� o matrice A � Mm,n(R+). S� se schimbe între ele liniile matricei astfel încât �irul sumelor

1 2 ms , s ,..., s 180 s� fie ordonat descresc�tor, unde

ij=1

n

ijs = a , i = 1,m� 181.

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 ( i , j )0 0 182 se nume�te punct �a dac�:

a) 0 0i , ja 183 este maxim pe coloana j0;

b) 0 0i , ja 184 este minim pe linia 0i 185.

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

ij ij2b = ( a - )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

ijij

i in 1j mjb =

a , i < j

( a 1+ a + a + a ) / 4, .

daca

altfel

��

187

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

44

ij

ij

ij

ij

b =

- 1, a (x, y)

0, a {x, y}

1, a [x, y].

daca

daca

daca

�

�

�

∈∈∉

�

��

��

188

4.24. Se d� A � Mm,n(R). S� se formeze matricea B cu m linii �i n coloane unde: ij ik ijb = | { a | k = 1,2,...,n}| - amax 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

ijij ij

b = a , a

0, ,

daca este par

altfel

��

190 ijij ij

c = a , a

0, .

daca este impar

altfel

��

191

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

ij

ij

ij

ij

ij

b =

0 , a < x

1 , x a < y

2 , y a < z

3 , a z.

daca

daca

daca

daca

�

�

�

�

≤≤

≥

�

�

��

�

��

192

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

i ij

ji=1

m

ij i

b = {a | j = 1,2,...,n } , i = 1,2,...,m

c = a b , j = 1,2,...,n.

max

�193

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.

45

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� A�MPn(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:

46

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 = { x ,...,x }, i

{ x |x < 0,k = 1, j}, i .i, ji n

k k

min daca este par

max daca 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 � � �i X � Vm*n(R). S� se genereze o matrice A � Mm,n(R) definit� astfel:

a = ( x + x +...+ x ) / (ij - i+1) , x > 0

{ x ,x ,...,x } , x 0iji i+1 ij i

i i+1 ij i

daca

max daca

�

� ≤��

195

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:

a = xijl=(i-1)n+1

(i-1)n+ j

l� 196

pentru i=1,2,...,m �i j=1,2,...,n. 4.49. Se dau 2 numere naturale m �i n. S� se construiasc� matricea A�Mm,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,

47

pentru i=1,2,...,m �i j=1,2,...,n. 4.52. Se d� a � R �i fie M(1)=a. S� se formeze matricea p�trat� A de ordinul n de forma M(1) M(12) M(11) M(10) M(2) M(13) M(16) M( 9) M(3) M(14) M(15) M( 8) M(4) M( 5) M( 6) M( 7)

(în cazul n=4) dac� M(k) = I + 10M(k-1)2 197

pentru k = 2,3,...,n*n, unde pI 198 reprezint� r�sturnatul num�rului p (exemplu: r�sturnatul num�rului 123 este num�rul

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. 4.54. Se d� o matrice cu elemente cuvinte de maximum 30 de litere sau spa�ii. S� se afle frecven�a vocalelor în cuvinte: - pe linii; - pe coloane; - în matrice. 4.55. Se dau vectorii A � Vm(R) �i B � Vn(R). S� se formeze matricea C�Mm,n(R) dac�

c(i, j) = a(k)

b(k)

k=1

i

k= j

n

�

�199

Î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 C�Mm,n(R) dac�

iji j

1 m 1 nc =

a * b{ a ,...,a ,b ,...,b }max

200

Î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 C�Mm,n(R) dac� ij i i j jc = { a , b , a + b }, i = 1,2,...,m, j = 1,2,..nmax 201.

4.58. Se dau vectorii A � Vm(R) �i B � Vn(R). S� se formeze matricea C�Mm,n(R) dac�

ijk=1

i

kp=1

j

pc = a b� �• 202

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

ij ij ijc = {a ,b } , i = 1,m j = 1,nmax 203.

4.60. Se dau dou� matrice A,B � MPn(R). S� se determine matricea C � MPn(R) definit� prin: ij ik kjc = { a + b | k = 1,2,...,n}.min 204

48

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

ijij ij

ij ijc =

0 , a b 1 , a = b .

daca

daca

�

�

≠��

205

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

j=1

n

ijj=1

n

ija < b .� � 206

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 1 2 nnx , x ,..., x [0,2 ) .∈ 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:

ij

k l

k2

l

i i+1 j

a =

{ x |k j si k i} , j i x > 0, l = j, j +1,...,i

{ x | j k i}, j i x 0, l = j, j +1,...,i

( x + x +...+ x ) / (j - i+1), j > i .

max daca si

min daca sidaca

≥ ≤ ≤ ∃≤ ≤ ≤ ∃ ≤

�

��

��

�

�

�

209

49

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: REUN(n,m,A,B,nm,AUB); DATE {de intrare} n, {num�rul elementelor mul�imii A} m, {num�rul elementelor mul�imii B} A, {mul�imea {a1, a2, ... , an } } B; {mul�imea {b1, b2, ... , bm } } REZULTATE nm, {num�rul elementelor reuniunii } AUB {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

50

- o procedur� pentru calculul reuniunii a dou� mul�imi, cu ordonarea �i tip�rirea rezultatului: TIPREUN(n,m,A,B,nm,AUB). aceea�i semnifica�ie ca la procedura REUN, dar, în plus, se tip�re�te AUB. Algoritmul pentru rezolvarea problemei, descris în limbajul PSEUDOCOD, este urm�torul: Algoritmul Exemplu1 este: Cheam� CIT(n,A); { A e vectorul care con�ine în componentele } { sale cele n elemente ale mul�imii A} Cheam� CIT(m,B); { Cite�te mul�imea B} Cheam� CIT(p,C); { Cite�te mul�imea C} Cheam� TIPORDON(n,A); Cheam� TIPORDON(m,B); Cheam� TIPORDON(p,C); Cheam� TIPREUN(n,A,m,B,n1,AB); { Tip�re�te pe AB := A U B} Cheam� TIPREUN(m,B,p,C,m1,BC); Cheam� TIPREUN(p,C,n,A,p1,CA); Sf-algoritm. Subalgoritmii apela�i mai sus sunt descri�i în continuare: Subalgoritmul ORDON(r,X) este: {Ordoneaz� componentele lui X} Repet� {examineaz� toate componentele} Fie sch:= 0; {ipoteza c� sunt ordonate} Pentru i:= 1, r-1 execut� Dac� i i+1x > x 210 atunci Fie xx:= ix ;211 Fie i i+1x := x ;212

Fie i+1x := 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: {AUB := A � B} Pentru i:=1, n execut� i iAUB := A ; 214 sf-pentru Fie n1:=n; Pentru j=1, m execut� Fie i:=1; Câttimp ( B A ) si (i n)j i≠ ≤ 215 execut� i:=i+1 sf-câttimp

Dac� i>n atunci Fie n1:=n1+1; 216 sf-dac� sf-pentru sf-REUN Subalgoritmul TIPORDON(r,X,ch); {Ordoneaz� �i apoi tip�re�te} { cele n componente ale vectorului X} {ch=numele mul�imii reprezentat� în vectorul X} Cheam� ORDON(p,X); Cheam� TIPAR(r,X,ch); sf-REUN Subalgoritmul TIPREUN(n,A,m,B,n1,AUB,ch) este: { AUB:= A � B}

51

{Ordoneaz� �i tip�re�te pe AUB} Cheam� REUN(m,B,p,C,m1,BC); Cheam� TIPORDON(r,X,ch); sf-TIPREUN Traducerea algoritmului în limbajul PASCAL este urm�toarea: Program exemplu1; { Programul 5.1 } {opera�ii cu mul�imi reprezentate ca vectori} Type sir = array [1..30] of real; s3 = string[3]; Var n, m, p, n1, m1, p1 : integer; a, b, c, {a,b,c con�in elementele a trei mul�imi de numere } ab, bc, ca : sir; Procedure cit(var n: integer; var a: sir; ch: s3); {Cite�te n si } { mul�imea a cu n elemente} {ch=numele mul�imii citite} 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; {Tip�re�te mul�imea a cu} ch: s3); {numele ch având n elemente} 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; {Ordoneaz� cresc�tor elementele} var x: sir); {vectorului X cu r componente} 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; Procedure tipordon(r: integer; var x: sir; nume:string);

52

var xx: real; i, sch: integer; begin ordon(r, x); tipar(r, x, nume); end; Procedure reun(n, m: integer; A,B: sir; {Calculeaza A � B} 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; {Calculeaz� reuniunea,} var n1: integer; {ordoneaz� elementele �i} var AUB:sir; nume:string); {tip�re�te rezultatul} var xx: real; i, sch: integer; begin reun(n, m, A, B, n1, AUB, nume); ordon(n1, AUB); tipar(n1, AUB, nume); end; Begin {programul principal} 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. 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; {n�N, n>3} REZULTATE (pj,j=1,n); {p1,p2,...,pn sunt primele n numere prime}

53

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: {Se caut� n numere prime} 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 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; {Programul 5.2. G�se�te primele n numere prime } Type vector = array[1..999] of integer; Var n, { num�rul numerelor g�site } i : integer; { variabila contor in P } P : vector; { Vectorul numerelor prime } function prim(n: integer): boolean; {Dac� n e prim atunci TRUE} 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; { In vectorul P se ob�in } Var P:vector); { primele n numere prime } 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;

54

end; begin {programul principal} 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. 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 = qnX

n + ... + q1X + q0, R = rkX

k + ... + 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 R• 218 a dou� polinoame Q �i R, tip�ri�i polinoamele (x + 1)n pentru n = 1,2,...,12. 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 f�g �i g�f într-un punct dat, folosind o func�ie de calcul a valorii unui polinom într-un punct. 5.10. Folosind dezvoltarea în serie:

55

arcsin x = x + 12

x3

+ 1 32 4

x5

+ 1 3 52 4 6

x7

+ ...3 5 7

•••

•• •• •

• 219

s� se defineasc� o func�ie PASCAL care calculeaz� arcsin x cu precizia ε = 10 .-6 220 S� se tip�reasc� apoi valorile:

iv = 1i

, i = 2,3,...,marcsin 221.

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 kx 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:

i i3 223 i5 224

2 ... ...

3 ... ...

. . .

. . .

. . .

10 ... ...

Observa�ie. Radicalul r = mn 225 se calculeaz� prin rezolvarea ecua�iei nt = 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 n�N �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: 1 1 i i i-1 i i-1y = x , y = ( x div x ) * ( x + x ) , 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.

56

5.18. Trei numere întregi a, b, c, a < b < c se numesc pitagorice dac� 2 2 2c = a + b 228, iar dou� triplete ( a ,b ,c )1 1 1 229 �i ( a ,b ,c )2 2 2 230 sunt considerate a fi asemenea dac�

1

2

1

2

1

2

aa

= bb

= cc

231.

Se d� n�N �i mul�imea de numere întregi X = {xi�i=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 1 2 nA , A , ..., A 232 n mul�imi de numere. S� se scrie programul care determin� mul�imea: A = (...( A A ) A ) ... A ) A1 2 3 n-1 n∆ ∆ ∆ ∆ ∆ 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 < x < x < ... < x = b0 1 2 n 235 care are ca puncte capetele subintervalelor din I; b) S� se calculeze valorile i iv = f( x ) 236, unde f( x )i 237 este num�rul de subintervale din I în care se afl�

ix 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 =

x x . . . . . .

x x x . . . . .

. x x x . . . .

. . . . . . . .

. . . . . x x x

. . . . . . x x

1 n+1

2n 2 n+2

2n+1 3 n+3

3n-3 n-1 2n-1

3n-2 n

�

�

��

��

239.

S� se tip�reasc� în final A, A , ..., A .2 n 240 5.22. Se dau nN �i numerele 1 2 nx , x , ..., x 241. Se cere programul care genereaz� matricea de dimensiune mxk 242 care are pe liniile sale în ordine elemente din �irul: 1 2 n 1 2 nx , x , ..., x , x , x , ..., x , ... .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:

57

A =

x x . . . x

x x . . . x

. . . . . .

x x . . . x

1 2 m

m+1 m+2 2m

(m-1) m+1 (m-1) m+2 m2• •

�

�

��

��

245.

5.24. S� se scrie un program care rezolv� ecua�ia matriceal�: A X + B = C• 246, unde A,B,C ∈247 3x3M 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 n�N �i vectorii X, Y cu n componente numere reale. S� se calculeze valorile:

i i

i i

i i

i i

v = f( x ) =

g( x ), x < 0,

l( x ), x = 0,

h( y ), x > 0,

daca

daca

daca

�

�

�

�

��

��

249

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

{ }{ }

g( x ) = x , x , ... , x ,

h( y ) = y , ... , y ,

i 1 2 i

i i n

max

min250

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

| y |i 253. 5.27. Se dau m,n�N �i o matrice mxnA ( 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:

a) 3C - 7 C + 11C - ... + (-1 ) (4n - 1)C ;n1

n2

n3 n-1

nn 255

b) ( C )

0! +

( C )1!

+ ... + ( C )

n!n0 3

n1 3

nn 3

256.

5.29. S� se scrie un program pentru calculul sumei:

S = 1

a a ... a +

1a a ... a

+ ... + 1

a ... a,

1 2 k 2 3 k+1 n-k+1 n• • • • • • • •257

unde { } a n 258 e o progresie aritmetic� pentru care ra�ia �i primul termen se cer utilizatorului.

58

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

a) n2p

1p

3p

2p

n-1p

npS =

1 a - a

+ 1

a - a + ... +

1a - a

260

b) ′n1

2 1

2

3 2

n

n+1 nS =

aa - a

+ a

a - a + ... +

aa - a

261.

Observa�ie. Ra�ia �i primul termen al progresiei vor fi furnizate programului de c�tre utilizator. 5.31. Se dau n�N �i numerele reale 1 2 na < a < ... < a 262. S� se scrie programul care tip�re�te permutarea σ n∈ S 263 pentru care suma

ni=1

n

i (i)2S = ( a - a )� σ 264

este maxim�, respectiv minim�.

5.32. Fie f(X)= a X + a X +...+a X + a I ,0n

1n-1

n-1 n m• • • • 265 unde ia _ , i = 0,n,∈ 266 iar X,Im

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

k=1

n

2 2

k k

k k�

�

��

�

cos sin

cos sin

α α

α α269

5.34. Dac� 1 2x , x 270 sunt r�d�cinile reale ale ecua�iei de gradul doi (cu coeficien�i reali):

12

2 3a x + a x + a = 0• • 271, s� se scrie programul care calculeaz� suma:

S = x x x

x x x .

k=1

n 1k

22k

13k

23k

12k

2k

��

��

�� 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. 5.35. Se dau m,n�N. S� se scrie programul care genereaz� �i tip�re�te matricea A cu m linii �i n coloane definit� prin:

59

ij2 2a =

P(i + j), i + j < (m,n)

R( i , j ), (m,n) i + j (m,n)

Q(i + j), (m,n) < i + j

daca min

daca min maxdaca max

�

�

�

≤ ≤�

��

��

273

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� se scrie un program care determin� primele m numere naturale n ∈ Ν 274 cu proprietatea

cmmdc ( n, 2 - 1 ) > 1n 275. 5.37. S� se scrie un program care determin� cel mai mic num�r natural n ∈ Ν care are exact m divizori primi proprii.

5.38. Fie n ∈ Ν* 276 S� se scrie un program care calculeaz� suma:

S = md

(d)d|m� • ϕ 277

unde însumarea se face dup� divizorii naturali d ai lui m (inclusiv 1 �i m), iar ϕ 278 este indicatorul lui Euler,

ϕ(n) = 279 num�rul numerelor naturale mai mici decât n �i prime cu n, ∀ ∈ n Ν* 280 (cu conven�ia ϕ(1) = 1 281 ).

5.39. Fie m = k Ck=0

n

2nk� • 282 unde n�N, n 1. S� se scrie un program care

calculeaz� valoarea pe un punct x dat a func�iei:

f(x) = 1m

(k - x ) c .k=0

n2

2n2k• •� 283

5.40. Fie ( p , p , p ) ( p < p < p )1 2 3 1 2 3 284 un triplet format din numere prime aflate la acea�i distan��

unul fa�� de altul, adic� 3 2 2 1p - p = p - p = d > 0,285. S� se determine primele n triplete pentru care d este

multiplu de 2 ( n 10≤ 286). 5.41. Se dau m,n�N �i o matrice A�Mm,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 n�N �i func�ia

60

f(n) = C ( k + 1), n par

1k!

, n impar

k=0

n

nk 2

k=1

n

�

�

�

�

��

�

��

287

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.

61

63

CAPITOLUL 6 PROBLEME REZOLVATE CU MATRICE 6.1. RELA�II ÎNTRE PERSOANE Se dau n persoane �i matricea A�MPn(B2) unde

ija = 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; { n = num�rul persoanelor } { A = matrice p�trat� de ordinul n } REZULTATE k,P; {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; {n = num�rul persoanelor } {A = matrice p�trat� de ordinul n } 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. 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; {Programul 6.1.} { Rela�ia de cuno�tin�e intre persoane} Var n, { n = num�rul persoanelor } k, {k = nr. pers. care nu au nici o cuno�tin�a} i,j : byte; P : array[1..20] of byte; { P = vector cu k componente ce} {re�ine cele k persoane f�r� cuno�tin�e}

64

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; { CITIRE NR. PERSOANE } repeat write ('Da�i num�rul persoanelor:'); readln (n) until n in [1..20]; { 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; { n�N, n>1, reprezint� ordinul matricei } REZULTATE A; {A=matrice de ordinul n, care reprezint� } {p�tratul magic; deci suma elementelor pe } { fiecare linie, coloan� sau diagonal� este aceea�i }

65

Î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 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 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: { 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 } DATE n; { n�N, n>1, reprezint� ordinul matricei } Pentru i:=1,n execut� { ini�ializare matrice } Pentru j:=1,n execut� Fie a[i,j] := 0 sf-pentru sf-pentru Fie i:=1; j:=n div 2 +1; { fixare locul de pornire} a[i,j]:=1; Pentru k := 2,n*n execut� m1 := (i+n-2) mod n + 1; { calculul pozi�iei urm�toare} 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; { atribuire noua valoare } Fie i:=m1; j:= m2; { �i noua pozi�ie } sf-dac� sf-pentru REZULTATE A; sf-algoritm Programul Pascal echivalent este urm�torul: Program magic; { 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 } Uses Crt;

66

Var n, { nN, n>1, reprezint� ordinul matricei } m1, m2, { variabile curente pentru noua pozi�ie } i, j, { dau pozi�ia curenta in p�trat } k : integer; { valoarea ce se scrie in p�trat } a : array[1..19,1..19] of integer; { P�tratul magic } Begin Writeln('Se construie�te un p�trat magic cu n linii'); Repeat write ('n='); readln (n) { Cite�te 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; { ini�ializare matrice } i:= 1; j:= n div 2 + 1; { fixare locul de pornire} a[i,j]:=1; for k := 2 to n*n do begin m1 := (i+n-2) mod n + 1; { calculul pozi�iei urm�toare } 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; { atribuire noua valoare } i := m1; j := m2; end; { Tip�rirea rezultatului } ClrScr; for i := 1 to n do { tip�re�te linia i } 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. 6.3. PROBLEME PROPUSE 6.1. Se dau n localit��i. Într-o matrice A sunt marcate drumurile directe între localit��i astfel: ija = 1,289 dac� exist� drum direct între localit��ile i �i j;

ija = 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.

67

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

ija = 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� n 6, 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 i2a 293 este copilul lui i1a 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 n�N, 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} � M' �i o opera�ie � dat� prin matricea O, s� se verifice dac� H este parte stabil� în raport cu opera�ia �. 6.5.4. S� se verifice dac� opera�ia dat� este asociativ�. 6.5.5. S� se verifice dac� opera�ia admite element neutru la dreapta �i în caz afirmativ s� se precizeze acest element. 6.5.6. S� se verifice dac� opera�ia admite un element neutru la stânga �i în caz afirmativ s� se precizeze acest element. 6.5.7. S� se verifice dac� opera�ia admite un element neutru.

68

6.5.8. Se �tie c� opera�ia are ca element neutru pe k. Pentru un j�M, 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 j M, 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 ija = 1,295 dac� i este în rela�ie cu j (deci iRj),

ija = 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 = { a , a ,..., a }

B = { b , b ,..., b }1 2 m

1 2 n297.

O rela�ie R între A �i B poate fi reprezentat� printr-o matrice cu elementele:

iji j

r = 1 , a R b0 , .

daca

altfel

��

298

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).

69

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). 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 � R2 � ... � 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: ija = d,299 dac� exist� drum direct între i �i j �i d este distan�� între i �i j;

ija = 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 j, atunci not�m prin δ (i) = max { d(i, j)| j = 1,2, ..., n } 301 �i localitatea i se nume�te cea mai central� dac�

δ δ(i) = min { (j)| j = 1,2,..., n } 302 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: ija = 1, 303

dac� se poate circula dinspre i spre j, ija = 0, 304

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

70

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

71

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.

Date post:	13-Jun-2015
Category:	Documents
Upload:	egina
View:	3,804 times
Download:	6 times

67 de Pagini de Probleme Rezolvate Si Teorie in Pascal

Documents