Info Teorie

of 85 /85
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

description

teorie

Transcript of Info Teorie

  • 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. Numrul 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 mulimi ................................................................................................................. 51

    5.2. Numere prime ................................................................................................................................. 54

    5.3. Probleme propuse ........................................................................................................................... 55

    Capitolul 6.

    PROBLEME REZOLVATE CU MATRICE

    6.1. Relaii ntre persoane ...................................................................................................................... 63

    6.2. Ptrate magice ................................................................................................................................ 64

  • 6

    6.3. Probleme propuse ........................................................................................................................... 66

    Capitolul 7.

    PROGRAMARE N LIMBAJ DE ASAMBLARE

    7.1. Tiprirea valorii zecimale a unui numr ntreg .............................................................................. 73

    7.2. Tiprirea valorii hexazecimale a unui numr ................................................................................. 75

    7.3. Interclasarea a dou iruri .............................................................................................................. 76

    7.4. Manevrarea biilor .......................................................................................................................... 78

    7.5. Probleme propuse ........................................................................................................................... 79

    Capitolul 8.

    PROBLEME REZOLVATE FOLOSIND TIPUL MULIME SAU ENUMERARE

    8.1. Divizori comuni .............................................................................................................................. 89

    8.2. Ciurul lui Eratostene ....................................................................................................................... 92

    8.3. Statistica culorilor citite .................................................................................................................. 94

    8.4. Probleme propuse ........................................................................................................................... 95

    Capitolul 9.

    PROBLEME CU IRURI DE CARACTERE

    9.1. Poziia unui subir ntr-un ir ........................................................................................................ 99

    9.2. Afiarea cuvintelor care ncep cu majuscul ................................................................................. 100

    9.3. Probleme propuse ......................................................................................................................... 102

    Capitolul 10.

    PROCEDURI RECURSIVE

    10.1. Generarea permutrilor .............................................................................................................. 107

    10.2. Calculul combinrilor de m elemente luate cte k ..................................................................... 108

    10.3. Subprograme mutual recursive .................................................................................................. 109

    10.4. Probleme propuse ....................................................................................................................... 110

    Capitolul 11.

    PROBLEME CU FIIERE

    11.1. Construirea, actualizarea i listarea unui fiier ........................................................................... 113

    11.2. Probleme propuse ....................................................................................................................... 119

    Capitolul 12.

    PROBLEME CU LISTE

    12.1. Liste nlnuite ............................................................................................................................ 131

    12.2. List de articole .......................................................................................................................... 132

  • 7

    12.3. Arbore binar ............................................................................................................................... 135

    12.4. Probleme propuse ....................................................................................................................... 137

    Capitolul 13.

    GRAFIC

    13.1. Graficul funciei SIN (n mod text) ............................................................................................ 141

    13.2. Graficul funciei SIN (n mod grafic) ......................................................................................... 141

    13.3. Recursivitate n grafic ............................................................................................................... 142

    13.4. Probleme propuse ....................................................................................................................... 144

    Capitolul 14.

    PROBLEME DE CONCURS

    14.1. Plimbare pe ecran ....................................................................................................................... 153

    14.2. Probleme propuse ....................................................................................................................... 156

    Capitolul 15.

    TIPURI ABSTRACTE DE DATE

    15.1. Noiuni fundamentale ................................................................................................................. 163

    15.2. TAD enumerare n Pascal .......................................................................................................... 165

    15.3. TAD stiv n Pascal .................................................................................................................... 169

    15.4. Probleme propuse ....................................................................................................................... 175

    Capitolul 16.

    PROBLEME CU GRAFE

    16.1. Noiuni fundamentale i notaii folosite ..................................................................................... 191

    16.2. Tipul abstract de date GRAF ..................................................................................................... 194

    16.3. Preluarea reprezentrii geometrice de ctre calculator .............................................................. 208

    16.4. Probleme propuse pentru programare ........................................................................................ 219

    16.5. Probleme cu caracter teoretic ..................................................................................................... 222

    BIBLIOGRAFIE ......................................................................................................................... 227

  • 8

  • 9

    PREFA

    Culegerea de probleme de fa se dorete a fi un ghid io colecie de probleme pentru

    nvarea programrii. Diversitatea problemelor propuse i gradul diferit de dificultate fac culegerea

    util nu numai studenilor, ci i elevilor de liceu. Iniial ea a fost conceput ca ghid pentru lucrrile de

    laborator ale studenilor anilor nti i doi de la secia de Informatic a Facultii de Matematic i

    Informatic.

    Problemele sunt grupate n 16 capitole, n funcie de specificul i gradul lor de complexitate.

    Succesiunea capitolelor din culegere vizeaz o abordare gradual a problematicii, att din punctul de

    vedere al complexitii algoritmilor, specificai n limbaj Pseudocod, ct i al nvrii unui limbaj de

    programare, n particular limbajul Pascal. Fiecare capitol conine cel puin dou exemple de probleme

    rezolvate, pentru care sunt precizai att algoritmii de rezolvare, ct i programele surs Pascal.

    Intenia autorilor este de a sugera un anumit stil de rezolvare a problemelor cu calculatorul,

    acordndu-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 soluiilor putnd fi fcut i n alte limbaje de programare.

    Problemele de acelai tip sunt grupate n acelai capitol, iar un capitol acoper toat gama de

    probleme pentru tema abordat. Astfel, capitolul I conine probleme elementare, a cror rezolvare nu

    cere folosirea vectorilor sau a matricelor. Capitolul doi conine probleme referitoare la vectori, n timp

    ce capitolul trei conine probleme a cror rezolvare cere folosirea vectorilor. Capitolul patru conine

    probleme cu matrice. Capitolul cinci cere folosirea subalgoritmilor. Capitolul ase conine probleme a

    cror rezolvare cere folosirea matricelor. Urmeaz un capitol de exemple i probleme pentru

    programarea n limbaj main. Capitolul opt conine probleme referitoare la tipurile mulime i

    enumerare din Pascal. Capitolul nou conine probleme referitoare la iruri de caractere. Capitolul

    zece se refer la recursivitate. Urmeaz un capitol de probleme privind folosirea fiierelor. Capitolul

    12 conine probleme care cer folosirea tipului referin n Pascal. Urmtorul capitol conine probleme

    de grafic cu calculatorul. Capitolul 14 conine mai multe probleme date la diferite concursuri de

    programare. Tipurile abstracte de date sunt obiectul capitolului 15. n sfrit, ultimul capitol conine

    probleme despre grafe.

    Dei la selectarea problemelor au contribuit toi autorii, fiecare capitol a fost elaborat de unul

    sau doi autori, dup cum urmeaz:

    Cap.1 - Prof. S.Groze i Prof. M.Freniu;

    Cap.2 - Prof. M.Freniu;

    Cap.3 - Lect. Robu J. i Prof. M.Freniu;

    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;

  • 10

    Cap.12 - Lect. V.Prejmereanu;

    Cap.13 - Lect. V.Prejmereanu;

    Cap.14 - Asist. S.Motogna;

    Cap.15 -

    Cap.16 - Conf. T.Toadere.

    Eventualele erori nu se pot imputa numai celor de mai sus, toi autorii participnd la corectarea final

    a acestei culegeri.

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

    Contieni c exist posibiliti de mbuntire a coninutului prezentei lucrri, autorii

    mulumesc anticipat pe aceast cale tuturor celor care vor face observaii i propuneri de mbuntire,

    de care se va ine seama la o nou editare a culegerii de probleme.

  • 11

    CAPITOLUL 1

    PROBLEME SIMPLE

    1.1. GHID DE LUCRU

    Rezolvarea unei probleme cu ajutorul calculatorului presupune parcurgerea urmtoarelor

    faze:

    - precizarea complet a problemei de rezolvat;

    - proiectarea algoritmului de rezolvare a problemei;

    - programarea propriu-zis (implementarea);

    - testarea programului obinut;

    - exploatarea i ntreinerea programului.

    Aceste faze constituie ciclul de via al programului.

    De foarte multe ori, atunci cnd 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 discuii, uneori ntinse n timp, n urma crora se ajunge la

    un enun relativ complet i exact al problemei. ntruct problemele propuse sunt luate din domeniul

    matematicii sarcina noastr va fi mult mai uoar.

    Dup enunarea problemei urmeaz modelarea matematic i cutarea 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 urmrit. Modelarea matematic i alegerea unei metode de

    rezolvare se mbin aproape ntotdeauna cu conceperea algoritmului, fiind greu s se separe una de

    cealalt. Activitile de mai sus constituie ceea ce numim proiectarea programului.

    Pe toat durata proiectrii trebuie menionate n scris toate deciziile luate, ntruct este

    posibil ca ulterior s fie necesar o reproiectare i deci, s se revin asupra acestor decizii.

    Documentaia realizat este necesar n primul rnd pentru urmtoarea faz a ciclului de via al

    programului, implementarea. De asemenea, n faza de ntreinere 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 fcut nct s permit o ntreinere ct mai uoar. Faza urmtoare,

    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 cror 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 situaii la refacerea (parial sau

    integral) a activitilor anterioare. Sigur c este de dorit s nu se ajung la astfel de situaii i, dac

    proiectarea i implementarea au fost fcute corect, n faza de testare nu ar trebui s ntlnim erori.

    Urmtoarea faz din viaa programului const n exploatarea propriu-zis a acestuia, faz n

    care execuia se face cu date reale. Aceast activitate se ntinde n timp pe mai muli ani i cere

    adeseori schimbri n program, motiv pentru care este cunoscut sub numele de ntreinerea

  • 12

    programului. Este faza cea mai costisitoare i cea mai important din viaa unui produsul real. Toat

    activitatea de realizare a programului trebuie s in seama de acest fapt i programul s fie astfel

    conceput nct s se permit modificri n ceea ce face programul cu un numr minim de modificri n

    textul acestuia. Documentarea programului presupune elaborarea unor materiale scrise n care se

    precizeaz toate informaiile 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 atenia asupra logicii rezolvrii problemei i

    s uite de restriciile impuse de limbajul de programare i calculatorul folosit. n aceast faz este

    necesar o analiz atent a problemei n vederea gsirii unui algoritm corect proiectat.

    De asemenea, proiectarea algoritmului permite evitarea duplicrii unui grup de instruciuni n

    mai multe pri ale programului. Identificarea unui astfel de grup permite definirea lui ca un singur

    subalgoritm i folosirea acestui subalgoritm ori de cte ori este necesar.

    n descrierea unui algoritm deosebim urmtoarele activiti importante:

    - specificarea problemei;

    - descrierea metodei alese pentru rezolvarea problemei;

    - precizarea denumirilor i semnificaiilor variabilelor folosite;

    - descrierea algoritmului propriu-zis.

    Astfel, dac ni se cere s calculm radicalul de ordinul 2 din x, n partea de specificare a

    problemei vom meniona:

    Se d un numr real nenegativ, notat prin x.

    Se cere s gsim un alt numr pozitiv r astfel nct r2=x.

    Pentru un informatician este clar c un astfel de numr nu se poate gsi n general prin nici

    un procedeu finit. Este ns posibil s gsim o aproximare orict de bun a lui r. Deci specificarea

    fcut nu este corect, neputnd gsi un algoritm care s rezolve problema n forma enunat. Vom

    modifica aceast specificaie, cernd s se calculeze aproximativ r cu o eroare ce nu depete un

    numr real eps orict de mic.

    Specificaia problemei este:

    DATE eps,x;

    REZULTATE r; -

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

    Urmeaz s precizm metoda de rezolvare a problemei. Se tie c exist cel puin dou

    posibiliti de a calcula pe r:

    - ca limit a unui ir (definit printr-o relaie de recuren) convergent la r;

    - prin rezolvarea ecuaiei r2=x.

    Precizm c-l vom calcula pe r rezolvnd ecuaia r2=x. Dar i rezolvarea acestei ecuaii se poate face

    a,b] care conine rdcina r la intervalul [a',b'], care este

    jumtatea stng, sau jumtatea dreapt a intervalului [a,b], cea care conine rdcina.

    Variabilele folosite n descrierea algoritmului sunt:

  • 13

    - a i b = capetele intervalului n care se afl rdcina;

    - m mijlocul intervalului (a,b). n momentul n care b-a

  • 14

    a,b, {capetele intervalului ce conine 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

  • 15

    Sf-pentru

    Sf-pentru

    Sf-pentru

    Sf-dac

    Sf-algoritm.

    Programul Pascal corespunztor este dat n continuare.

    PROGRAM NRPITAGORICE; {Programul 1.1.2. Numere pitagorice}

    VAR n,

    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 tipresc tripletele(a,b,c) de numere pitagorice');

    WRITELN('cu proprietatea: a+b+c

  • 16

    1.3. S se verifice dac numrul este perfect. (Un numr n este perfect dac este egal

    cu suma divizorilor lui diferii 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 numrului x este egal

    cu suma divizorilor numrului y. S se gseasc numerele "prietene" din intervalul [a,b].

    1.6. S se calculeze i s se tipreasc primii n termeni din irul Fibonacci, ir definit de

    relaia de recuren

    i+1 i i-1t = t + t 2, i=1,2,...

    avnd 0 1t = t =13.

    1.7. Fie + , . S se scrie un algoritm pentru calculul numrului combinrilor de n

    elemente luate cte k.

    1.8. Fie . S se scrie un algoritm pentru calculul mediei aritmetice, geometrice i

    armonice a tuturor divizorilor lui a.

    1.9. Fie funcia lui Euler , unde este numrul numerelor relativ prime cu n i

    mai mici ca n. S se tipreasc valorile =1,2,...,m, pentru dat.

    1.10. Fie . 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 . 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 cta zi din acel an este aceast

    zi.

    1.14. Se consider ( z ,l ,a )n n n 7 data naterii unei persoane i ( z ,l ,a )c c c 8 o dat

    curent. S se determine vrsta, n zile, a persoanei respective.

    1.15. Se dau datele de natere ( 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 tnr, prin indicatorul r

    vrst, 1 dac prima persoan este mai tnr).

  • 17

    1.16. Cunoscnd n ce zi din sptmn a fost 1 ianuarie, s se scrie un algoritm ce determin

    ziua din sptmn n care este a n-a zi a anului.

    1.17. rime pentru toate

    permutrile cifrelor lor. Ex. 13 i 31; 131,113 i 311, etc.). S se scrie un algoritm care determin

    numerele prime "permutabile", mai mici dect un numr m dat.

    1.18. O formul de generare a unui ir de numere (yi) este

    n2y = n - 79n + 160110.

    Se cere algoritmul care determin pentru un numr n 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.

    1.20. Fiind date numerele , se cere un algoritm care s stabileasc cea mai mare

    dintre fraciile a/b i c/d.

    1.21. S se gseasc soluiile ntregi i pozitive ale ecuaiei ax + by = c, cu proprietatea

    x+y0.

    1.22. Se cere valoarea funciei f:[- x, dac

    f x

    x

    -x -

  • 18

    unde d = (a,b) este cel mai mare divizor comun al numerelor a i b, iar p este probabilitatea ca un

    numr ce verific condiia , luat la ntmplare, s fie prim.

    1.26. Se cere un algoritm pentru determinarea numerelor impare succesive a cror sum este

    egal cu n3, pentru n=1,...,20. (Ex. 3 3 3

    1 =1, 2 = 3+5, 3 =7 +9+11 14, etc).

    1.27. S se scrie un algoritm care citete succesiv p perechi de numere ntregi (m,n

    m n i care calculeaz, pentru fiecare pereche coeficientul binomial bn,m definit de relaia recursiv

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

    b = 1, m= 0 m= n,

    b + b , .

    daca sau

    in caz contrar

    15

    1.28. S se afle toate punctele de coordonate ntregi situate n interiorul ptratului cu

    diagonala determinat de punctele A(a,b) i C(c,d).

    1.29. Fie . S se scrie un algoritm pentru calculul numrului punctelor de coordonate

    ntregi interioare elipsei de ecuaie

    2

    2

    2

    2

    x

    a+

    y

    b = 1 16

    1.30. Fie dreapta d determinat de punctele A(a1,a2) i B(b1,b2). S se determine poziia

    punctelor A i B fa de dreapta d, prin indicatorul R definit astfel:

    R=0, dac punctele A(a1,a2) i B(b1,b2) se afl n acelai semiplan determinat de dreapta d ;

    R=1, dac punctele A i B aparin 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 vrfurilor sale i un punct M n planul su. S se

    determine poziia punctului M fa de laturile triunghiului, marcndu-se cu R

    posibile: interior triunghiului, pe una din laturi, exterior triunghiului.

    1.32. Se d un ptrat P1 de latur 1 cruia i se circumscrie un cerc C1. Cercului obinut i se

    circumscrie un nou ptrat P2, acestuia un nou cerc C2, etc. S se calculeze aria ptratului Pn i aria

    cercului Cn obinute dup un numr de n pai, 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, . S se determine poziia dreptelor

  • 19

    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 extremitile 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

    intersecie a segmentelor date. n cazul n care acest punct nu exist, se va tipri un mesaj.

    1.37. O fabric de mobil primete comenzi pentru producerea unei diversiti de biblioteci,

    avnd:

    - lungimea cuprins ntre 2-9 m;

    - nlimea cuprins ntre 1-3 m;

    - un numr 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. Construcia unei biblioteci trebuie s respecte anumite condiii impuse de normele de

    fabricaie:

    - lungimea trebuie s fie de 2-3 ori mai mare dect nlimea;

    - limea trebuie s fie 1/3 pn la 1/2 din nlime;

    - numrul de corpuri trebuie s fie n raportul de 1/2 pn la 1 fa de produsul dintre lungime i

    nlime. Se cere algoritmul de acceptare al unei comenzi i de calcul al preului.

    1.38. Fie funcia f:[a,b

    f(x)=

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

    ax + bx

    x + 2 , (a + b) / 2 < x b

    2

    2

    daca

    daca

    18

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

    1.39. Se cere un algoritm pentru calculul aproximativ al rdcinii unei ecuaii f(x)=0, unde

    f:(a,b

    dedus, s se calculeze Mn 19. Indicaie. Se va lua f(x) = xn - M, iar intervalul (a,b), se nlocuiete cu [0,M].

    1.40. Dintr-o urn cu m bile (m>1), numerotate de la 1 la m, se extrage la ntmplare o bil.

  • 20

    S se scrie un algoritm pentru calculul probabilitii ca numrul nscris pe bila extras s fie prim.

    1.41. Un mobil efectueaz o micare oscilatorie armonic. tiind c pentru elongaiile x1=2

    cm i x2=3 cm, mobilul are vitezele v1=5m/s i respectiv v2=4m/s, s se calculeze amplitudinea i

    perioada micrii oscilatorii a mobilului.

    Indicaie. Se tie c PI=3.14 i se ine seama c amplitudinea, respectiv perioada micrii

    oscilatorie a mobilului sunt date de

    A=x v - x v

    v - v ; T = 2PI

    x - x

    v - 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 vrfurile 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 nct distana 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 ecuaie y=x2+1 determin o mprire a planului n opt

    regiuni interioare. S se determine dac punctele C i D se afl n aceeai regiune sau nu.

    1.46. Se dau n a numr de an al secolului nostru. S se precizeze data

    corespunztoare celei de a n-a zi a anului a sub forma (lun, zi).

    1.47. Se d numrul . S se tipreasc acest numr n sistemul de numeraie roman.

    1.48. tiind c 1 ianuarie 1994 a fost ntr-o zi de smbt, s se determine n ce zi a

    sptmnii va fi 1 ianuarie 2020.

    1.49. Se consider trei rezervoare cilindrice care conin benzin de trei caliti. Se cere

    situaia livrrilor sptmnale, livrrile zilnice nregistrndu-se secvenial. S se precizeze beneficiarul

    cruia i s-a livrat cantitatea maxim de benzin.

  • 21

  • 23

    CAPITOLUL 2

    PROBLEME CU IRURI DE NUMERE

    2.1. NUMERE DISTINCTE

    Se dau n x1,x2, ...,xn. Se cere s se rein ntr-un vector Y toate

    numerele, dar fr a repeta vreunul, deci Y are numai componente distincte.

    Specificarea problemei:

    DATE n, (xi, i=1,n); { xi

    REZULTATE (yj, j=1,k); { X=Y, unde X este }

    { mulimea ce conine toate numerele xi, i=1,n, }

    { iar Y =mulimea ce conine pe yj, j=1,k i yl j

    Variabilele intermediare folosite i semnificaia lor, precum i metoda folosit vor fi

    rezultatul rafinrilor succesive i vor fi nelese 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

    propoziiei 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 aparine lui Y.

    *Dac nu aparine atunci adaug pe xi la Y.

    SF-PENTRU

    REZULTATE (yj, j=1,k);

    SF-ALGORITM

    Decizia ce trebuie luat este cum s verificm apartenena unui element u la mulimea Y.

    Pentru aceasta vom reine n indicatorul ind cele dou situaii posibile: 0 pentru apartenen i pozitiv

  • 24

    n caz contrar. Acest calcul se poate face folosind urmtoarele propoziii:

    ind:=1;

    DAC xi=yind ATUNCI ind:=0

    ALTFEL ind:=ind+1

    SF-DAC

    SF-

    Cu acestea ajungem la versiunea final a algoritmului dorit.

    ALGORITMUL DISTINCTE ESTE: { Versiunea final }

    DATE n, (xi, i=1,n); { xi

    FIE y1:=x1; k:=1;

    PENTRU i:=2,n EXECUT

    {Verific dac xi aparine lui Y}

    ind:=1;

    DAC xi=yind ATUNCI ind:=0

    ALTFEL ind:=ind+1

    SF-DAC

    SF-

    {Dac nu aparine 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 mulimea ce conine }

    { toate numerele xi, i=1,n, iar Y este mulimea }

    { ce conine pe yj, j=1,k i yl j

    SF-ALGORITM

    Programul Pascal corespunztor este:

    PROGRAM DISTINCTE; { Programul 2.1. Retine valorile distincte }

    VAR n, { numrul numerelor date }

    i,j, { contor - variabile de lucru }

    k, { numrul valorilor distincte gsite }

    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');

  • 25

    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] aparine lui Y }

    While (ind>0) and (ind0 then { atunci adaug pe x[i] la Y }

    begin k:=k+1; y[k]:=x[i] end;

    end;

    Writeln; { Tiprete rezultatele }

    Writeln(' Numerele distincte sunt');

    For j:=1 to k do write(y[j]:5);

    readln

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

    obinut din irul numerelor naturale prin nlocuirea fiecrui numr natural n printr-un grup de numere,

    dup urmtoarele reguli: numrul prim p este nlocuit prin numerele p,p-1,...3,2,1, iar numrul compus

    c este nlocuit prin c urmat de toi divizorii si proprii, un divizor d repetndu-se de d ori. Dndu-se

    numrul natural n, se cere s se tipreasc primele n numere din irul dat.

    Specificarea problemei.

    Se d un numr natural n i irul de numere naturale descris mai sus.

    Se cere tiprirea primelor n numere din irul dat.

    Aparent problema este complet specificat, ceea ce nu e complet adevrat. Ne dm seama de

    acest lucru dac ncercm s precizm ce rezultate se vor reine n memoria calculatorului. Este

    posibil ca n memorie s reinem toate numerele cerute ntr-un vector X sub forma

    Y =( y , y ,..., y )1 2 n 21, sau s nu le reinem n memorie ci doar s le afim pe ecran. De fapt

    exist o variant simplificat a problemei de mai sus n care se cere s se obin doar al n-lea numr

  • 26

    din irul dat.

    Specificarea problemei, pentru tiprirea celor n numere, fr reinerea lor n memorie.

    DATE n;

    REZULTATE afiarea primelor n numere din irul menionat.

    Pentru a concepe un algoritm de rezolvare, n ambele variante se parcurge irul dat, reinnd sub

    numele t termenul curent al irului, iar sub numele i poziia acestui termen n vector. Prin k vom nota

    numrul natural din care se obine grupul de termeni din care face parte t, iar prin j indicele lui t n

    acest grup. Indicatorul ind va primi valoarea 1 dac numrul k este prim i 0 n caz contrar.

    Algoritmul pentru rezolvarea problemei este dat n continuare.

    Algoritmul GENERARE1 este: { varianta1 }

    DATE n;

    Fie i:=1;

    t:=1; tiprete t;

    k:=2;

    ind:=1; { Pentru cazul k este prim }

    Cttimp i

  • 27

    Dac ind=1

    i:=i+1;

    Tiprete t; t:=t-1

    sf-ct timp

    altfel d:=2; i:=i+1; Tiprete k;

    Ct timp d

  • 28

    While i 1. S se formeze vectorul ale crui componente sunt primele

    m numere din irul lui Fibonacci, definit prin n1=n2=1 i nk+1=nk+nk-1 pentru k=2,3,... .

  • 29

    2.5. Se d numrul natural n > 1. S se tipreasc triunghiul lui Pascal, avnd n linia m toate

    combinrile C(m,k) de m obiecte luate cte k, k=0,m, pentru m=1,2,...,n. Se va folosi relaia 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 +. S se determine numrul n al cifrelor i cele n cifre din scrierea

    numrului ntreg mk = (c1c2c3...cn)10.

    2.7. Se dau numrul natural n > 1 i n. S se determine indicele componentei minime

    i indicele componentei maxime din X.

    2.8. Se dau numrul natural n > 1 i numerele x1, x2, ..., xn. S se gseasc toate poziiile

    1 2 kp , p ,..., p 24 pe care se afl valoarea maxim.

    2.9. Se dau numrul natural n > 1 i numerele x1, x2, ..., xn. S se verifice dac numerele date

    sunt n progresie aritmetic sau geometric, calculnd 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 numrul natural n > 1 i numerele x1, x2, ..., xn. S se gseasc media numerelor

    date, numrul valorilor pozitive, produsul valorilor negative i s se tipreasc numerele mai mari

    dect 100.

    2.11. Se dau numrul natural n > 1 i numerele x1, x2, ..., xn. S se ordoneze cresctor primele

    k numere i descresctor celelalte numere, pentru k dat, k n}.

    2.12. Se dau numrul natural n > 1 i numerele x1, x2, ..., xn. S se gseasc toate numerele

    distincte 1 2 my , y ,..., y 25 din irul X precum i frecvenele acestor numere ntre numerele date.

    2.13. Se dau numrul 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 numrul natural n > 1 i numerele x1, x2, ..., xn. S se determine cel mai mare

    numr negativ i poziiile pe care se afl el n irul dat.

    2.15. Se dau numrul 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

  • 30

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

    2.16. Se dau numrul 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 numrul 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 numrul componentelor vectorului X egale cu xi, pentru i=1,2,...,n.

    2.18. Se dau numrul natural n > 1 i numerele x1, x2,..., xn. S se calculeze componentele

    vectorului 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 numrul 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 numrul natural n > 1 i numerele x1, x2,..., xn. S se determine numrul 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 numr negativ, dac exist numere pozitive, respectiv 0 n

    caz contrar.

    2.21. Se dau numrul natural n > 1 i numerele x1, x2,..., xn. S se rein toate numerele

    distincte y1,y2,...,yk i s se calculeze frecvenele de apariie ale acestor numere n irul dat.

    2.22. Se dau numrul natural n > 1 i numerele x1, x2,..., xn. S se determine vectorul

    Y=(y1,y2,...,yn), unde yi este egal cu numrul valorilor din irul dat mai mari dect xi, pentru i=1,n.

    2.23. Se dau numrul natural n > 1 i numerele x1, x2,..., xn. Dac yi este numrul termenilor

    mulimii {xj j

  • 31

    2.25. Se dau numrul 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 nelege media aritmetic a puterilor

    de exponent j ale numerelor date.

    2.26. Se dau numrul 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 numrul

    elementelor mulimii { x | m - k* s < x < m + k* s}i 1 i 1 29.

    2.27. Se dau numrul natural n > 1 i numerele x1, x2,..., xn. Secvena xi, xi+1,..., xi+p se

    numete scar (de lungime p) dac xi

  • 32

    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 numerele reale a, b, a

  • 33

    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

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

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

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

    i s se determine elementele mulimii { i | x * x > E}i i 60.

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

    2.47.

    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 mulimii { x | 3(s3 - s2* s2) > |x - s2|}i i 63.

    2.47. Se dau 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

  • 34

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

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

    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

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

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

    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 rein poziiile

    1 2 ki , i , ... , i 71, pe care cei doi vectori coincid. S se elimine din vectorii X i Y termenii de pe aceste poziii.

    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 poziia componentei maxime a vectorului

    ( x ,x ,...,x , y , y ,..., y )1 2 i i i+1 n 75 (dac exist mai multe, poziia primei valori maxime).

    2.52. Se dau i n. S se determine poziiile i0 i j0 cu urmtoarea proprietate:

    exist m componente consecutive din cei doi vectori, ncepnd cu poziiile i0, respectiv j0, care

    coincid i m este cel mai mare posibil. n cazul n care nu exist poziii 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

  • 35

    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

  • 36

    2.59. Se dau 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 puin o valoare ia 94 nu este corect,

    kod = -1, dac cel puin 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 i cifrele zecimale ia ,96 i=1,2,...,m i jb ,97 j=1,2,...,n. Dac

    numerele reale A i B au reprezentrile 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 r1. Dac X este irul:

    1, 1, 2, 1, 2, 3, 1, 2, 3, 4, ...

    obinut din irul numerelor naturale prin nlocuirea fiecrui numr natural k cu secvena 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>1. Dac X este irul:

    3, 5, 5, 7, 11, 13, 17, 19, ...

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

    2.63. Se d 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, ...

    obinut prin scrierea consecutiv a tuturor tripletelor de numere pitagorice p, q, r, p1. 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:

  • 37

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

    obinut din irul numerelor naturale prin nlocuirea fiecrui numr natural prim p prin secvena

    1,2,...,p i a numrului neprim c prin scrierea lui de c ori, ncepnd cu mx 108 (fr a reine termenii

    ix 109 n calculator).

    2.66. Se dau 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, ...

    obinut din irul numerelor naturale prin nlocuirea fiecrui numr prim p cu un grup de p numere

    toate egale cu p, ncepnd cu mx 111 (fr a reine termenii ix 112 n calculator).

    2.67. Se dau 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, ...

    obinut prin scrierea numerelor naturale i a divizorilor proprii ai acestor numere, ultimul divizor d

    repetndu-se de d ori, ncepnd cu mx 114 (fr a reine termenii ix 115 n calculator).

    2.68. Se dau 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, ...

    obinut prin scrierea numerelor naturale i nlocuirea fiecrui numr compus prin toi divizorii si

    proprii, ncepnd cu mx 117 (fr a reine termenii ix 118 n calculator).

    2.69. Se dau i seria

    n=1

    1

    3n - 2

    1

    3n -1

    1

    3n .

    119

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

    sunt sume pariale 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-1

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

    4

    2n -1

    1

    2+

    1

    3

    123

    S se construiasc vectorul V =( v ,v ,...,v )1 2 n 124 tiind c cele n componente ale vectorului V

    sunt sume pariale ale acestei serii, 1 20 i 20+5iv = s , v = s ,125 i=2,3,...,n, unde ks 126 este suma primilor k termeni.

  • 38

    2.71. Se dau n

    33

    2 (1+

    1

    6+

    1* 2

    6* 10+

    1* 2* 3

    6* 10* 14+... ) 127

    S se construiasc vectorul V =( v ,v ,...,v )1 2 n 128 tiind c cele n componente ale vectorului V

    sunt sume pariale ale 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 cunoate seria

    2 1+1

    3+

    1* 2

    3* 5+

    1* 2* 3

    3* 5* 7+...

    131

    S se construiasc vectorul V =( v ,v ,...,v )1 2 n 132 tiind c cele n componente ale vectorului V

    sunt sume pariale ale 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 cunoate seria

    i 2 3u = 1+1

    3 1

    9+

    1

    5

    1

    9+

    1

    7

    1

    9+...135

    S se construiasc vectorul V =( v ,v ,...,v )1 2 n 136 tiind c cele n componente ale vectorului V

    sunt sume pariale ale 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 i se cunoate seria

    1+1

    3* 3+

    1* 2

    3* 5* 5+

    1* 2* 3

    3* 5* 7* 7+

    1* 2* 3* 4

    3* 5* 7* 9* 9+...139

    S se construiasc vectorul V =( v ,v ,...,v )1 2 n 140 tiind c cele n componente ale vectorului V

    sunt sume pariale ale 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 unoate seria

  • 39

    1+1

    3* 3+

    1* 2

    3* 5* 5+

    1* 2* 3

    3* 5* 7* 7+

    1* 2* 3* 4

    3* 5* 7* 9* 9+...143

    S se construiasc vectorul V =( v ,v ,...,v )1 2 n 144 tiind c cele n componente ale vectorului V

    sunt sume pariale ale 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 cunoate seria convergent din problema 2.69. S se determine suma parial sn a

    primilor n termeni pentru care

    |s - s | < n n-1 147 n fiind cel mai mic numr natural posibil.

    2.77. Se cunoate seria convergent din problema 2.70. S se determine suma parial sn a

    primilor n termeni pentru care

    |s - s | < n n-1 148 n fiind cel mai mic numr natural posibil.

    2.78. Se cunoate seria convergent din problema 2.71. S se determine suma parial sn a

    primilor n termeni pentru care

    |s - s | < n n-1 149 n fiind cel mai mic numr natural posibil.

    2.79. Se cunoate seria convergent din problema 2.72. S se determine suma parial sn a

    primilor n termeni pentru care

    |s - s | < n n-1 150 pent n fiind cel mai mic numr natural posibil.

    2.80. Se cunoate seria convergent din problema 2.73. S se determine suma parial sn a

    primilor n termeni pentru care

    |s - s | < n n-1 151 n fiind cel mai mic numr natural posibil.

    2.81. Se cunoate seria convergent din problema 2.74. S se determine suma parial sn a

    primilor n termeni pentru care

    |s - s | < n n-1 152 n fiind cel mai mic numr natural posibil.

    2.82. Se cunoate seria convergent din problema 2.75. S se determine suma parial sn a

    primilor n termeni pentru care

    |s - s | < n n-1 153 n fiind cel mai mic numr natural posibil.

  • 40

    2.83. S se tipreasc primii n termeni ai irului (xk) definit de relaia de recuren

    k k-1 k-1x = ( x + a / x ) / 2,154 pentru a i x0 numere reale date, pentru care

    |x - x |

  • 41

    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] -- f(x) = 0 are o singur rdcin 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 obine mprind intervalul [ x , y ]i-1 i-1 170 n trei pri egale

    i lund partea care conine rdcina;

    3. n este cel mai mic numr natural pentru care n ny - x 171

  • 42

  • 43

    CAPITOLUL 3

    PROBLEME REZOLVATE CU AJUTORUL

    VECTORILOR

    3.1. NUMRUL PUNCTELOR DIN CERC

    Se dau n puncte n plan i un cerc. Se cere numrul punctelor care se afl n interiorul

    cercului.

    Rezolvare

    Punctele se dau prin coordonatele (xi,yi), i=1,2,...,n. Variabila nr va conine numrul

    punctelor din interiorul cercului, care se d prin centrul O(a,b) i raza r.

    Deci specificarea problemei este:

    DATE n, { numrul punctelor date }

    (xi,yi, i=1,n), { coordonatele celor n puncte }

    a,b, { coordonatele centrului cercului }

    r; { raza cercului dat }

    REZULTATE nr; { numrul punctelor aflate n interiorul cercului }

    Pentru a calcula valoarea lui nr se iniializeaz cu 0 acest numr i se verific care dintre

    punctele (xi,yi) au distana fa de (a,b) mai mic dect r, deci se afl n cerc. Pentru fiecare rspuns

    afirmativ valoarea lui nr se mrete cu 1.

    Algoritmul pentru rezolvarea problemei este dat n continuare.

    Algoritmul PUNCTE_IN_CERC este :

    DATE n, { numrul 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; { numrul punctelor aflate n interiorul cercului }

  • 44

    sf-algoritm.

    Programul PASCAL este dat n continuare.

    Program Nr_Puncte_n_cerc; {Programul 3.1 Nr. puncte ntr-un cerc}

    var n, { numrul punctelor date }

    i, { variabila de lucru - contor }

    nr : integer; { numrul punctelor aflate in cerc }

    a,b, { coordonatele centrului cercului }

    r : real; { raza cercului dat }

    x, { x[i] = abscisa iar }

    y:array [1..50] of real; { y[i] = ordonata punctului "i" }

    begin

    clrscr;

    writeln('Programul numr cte 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)

  • 45

    Se dau i vectorii X,Y de componente numere ntregi, ordonate nedescresctor.

    Formai vectorul Z de dimensiune m+n, avnd drept componente toate componentele vectorilor X i

    Y, de asemenea ordonate nedescresctor.

    Rezolvare

    Specificarea problemei este:

    DATE m, { numrul componentelor lui X }

    n, { numrul componentelor lui Y }

    (xi,i=1,m), {componentele vectorului X: x1 2 m}

    (yi,i=1,n); {componentele vectorului Y: y1 2 n}

    REZULTATE k, { numrul componentelor lui Z: k=m+n }

    (zi, i=1,k), { componentele vectorului Z. Ele sunt toate }

    { componentele din X i Y. Avem z1 2 k }

    Pentru a forma vectorul Z observm mai nti c z1 este cel mai mic dintre x1 i y1. Ct timp

    mai sunt componente i n X i n Y urmtorul z va fi cel mai mic dintre xi i yj, i, respectiv j, fiind

    poziiile n cei doi vectori pn la care componentele au fost deja depuse n Z. Evident se va ncepe cu

    i=1 i j=1, iar k - poziia curent n vectorul Z va fi iniial tot 1.

    Algoritmul pentru rezolvarea problemei este dat n continuare:

    Algoritmul INTERCLASARE este : { Z := X interclasat cu Y }

    Date m, { numrul componentelor lui X }

    n, { numrul componentelor lui Y }

    (xi,i=1,m), {componentele vectorului X. Avem x1 2 m }

    (yi,i=1,n), {componentele vectorului Y. Avem y1 2 n }

    Fie i:=1; j:=1; k:=0;

    Dac xi

  • 46

    sf-algoritm

    Programul PASCAL este dat n continuare.

    PROGRAM INTERCLASARE; { Programul 3.2. Interclasarea }

    { componentelor vectorilor X si Y }

    VAR m, { numrul componentelor lui X }

    n, { numrul componentelor lui Y }

    i,j, { contori in X, respectiv Y }

    k: integer; { numrul valorilor gsite 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

  • 47

    3.3. PROBLEME PROPUSE

    3.1. Se d un polinom P(X) cu coeficieni reali. S se calculeze valoarea polinomului P(X)

    ntr-un punct x0 dat.

    3.2. Se d un polinom P(X) cu coeficieni reali. S se verifice dac un numr dat r este

    rdcina acestui polinom.

    3.3. Se d un polinom P(X) cu coeficieni reali. S se calculeze derivata acestui polinom.

    3.4. Se d un polinom P(X) cu coeficieni reali. S se calculeze derivata de ordinul k a

    polinomului dat.

    3.5. Se d un polinom de gradul n cu coeficieni ntregi. S se gseasc rdcinile ntregi ale

    polinomului dat.

    3.6. Se d un polinom de gradul n cu coeficieni ntregi. S se gseasc rdcinile raionale

    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 i mulimile

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

    B = {b , b ,..., b }

    1 2 m

    1 2 n

    173

    S se calculeze C = A B.

    3.11. Se dau i mulimile

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

    B = {b , b ,..., b }

    1 2 m

    1 2 n

    174

    S se calculeze C = A B.

    3.12. Se dau i mulimile

  • 48

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

    B = {b , b ,..., b }

    1 2 m

    1 2 n

    175

    S se calculeze C = A - B.

    3.13. Se dau dou numere scrise n baza b. S se calculeze suma i diferena 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 gseasc ctul i restul mpririi primului

    numr la al doilea numr.

    3.16. S se transforme un numr din baza p n baza q.

    3.17. Se d o mulime M de n puncte n plan. S se gseasc punctul cel mai deprtat de

    origine.

    3.18. Se d o mulime M de n puncte n plan. S se ordoneze n funcie de distana lor fa de

    axa OX.

    3.19. Se d o mulime M de n puncte n plan. S se ordoneze n funcie de distana lor la

    originea axelor de coordonate.

    3.20. Se d o mulime M de n puncte n plan. S se gseasc triunghiul de arie minim care

    are vrfurile n M.

    3.21. Se d o mulime M de n puncte n plan. S se gseasc numrul triunghiurilor care au

    vrfurile n mulimea M.

    3.22. Se d o mulime M de n puncte n plan. S se determine submulimea maxim de

    puncte coliniare.

    3.23. Se d o mulime M de n puncte n plan. S se determine submulimea 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 gseasc 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 gseasc cte puncte sunt la o

    distan de punctul M mai mic dect un numr real r dat.

  • 49

    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 vrfurilor unui poligon convex, n ordinea lor. S se gseasc

    diagonala cea mai lung.

    3.31. Se dau n puncte n plan i ecuaia unei drepte. S se numere cte puncte se afl pe

    dreapt i s se afle punctul de distan maxim fa de dreapt.

    3.32. Se dau n cercuri concentrice. S se gseasc 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 funcie 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 funcia f, dat prin vectorul F

    este injectiv.

    3.35. Se d o funcie f : {1,2,...,m} ---> {1,2,...,n} reprezentat aa cum se menioneaz n

    problema 3.34. S se verifice dac funcia f, dat prin vectorul F este surjectiv.

    3.36. Se dau funciile f:{1,2,...,m} --->{1,2,...,n} i g:{1,2,...,n}---> {1,2,...,p}, reprezentate

    aa cum se menioneaz n problema 3.34. S se determine compunerea celor dou funcii date.

    3.37. O aplicaie f : {1,2,...,n} ---> {1,2,...,n} bijectiv se numete permutare. Ea se poate

    reprezenta n calculator aa cum s-a artat n problema 3.34. Se d o permutare f. S se determine

    numrul inversiunilor permutrii f.

    3.38. Se d o permutare f aa cum s-a artat n problema 3.37. S se determine ordinul

    permutrii date. Prin ordinul permutrii f se nelege cel mai mic ntreg k pentru care fk este aplicaia

    identic.

    3.39. Se d o permutare f aa cum s-a artat n problema 3.37. S se calculeze inversa

    permutrii f.

    3.40. Se dau dou permutri f i g aa cum s-a artat n problema 3.37. S se determine

  • 50

    compunerea celor dou permutri date.

    3.41. La un concurs de patinaj artistic se cunosc cele n note obinute 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 obinut (o singur dat n cazul c sunt dou note egale, deci se face media aritmetic a n-2

    note).

    3.42. Pentru cei n studeni ai anului nti se cunosc notele mi, i=1,n, la primul examen. Se

    cere s se determine numrul studenilor cu nota 10, numrul studenilor cu note de 8 i 9 i s se

    tipreasc lista studenilor nepromovai.

    3.43. Pentru cele 365 de zile ale unui an se cunosc cantitile de precipitaii zilnice pi,

    i=1,365. Se cere s se determine numrul zilelor fr precipitaii, mediile lunare i media anual a

    precipitaiilor i s se listeze zilele cu precipitaii ce depesc cantitatea a.

    3.44. Se dau intervalele [ai-1,ai], i = 1,m i numerele reale x1,x2, ... , xn. Prin

    frecvena fi se nelege numrul valorilor xj care se afl n intervalul [ai-1,ai]. S se determine

    frecvenele f1,f2,... ,fm i s se listeze indicii j pentru care xj

  • 51

    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 folosete un tablou

    unidimensional pentru irul X i un tablou bidimensional pentru matricea A. Deci specificarea

    problemei este:

    DATE m, {numrul liniilor matricei A}

    n, (numrul coloanelor matricei A}

    X; {vector ce conine cele m*n numere date}

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

    Deoarece n expresia ce definete 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)

  • 52

    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 corespunztor este urmtorul:

    Program matrice; { Programul 4.1. Construirea unei matrice A }

    Type sir=array[1..100] of real;

    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 conine o suma}

    begin

    Writeln('Se calculeaz o matrice A de dimensiune m*n');

    writeln('dandu-se un vector X cu m*n componente');

    write(' Dai numrul liniilor matricei : '); readln(m);

    write(' Dati numrul coloanelor matricei: '); readln(n);

    writeln(' Dai 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

  • 53

    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 nct elementele matricei s fie elementele irului n urmtoarea ordine:

    (considerm 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, {numrul 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 urmtoarea 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 ncepnd cu prima linie i pn la linia a m-a, iar dac

    valoarea lui kod este 1 atunci pe acea coloan elementele irului se pun ncepnd cu linia a m-a i pn

    la prima linie.

    Variabile folosite:

    X - vector ce conine numerele date, de lungime k;

    A - matricea cerut;

    m,n - dimensiunile matricei;

    l - indice n ir;

    kod - variabila de control.

    Algoritmul corespunztor este dat n continuare.

    Algoritmul MATRICE2 este:

    DATE m,n, {dau dimensiunea matricei}

    k, {numrul componentelor irului X}

    X; {vector de dimensiune k}

    Dac m*n>k

    atunci Tiprete('Prea puine 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

    pn cnd j>n sf-repet

  • 54

    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, {numr natural dat}

    l, {indice n ir}

    kod : integer; {variabila de control}

    X : sir; {vector ce conine numerele date, de lungime k}

    A : mat; {matricea cerut}

    Begin

    Writeln{'Se constuiete o matrice dintr-un ir de numere');

    write('Dai dimensiunile matricei:'); readln(m,n);

    write('Dai dimensiunea irului:'); readln(k);

    { Dac elementele irului nu }

    if m*n > k { "umplu" matricea se }

    then write('Prea puine 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}

    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 cnd s-a completat coloana n}

    for i:= 1 to m do { tiprete linia i a matricei }

    begin

    for j := 1 to n do write(a[i,j]:5);

    writeln

  • 55

    end

    end

    end.

    4.3. PROBLEME PROPUSE

    n cele ce urmeaz vom nota prin Mm,n(D) mulimea matricelor cu m linii i n coloane avnd

    toate elementele din domeniul D. n cazul m=n, deci al matricelor ptrate, vom nota Mn,n(D) =

    MPn(D). Prin Z vom nota mulimea numerelor ntregi, iar prin R mulimea numerelor reale. Prin Vn(D)

    se noteaz mulimea vectorilor cu n componente, toate elemente din domeniul D.

    4.1. Se d o matrice m,n(R+). S se calculeze raportul dintre cel mai mic element i cel

    mai mare element al matricei.

    4.2. Se d o matrice m,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 m,n(R+). S se formeze un vector cu n componente, astfel nct

    componenta a i-a s fie egal cu elementul maxim din coloana a i-a a matricei.

    4.4. Se d o matrice Mm,n(R). S se determine linia i coloana care conin cel mai mic

    element pozitiv.

    4.5. Se d o matrice m,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 m,n(R). S se tipreasc indicii liniilor care conin elemente

    negative. S se formeze apoi matricea B, obinut din matricea A prin eliminarea acestor linii.

    4.7. Se d o matrice m,n(R+). S se schimbe ntre ele liniile matricei A astfel ca prima

    coloan s devin ordonat cresctor.

    4.8. Se d o matrice m,n(R+) i un interval S se rein ntr-un vector X toate

    elementele matricei aflate n intervalul

    4.9. Se d o matrice m,n(R+). Pentru fiecare linie s se scad din elementele sale

    valoarea minim din acea linie.

    4.10. Se d o matrice m,n(R). S se construiasc vectorul X =

    ( x , x , ..., x )1 2 k 179 ce reprezint indicii liniilor care conin valori nule.

  • 56

    4.11. Se d o matrice m,n(R). S se tipreasc matricea A completat cu o nou coloan

    n care elementul din linia a i-a este egal cu cel mai mare numr negativ din linia a i-a, dac exist

    elemente negative, respectiv cu 10 cnd nu exist elemente negative.

    4.12. Se d o matrice m,n(R+) i numerele naturale l i k (1

  • 57

    4.21. Se d o matrice m,n(R+). S se formeze matricea B cu m linii i n coloane unde

    ij ij2

    b = ( a - )max 186, unde max este cel mai mare element al matricei A.

    4.22. Se d o matrice A m,n(R+). S se formeze matricea B cu m linii i n coloane unde

    ijij

    i in 1j mj

    b = a , i < j

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

    daca

    altfel

    187

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

    linii i n coloane unde

    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 m,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 m,n(R+). S se formeze matricea B cu m linii i n coloane, n care elementul

    bij se definete ca suma elementelor matricei A aflate pe linia i, mai puin elementul aflat pe coloana j.

    4.26. Se d m,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

    ij

    ij ij

    c = a , a

    0, .

    daca este impar

    altfel

    191

    4.27. Se d m,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

  • 58

    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 m,n(R+). S se determine vectorii B i C definii astfel :

    i ij

    j

    i=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 m,n(Z). Fiind dat un numr natural p, s se formeze vectorul X cu m

    componente, unde xi reprezint numrul elementelor din linia a i-a a matricei A care sunt divizibile cu

    p.

    4.30. Se d n(R). S se determine linia l ce conine cel mai mare element al

    diagonalei principale i apoi s se schimbe linia i coloana l cu linia, respectiv coloana nti.

    4.31. Se d m,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.

    4.32. Se d n(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 n(R). S se ordoneze liniile i coloanele matricei astfel nct elementele

    de pe diagonala principal s fie ordonate cresctor.

    4.34. Se d n(R). n fiecare linie s se schimbe ntre ele elementele care se gsesc pe

    diagonala principal cu cele care se gsesc pe cea secundar.

    4.35. Se d n(R). S se determine vectorii X i Y cu n componente, unde:

    X(i) = numrul elementelor pozitive din linia i;

    Y(i) = numrul elementelor negative din coloana i .

    4.36. Se d n(R). S se calculeze suma primelor n puteri ale matricei A.

  • 59

    4.37. Se d n(R). S se calculeze matricea P = A*AT, unde A

    T reprezint transpusa

    matricei A.

    4.38. Se d n(R). S se genereze o matrice n(R) astfel nct elementele matricei

    s reprezinte elementele vectorului X scrise n urmtoarea 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 n(R). S se genereze o matrice ptrat A de ordin maxim posibil, astfel

    nct elementele matricei s reprezinte elementele vectorului X scrise n urmtoarea 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 n(R). S se genereze o matrice A ptrat de ordinul m, cu m maxim posibil,

    astfel nct elementele matricei s reprezinte elementele vectorului X scrise n urmtoarea 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 n(R). S se genereze o matrice ptrat A de ordinul m, cu m maxim posibil,

    astfel nct elementele matricei s reprezinte elementele vectorului X scrise n urmtoarea 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 i n(R) pentru n=m2. S se construiasc o matrice ptrat de

    ordinul m, dac este posibil, astfel:

    - deasupra diagonalei principale elementele matricei sunt elementele irului ncepnd 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:

    ai,j = max{ xj, ... , xi }.

    4.43. Se d 2n(R). S se construiasc o matrice ptratic de ordinul n astfel: se

    completeaz diagonala principal de sus n jos cu elemente consecutive din ir ncepnd cu x1;

    deasupra diagonalei principale se completeaz matricea paralel cu diagonala principal, de sus n jos,

  • 60

    cu elemente succesive din ir, ncepnd 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 2n(R). S se construiasc o matrice ptratic de ordinul n astfel nct:

    a = { x ,...,x }, i

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

    i 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 obinut din irul numerelor naturale prin nlocuirea

    fiecrui numr par p cu o secven format din numerele 1,p,p2 i a numrului 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 obinut din irul numerelor naturale prin

    nlocuirea fiecrui numr par p cu o secven format din p numere toate egale cu p i a numrului

    impar i cu o secven format din numerele 1,2,...,i).

    4.47. Se dau i m*n(R). S se genereze o matrice m,n(R) definit astfel:

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

    { x ,x ,...,x } , x 0ij

    i 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 i m*n(R). S se genereze o matrice m,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 m,n(R) definit

    astfel :

    este numr prim

    A(i,j) = este numr perfect neprim

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

    4.50. Fie B o matrice definit astfel:

    este numr prim

    B(i,j) =

    pentru i=1,2,...,m i j=1,2,...,n i fie matricea C de aceleai dimensiuni, n care linia i reprezint

  • 61

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

    i*j) , dac i*j < m*n/2

    A(i,j) =

    i+j) , n caz contrar,

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

    4.52. Se d i fie M(1)=a. S se formeze matricea ptrat 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 rsturnatul numrului p (exemplu: rsturnatul

    numrului 123 este numrul 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 poziie iniial n interiorul labirintului. S se gseasc cel mai scurt drum pe care se poate iei

    din labirint.

    4.54. Se d o matrice cu elemente cuvinte de maximum 30 de litere sau spaii. S se afle

    frecvena vocalelor n cuvinte:

    - pe linii;

    - pe coloane;

    - n matrice.

    4.55. Se dau vectorii m(R) i n(R). S se formeze matricea m,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 m(R) i n(R). S se formeze matricea m,n(R) dac

    iji j

    1 m 1 n

    c = a * b

    {a ,...,a ,b ,...,b }max200

    n cazul n care numitorul este nul se ia cij = min{ai, bj}.

  • 62

    4.57. Se dau vectorii m(R) i n(R). S se formeze matricea m,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 m(R) i n(R). S se formeze matricea m,n(R) dac

    ijk=1

    i

    k

    p=1

    j

    pc = a b 202

    4.59. Se dau dou matrice m,n(R). S se determine matricea m,n(R) unde

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

    4.60. Se dau dou matrice n(R). S se determine matricea n(R) definit

    prin:

    ij ik kjc = {a + b | k =1,2,...,n}.min 204

    4.61. Se dau dou matrice m,n(R). S se determine matricea m,n(B2) unde

    ijij ij

    ij ij

    c = 0 , a b

    1 , a = b .

    daca

    daca

    205

    4.62. Se dau dou matrice m,n(R). S se gseasc mulimea indicilor i pentru care:

    j=1

    n

    ij

    j=1

    n

    ija < b . 206

    4.63. Se cere s se genereze matricea A, ptratic de ordinul n, definit astfel:

    C(j,i), dac i 0 reprezentnd distana de la

    obiectul i la obiectul j (msur a gradului de disimilaritate dintre obiectele i i j). S se determine toate

    mulimile nevide de perechi de obiecte pentru care k-1 < d(i,j) k ( k k d(i,j)

    i,j=1,...,n}).

    4.65. S se tipreasc toate matricele ptrate de ordinul 4 care au un singur 1 pe fiecare linie

    i pe fiecare coloan iar n rest 0.

    4.66. Fie n(R) trei matrice diagonale, iar 2n(R) o matrice cu structura:

  • 63

    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 nn

    x , x ,..., x [0,2 ) . 208 S se tipreasc matricea

    ptrat de ordinul n care are proprietatea c linia a i-a a acestei matrice reprezint numrul xi n baza

    doi.

    4.69. Se d m,n(B2). S se determine numerele a cror reprezentri n baza 2 sunt date

    de coloanele matricei.

    4.70. Se d n(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 si

    daca

    209

  • 64

    CAPITOLUL 5

    SUBALGORITMI

    5.1. REUNIUNEA UNOR MULIMI

    Se consider, trei mulimi A, B, C. Se cere un program care afieaz:

    - elementele mulimii A n ordine cresctoare;

    - elementele mulimii B n ordine cresctoare;

    - elementele mulimii C n ordine cresctoare;

    - elementele mulimii n ordine cresctoare;

    - elementele mulimii n ordine cresctoare;

    - elementele mulimii n ordine cresctoare.

    Rezolvare.

    Pentru realizarea programului este necesar construirea a patru proceduri specificate n

    continuare:

    - o procedur pentru citirea unei mulimi: CIT(n,A);

    REZULTATE n,A {primesc valori prin citire}

    - o procedur pentru ordonarea unui ir: ORDON(r,X);

    DATE {de intrare}

    r, {numrul componentelor vectorului X}

    X; {vector cu n componente}

    REZULTATE X {la ieirea din subalgoritm vom avea: }

    { x1 < x2 < ... < xn }

    - o procedur pentru calculul reuniunii a dou mulimi:

    REUN(n,m,A,B,nm,AUB);

    DATE {de intrare}

    n, {numrul elementelor mulimii A}

    m, {numrul elementelor mulimii B}

    A, {mulimea {a1, a2, ... , an } }

    B; {mulimea {b1, b2, ... , bm } }

    REZULTATE nm, {numrul elementelor reuniunii }

    AUB

    - o procedur pentru tiprirea unei mulimi: TIPAR(n,A,ch);

    DATE {de intrare}

    n, {numrul elementelor mulimii A}

    A, {mulimea {a1, a2, ... , an } }

  • 65

    ch; {caracter considerat numele mulimii}

    REZULTATE afiarea elementelor mulimii

    - o procedur pentru ordonarea i apoi tiprirea unui ir: TIPORDON(r,X,ch);

    DATE {de intrare}

    r, {numrul componentelor vectorului X}

    X, { vector cu n componente arbitrare }

    ch; {caracter considerat numele mulimii}

    REZULTATE *ordonarea componentelor vectorului X i

    * afiarea elementelor ordonate cresctor

    - o procedur pentru calculul reuniunii a dou mulimi, cu ordonarea i tiprirea rezultatului:

    TIPREUN(n,m,A,B,nm,AUB).

    aceeai semnificaie ca la procedura REUN, dar, n plus, se tiprete AUB.

    Algoritmul pentru rezolvarea problemei, descris n limbajul PSEUDOCOD, este urmtorul:

    Algoritmul Exemplu1 este:

    Cheam CIT(n,A); { A e vectorul care conine n componentele }

    { sale cele n elemente ale mulimii A}

    Cheam CIT(m,B); { Citete mulimea B}

    Cheam CIT(p,C); { Citete mulimea C}