Recapitulare Bac Informatica

86
Recapitulare pentru bacalaureat 1. ALGORITMI..................................................... 3 1.1. Noţiunea de algoritm. Caracteristici :......................3 1.2. Date, variabile, expresii, operaţii:.......................3 1.3. Structuri de bază (liniară, alternativă si repetitivă):....5 1.4. Descrierea algoritmilor (programe pseudocod):..............8 2. Elementele de bază ale unui limbaj de programare (Pascal)....12 2.1 Vocabularul limbajului.....................................12 2.2 Constante. Identificatori..................................12 2.3 Noţiunea de tip de dată. Operatori aritmetici, logici, relaţionali....................................................13 2.4 Definirea tipurilor de date................................13 2.5 Variabile. Declararea variabilelor.........................13 2.6 Definirea constantelor.....................................14 2.7 Structura programelor. Comentarii..........................14 2.8 Expresii. Instrucţiunea de atribuire.......................14 2.9 Citirea/scrierea datelor...................................14 2.10 Structuri de control (instrucţiunea compusă, structuri alternative şi repetitive).....................................15 3.Subprograme................................................... 15 3.1. Subprograme. Mecanisme de transfer prin intermediul parametrilor...................................................15 3.2. Proceduri si functii predefinite..........................17 4. Tipuri structurate de date...................................18 4.1 Tipul tablou.........................18 4.2. Tipul sir de caractere....................................23 4.3. Tipul înregistrare (articol)..............................25 5. Fisiere text................................................. 26 5.1. Fisiere text. Tipuri de acces.............................26 5.2. Proceduri si functii predefinite pentru fisiere text......26 Sintaxa de declarare:..........................................26 Efect..........................................................27 Observatie importanta..........................................27 Probleme:......................................................27 1/86

description

recapitulare bac informatica

Transcript of Recapitulare Bac Informatica

Page 1: Recapitulare Bac Informatica

Recapitulare pentru bacalaureat

1. ALGORITMI....................................................................................................................................3

1.1. Noţiunea de algoritm. Caracteristici :............................................................................................3

1.2. Date, variabile, expresii, operaţii:.............................................................................................31.3. Structuri de bază (liniară, alternativă si repetitivă):..................................................................51.4. Descrierea algoritmilor (programe pseudocod):........................................................................8

2. Elementele de bază ale unui limbaj de programare (Pascal)..........................................................12

2.1 Vocabularul limbajului.............................................................................................................122.2 Constante. Identificatori...........................................................................................................122.3 Noţiunea de tip de dată. Operatori aritmetici, logici, relaţionali..............................................132.4 Definirea tipurilor de date........................................................................................................132.5 Variabile. Declararea variabilelor............................................................................................132.6 Definirea constantelor..............................................................................................................142.7 Structura programelor. Comentarii...........................................................................................142.8 Expresii. Instrucţiunea de atribuire..........................................................................................142.9 Citirea/scrierea datelor.............................................................................................................142.10 Structuri de control (instrucţiunea compusă, structuri alternative şi repetitive)....................15

3.Subprograme...................................................................................................................................15

3.1. Subprograme. Mecanisme de transfer prin intermediul parametrilor.....................................153.2. Proceduri si functii predefinite................................................................................................17

4. Tipuri structurate de date................................................................................................................18

4.1 Tipul tablou........................................................................................................184.2. Tipul sir de caractere...............................................................................................................234.3. Tipul înregistrare (articol).......................................................................................................25

5. Fisiere text......................................................................................................................................26

5.1. Fisiere text. Tipuri de acces.....................................................................................................265.2. Proceduri si functii predefinite pentru fisiere text...................................................................26Sintaxa de declarare:......................................................................................................................26Efect................................................................................................................................................27Observatie importanta....................................................................................................................27Probleme:........................................................................................................................................27

6. Algoritmi elementari......................................................................................................................28

6.1. Probleme care operează asupra cifrelor unui număr...............................................................296.2. Divizibilitate. Numere prime. Algoritmul lui Euclid..............................................................306.3. Sirul lui Fibonacci. Calculul unor sume cu termenul general dat...........................................336.4. Determinare minim/maxim.....................................................................................................356.5. Metode de ordonare (metoda bulelor, inserŃiei, selectiei, numărării)....................................36Metoda de sortare prin numărare....................................................................................................396.6. Interclasare..............................................................................................................................40

1/66

Page 2: Recapitulare Bac Informatica

6.7. Metode de căutare (secventială, binară)..................................................................................416.8 Analiza complexităţii (considerând criteriile de eficienţă durata de executare şi spaţiu de memorie utilizat)............................................................................................................................43

7. Subprograme definite de utilizator.................................................................................................43

7.1 Proceduri şi funcţii...................................................................................................................437.2 Proiectarea modulară a rezolvării unei probleme.....................................................................46

8. Recursivitate...................................................................................................................................47

8.1 Prezentare generală...................................................................................................................488.2 Funcţii şi proceduri recursive...................................................................................................48

9. Metoda backtracking......................................................................................................................49

9.1. Prezentare generală..................................................................................................................499.2. Probleme de generare. Oportunitatea utilizării metodei backtracking....................................52

10. Generarea elementelor combinatoriale.........................................................................................55

10.1          Permutari, aranjamente, combinari...............................................................................5510.2 Produsul cartezian .Submultimi..........................................................................................59

11.Grafuri...........................................................................................................................................60

11.1Grafuri neorientate..................................................................................................................6011.2Grafuri orientate......................................................................................................................6211.3Arbori......................................................................................................................................65

2/66

Page 3: Recapitulare Bac Informatica

1. ALGORITMI

1.1. Noţiunea de algoritm. Caracteristici 

Prin algoritm  se înţelege o mulţime ordonată şi finită de reguli ce descriu o succesiune finită de operaţii necesare rezolvării unei probleme.Paşii algoritmului trebuie să-i fie indicaţi calculatorului sub forma unor comenzi numite instrucţiuni. Mulţimea tuturor instrucţiunilor ce descriu algoritmul de rezolvare a unei probleme formează programul. Pentru a dialoga cu un calculator, este necesară cunoaşterea unui limbaj comun omului şi calculatorului.

Atenţie! Care sunt deosebirile dintre un calculator de buzunar şi unul programabil?

Exemple de algoritmi:

-calcularea ariei unui triunghi(se cunosc a,b,c);

-calcularea înălţimilor unui triunghi (se cunosc a,b,c);

-calcularea mediei unui elev;

-rezolvarea ecuaţiei de gradul I etc.

Caracteristici ale algoritmilor :

-generalitatea = proprietatea de a fi valabil pentru o clasă ( un gen) de probleme; (ex nu aduna 3+4 ci a+b)

-finitudinea  = proprietatea de a permite obţinerea soluţiei problemei după parcurgerea unui număr finit de operaţii (contraexemplu: ciclu infinit ex repeat write(‘*’) ;until 3=4 ;).

-unicitatea= proprietatea conform căreia ori de câte ori se porneşte de la acelaşi set de valori ale variabilelor de intrare se obţin aceleaşi soluţii.

Atenţie!Fiecare proprietate trebuie exemplificată prin căte un exemplu şi un contraexemplu.

Atenţie! Dacă un algoritm are aceste 3 proprietăţi nu înseamnă că el este şi corect.

1.2. Date, variabile, expresii, operaţii:1. Date :

-          Numerice 

-          Alfanumerice

-          Logice

2. Operatii :

-          aritmetice

-          relationale (<,>,<>,<=,>=)3/66

Page 4: Recapitulare Bac Informatica

-          logice (booleene true, false) 

3. Expresii

-          Aritmetice

-          relationale

-          logice (si, sau, not)

Tabela de adevăr a operatorului si:  

X                                 Y                                 X si Y

           False                           False                           False

            False                           True                             False

            True                             False                           False

            True                             True                             True

Observatie: ‚si’ are valoarea true doar daca ambii operanzi sunt true si falsa daca unul dintre ei este false.

Tabela de adevar a operatorului sau:  

X                                 Y                                 X sau Y

            False                           False                           False

            False                           True                             True     

            True                             False                           True     

            True                             True                             True     

 

Observatie: ‚sau’ are valoarea false doar daca ambii operanzi sunt falsi si true daca unul dintre ei este true.

Tabela de adevar a operatorului  not  

X                                 not XFalse                           TrueTrue                             False   

Operatorul XOR (sau exclusiv):

X                                 Y                                 X xor Y

           False                           False                           False

4/66

Page 5: Recapitulare Bac Informatica

            False                           True                             True

            True                             False                           True

            True                             True                             False

Aplicatii :

Legile lui De Morgan

Not(p sau q)= not p si not q

Not (p si q)= not p sau not q

1.3. Structuri de bază (liniară, alternativă si repetitivă):

1.1. Structuri liniare1.1.1. Citirea datelor

Citire

Sintaxa :

Citeste(v1,v2,…,vn) ;

Unde v1,… vn= variabile

Efect : calculatorul asteapta introducerea de la tastatura a valorii variabilelor v1,…, vn si da aceasta valoare (in memorie) variabilelor precizate

Exemplu : Citeste(a,b) => Memorie  |  Ecran

a 2                     2         

b 3                     3

1.1.2. Scrierea expresiilor

Sintaxa : Scrie(e1,e2,…,en);

Unde e1,…,en=expresii

Efect: Se evalueaza(calculeaza) valoarea expresiilor din lista si rezultatul se afiseaza pe ecran.

Exemplu : Scrie(a,b); => Ecran : 23

5/66

Page 6: Recapitulare Bac Informatica

  scrie(á este ‘, a); =>Ecran: A este 2

OBS importanta: in sintaxa lui ‘citeste’in lista nu pot sa apara expresii. De ce ? …

Atenţie la formatul de afişare(a:2, a:n1:n2)!

1.1.3. Atribuirea 

Sintaxa :

V := expresie

Se citeste : « v ia valoarea expresie »

Efect : Se evalueaza expresia v si rezultatul ii este dat (in memorie) lui v.

Exemple:

A :=a+b

B :=b+2*a

=> Memorie:….    

1.2. Structuri alternative :1.2.1. Instructiunea IF

daca  c atunci X    altfel Y

unde c=conditie (expresie logica) , X,Y= cate o singura instructiune ;

Efect - se evalueaza c si daca este true se executa X ; daca este false se executa Y ;

-  Probleme:

* Intr-o sala de clasa sunt mese si scaune. Se cunoaste numarul lor. Care dintre acestea sunt mai multe ? Cunoscand si numarul elevilor clasei si faptul ca la o masa pot sta 3 persoane afisati daca :

a)       sunt destule mese ;

b)       sunt destule scaune. 

* Se cunosc 5 numere<10000. Afisati numarul de cifre al acestora.

Scrie( íntrodu primul numar’) ;

Citeste(a) ;

Daca a<10 atunci scrie (‘numarul are o cifra’)

                    Altfel daca a<100 atunci scrie(‘numarul are 2 cifre’)

                                                   Altfel daca a<1000 atunci scrie(‘numarul are 3 cifre’)6/66

Page 7: Recapitulare Bac Informatica

                                                                                  Altfel scrie (‘numarul are 4 cifre);           

Scrie( íntrodu un numar’) ;

Citeste(b) ;

Daca b<10 atunci scrie (‘numarul are o cifra’)

                    Altfel daca b<100 atunci scrie(‘numarul are 2 cifre’)

                                                   Altfel daca b<1000 atunci scrie(‘numarul are 3 cifre’)

                                                                                  Altfel scrie (‘numarul are 4 cifre);           

Scrie( íntrodu un numar’) ;

Citeste(c) ;

Daca c<10 atunci scrie (‘numarul are o cifra’)

                    Altfel daca c<100 atunci scrie(‘numarul are 2 cifre’)

                                                   Altfel daca c<1000 atunci scrie(‘numarul are 3 cifre’)

                                                                                  Altfel scrie (‘numarul are 4 cifre);           

Scrie( íntrodu un numar’) ;

Citeste(d) ;

Daca d<10 atunci scrie (‘numarul are o cifra’)

                    Altfel daca d<100 atunci scrie(‘numarul are 2 cifre’)

                                                   Altfel daca d<1000 atunci scrie(‘numarul are 3 cifre’)

                                                                                  Altfel scrie (‘numarul are 4 cifre);           

Scrie( íntrodu un numar’) ;

Citeste(e) ;

Daca e<10 atunci scrie (‘numarul are o cifra’)

                    Altfel daca e<100 atunci scrie(‘numarul are 2 cifre’)

                                                   Altfel daca e<1000 atunci scrie(‘numarul are 3 cifre’)

                                                                                  Altfel scrie (‘numarul are 4 cifre);           

Dupa rezolvarea acestei probleme se simte nevoia unei noi instructiuni: repeta.

1.2.2. Instructiunea Case

7/66

Page 8: Recapitulare Bac Informatica

Sintaxa:

CASE e OF

              L1:I1;

  L2:I2;

  L3 :I3 ;

….

[else In+1]

end ;

e= expresie cu rezultat de tip ordinal ;

L1,L2,…Ln= liste de valori posibile ale expresiei e (contin valori sau/si intervalle delimitate de ,) ;

I2, I2,…= cate o singura instructiune;

Efect: se evalueaza expresia e si se cauta lista careia ii apartine valoarea rezultata; se va executa instructiunea corespunzatoare listei. Daca nu e gasita o astfel de lista, se executa In+1, daca aceasta exitsta, altfel se trece la urmatoarea instructiune.

 

Structuri repetitive1.3.1. Instructiunea REPEAT  1.3.2. Instructiunea WHILE1.3.3. Instructiunea FOR1.3.4. Verificari.

1.4. Descrierea algoritmilor (programe pseudocod):

Programarea structurata a inceput la inceputul anilor 70. Este un concept cu o importanta fundamentala in scrierea algoritmilor. In general, algoritmii se eleboreaza prin utilizarea exclusiva a anumitor structuri (liniar, alternativa, repetitiva). Prin structura se intelege o anumita forma de imbinare a operatiilor cu care lucreaza algoritmii.

Structuri de bază:        structurile liniară        alternativă          repetitivă  Descrierea algoritmilor cu ajutorul schemelor logice şi în pseudocod;

Schema logică este reprezentarea grafică a unui algoritm.

 

 Blocurile necesare întocmirii unei scheme logice:

8/66

Page 9: Recapitulare Bac Informatica

Blocul terminal – pune în evidenţă începutul şi sfărşitul unei scheme logice; spre deosebire de celelalte, blocul terminal START, respectiv STOP pot să apară numai o singură dată într-o schemă logică.  

Blocul de intrare/ieşire  - pune în evidenţă informaţiile de intrare, respectiv ieşire, precum şi momentul şi locul în care acestea se execută; prin intermediul acestor blocuri are loc schimbul de informaţii dintre algoritmul propriu-zis şi exterior.

Blocul de calcul - pune în evidenţă operaţiile aritmetice, precum şi transferul de valori între diferitele variabile utilizate în algoritm.

Blocul de decizie - pune în evidenţă punctele de ramificare ale algoritmului (în funcţie de anumite condiţii). 

 Blocul de procedură (funcţie) – permite scrierea prescurtată a unei secvenţe care execută o anumită funcţiune;

Blocul conector - pune în evidenţă nodurile (punctele de intersecţie) unui algoritm

Modul de parcurgere al algoritmului (de trecere de la un bloc la altul) este indicat prin săgeţi având un singur vârf.

Descrierea modular-structurată a algoritmilor :

      Pentru ca un algoritm să fie simplu, eficient, intuitiv, uşor de verificat şi dezvoltat sau corectat el trebuie realizat ca o succesiune liniară de module formate din una sau mai multe instrucţiuni, cu proprietatea că au o singură intrare şi o singură ieşire. Pentru ca un modul să aibă o singură intrare şi o singură ieşire dispunem de trei structuri fundamentale

-structuri liniare;

-structuri alternative;

      -structuri repetitive ;

Structurile liniare= succesiuni de operaţii ce se execută necondiţionat în ordinea dată.

 Structurile alternative constau dintr-un bloc de decizie (c) şi două blocuri (a1) şi (a2) care se execută alternativ, după cum contractul este adevărată sau falsă (DA/NU) şi un bloc conector.

Observaţie: a1 sau a2 pot să fie vide.

Structurile repetitive permit efectuarea uneia sau mai multor operaţii de un număr de ori până o condiţie este îndeplinită. Structurile repetitive poartă şi denumirea de structuri ciclice sau cicluri.

 Avantaj: scrierea programului poate fi făcută de mai multe persoane, modificările se fac uşor.

Pseudocod:

            Structuri liniare: citirea, scrierea, atribuirea, instrucţiunea compusă, instrucţiunea vidă.

            Structuri alternative: dacă (if), case (case)

            Structuri repetitive: repetă (repeat), cât_timp (while), pentru (for).9/66

  

  

  

Page 10: Recapitulare Bac Informatica

a) Structuri liniare:

a1) citirea;

a2) scrierea;

a3) atribuirea;

a4) instrucţiunea compusă;

a5) instrucţiunea vidă.

b) Structuri alternative:

b1) dacă;

c) Structuri repetitive:

c1) repetă;

c2) cat timp;

c3) pentru.

Aplicaţii:

Ce vor tipări următoarele secvenţe de program :

1.      readln(a,b,c) ;

if a=1 then if b=2 then if c=3 then writeln(‘3’) else writeln(‘2’) else writeln(‘1) else writeln(‘0’) daca se citesc valorile 1 3 3?

2.      readln(a,b,c);

if a=1 then   else if b=2 then   else if c=3 then else writeln(‘0’)

dacă se citesc valorile 1 2 3?

3.      readln(a,b,c) ;

if (c<a) and not(a>=b) then c:=a+b

                                  else if not(a>=c) and (c<b) then a:=c+b

                                         else if (a<b) and (b<c) then a:=b+c;

writeln(a,b,c)’;

daca se citesc valorile 4 8 6 ?       

4)      readln(a,b) ;

10/66

Page 11: Recapitulare Bac Informatica

  if  a>=b then if b>0 then begin a:=a+2; b:=b-a; end else b:=b-4

else if a+2 >=b then b:=2-b else a:=a+b;

writeln(a,b);

 dacă se citesc valorile 0 1 ?         

5)      b :=-1 ;

repeat   readln(a) ;  if b<a then b:=a; until a=0;

writeln(b);

dacă se vor citi valorile: 4,-300009,33000 si 0.

6)      x :=7; for i :=1 to 5 do x :=x+1 ;writeln(x);

7)      x:=1; while x<=10 do x:=x+1; writeln(x);

8)      x:=1; for I:=1 to 2 do write(x); writeln;

9)      x:=1;I:=2; while I>=0 do begin write(x); I:=I-1; end;

10)  x:=1; for I:=1 to n do x:=x*n; pt n=5;

11)  x:=1; for I:=1 to n do x:=x*10;

12)  x:=10; for I:=1 to n do x:=x*I;

13)  x:=1; I:=0;

14)  while I<n do x:=x*10;I:=I+1;

15)  a:=0;b:=1; if a=0 then if b=0 then write('b=0')        else c:=-a/b;

16)      a:=1;b:=0; if a=0 then if b=0 then write('b=0')        else c:=-a/b;

17)    a:=0;b:=0; if a=0 then if b=0 then write('b=0')       else c:=-a/b;

18)   a:=7;b:=14; if a=0 then if b=0 then write('b=0')       else c:=-a/b;

19)     p:=1;i:=1;while i<7 do i:=i+1;p:=p*i;

20)     p:=1;i:=6;while i>1 do begin p:=p*i;i:=i-1; end;

21)    p:=1;i:=1;repeat p:=p*i;i:=i+1; until i<6;

22)    p:=1;n:=2;for i:=2 to n do p:=p*i;

23)    var i,n:integer;  begin n:=8;  for i:=1 to n do n:=n-1;  end.

24)     var x,y:char;  begin  x:='x';y:=x;writeln(x,y);writeln('x','y');  x:=y;y:='x'; writeln(x,y); end.

11/66

Page 12: Recapitulare Bac Informatica

25)    var x,y:char; begin  x:='x';y:='y';writeln(x,y);writeln('x','y');  x:=y;y:='x'; writeln(x,y); end.

26)    var i,j,k:integer; begin  for i:=1 to 2 do    begin    writeln;   for j:=1 to i*i do    begin      for k:=1 to i+j do write('*');      writeln;      end;      end; end.

27)     var i,j,k:integer;  begin for i:=1 to 2 do   begin   writeln;   for j:=1 to i+i do      begin      for k:=1 to j-i do write('*');      writeln;      end;      end; end.

28)   Verificaţi: var x:integer; begin for x:=1 to 10 do   case x of     1,3,5,7,9:writeln('Impar ',x);     2,4,10:writeln('Par ',x);   end end.

 

2. Elementele de bază ale unui limbaj de programare (Pascal)

2.1 Vocabularul limbajului

Setul de caractere (alfabetul) : - litere mari şi mici ale alfabetului latin (caractere alfabetice) :a, b, c etc. - cifrele sistemului de numeraţie zecimal (caractere numerice ) 0,1,2,3,…9 - simbolurile +,-,*,/,=,<.>,(,),&, etc numite caractere speciale

Separatori de simboluri:  spaţiul şi enter.

Comentariul :{ } sau (* *), caracterul de sfârşit de linie (eol), caracterul „ ; ” separă instrucţiunile şi declaraţiile. Poate să lipsească înaintea lui end.

2.2 Constante. Identificatori

Identificatorii desemnează nume de programe, constante, tipuri, variabile, funcţii, proceduri, parametri. Printr-un identificator înţelegem un nume asociat unei constante, variabile, proceduri sau funcţii. Un identificator poate conţine numai litere, cifre, caracterul special  “_” şi trebuie să înceapă obligatoriu cu o literă. Exemplu: A2, B, val_medie etc. O categorie specială de identificatori este reprezentată de cuvintele cheie al limbajului: program, begin, until, to, downto etc.

Constante întregi -cele cuprinse în [-32768, 32767] .Ex :13,-25,678,etc.

Constante reale  sunt numere reale cuprinse între 3.4*10 la puterea -4352 şi 1.1*10 la puterea 4932.

Constantele caracter: orice limbaj de programare conţine un set de caractere propriu. Setul de caractere folosit de limbajul Pascal se numeşte setul ASCII şi conţine litere, cifre şi caractere speciale.

Constante simbolice (desemnate prin identificatori) : - identificatori introduşi  prin definiţii de constante; - identificatorii constantelor unui tip enumerare; - identificatorii standard true şi false; - identificatorii nil şi maxint;

12/66

Page 13: Recapitulare Bac Informatica

2.3 Noţiunea de tip de dată. Operatori aritmetici, logici, relaţionali

Tipul unei date defineşte mulţimea valorilor pe care le poate lua variabila, precum şi mulţimea de operaţii care pot fi efectuate cu elementele mulţimii respective. Ex: integer, boolean, real etc.

Operatori aritmetici: +, -, *, /, div, mod.Operatori logici: and, or, xor, not.Operatori relaţionali: <, >, =, <=, >=, <>.

2.4 Definirea tipurilor de date

Type nume_tip=tip ; Tipurile ordinale reprezintă mulţimi finite şi ordonate de valori. Putem să ne referim la numarul de ordine al unei valori (cu funcţia ord), putem specifica elementul succesor ( cu funcţia succ) sau cel predecesor (cu funcţia pred) al unui element dat.

- Tipuri simple standard: tipuri întregi, real, boolean (logic), char (255 caractere). Tipurile întregi pot fi: integer(-32678...32767), word(0...65535), shortint(-128...127), byte(0...255), longint(-2.147.486.348...2.147.483.647).

-Tipuri ordinale definite de utilizator: enumerat şi subdomeniu. Tipul enumerare defineşte o mulţime ordonată de valori: se enumeră un şir de identificatori care desemnează valorile posibile. Primul identificator desemnează cea mai mică valoare, cu numărul de ordine zero. Poate fi definit astfel: Type nume_tip=(idebtif1,identif2,….,identifn); Variabilele de tip enumerare sunt declarate în secţiunea var. Ele pot lua una din valorile enumerate în listă. Operaţiile ce se pot face sunt : atribuirea, determinarea numărului de ordine (ord), determinarea succesorului sau predecesorului(deter. succ. ultimului element sau pred. primului elem. va genera eroare), comparaţia (<,<=,>,>=,…)

-Tipul interval. Fiind  dat un tip ordinal, din acesta se poate genera un nou tip, numit tipul interval. Definiţia lui indică valoarea constantă cea mai mică şi cea mai mare din interval (în sensul numărului de ordine) şi cuprinde toate valorile dintre ele. Exemple : 2..7 sau ‘c’..’f’. Type nume_tip=valoarea_minima..valoarea_maximă Obs : valoarea_minimă≤valoarea maximă. Nu este permisă definirea unui interval al tipului real, deoarece acesta nu este un tip ordinal.

-Tipul fişier(f:text;);-Tipuri structurate: tablouri unidimensionale(vectori- ex: var v:array[1..100];), tablouri

bidimensionale (matrici ex:var m:array[1..100,1..100];), sir de caractere (ex: v:string;), articol (ex: a:record

n:integer; end;).

2.5 Variabile. Declararea variabilelor

Spre deosebire de constante, o variabilă este o dată ale cărei valori se pot modifica la fiecare nouă execuţie a programului sau chiar în timpul unei execuţii. Orice variabilă are asociat un anumit tip.

O declaraţie de variabilă asociază  un nume şi un tip unei locaţii de memorie. Fiecare variabilă ce apare într-un program Pascal trebuie să fie declarată în secţiunea var în felul următor :

Var listă_de _identificatori1:tip1; …. listă_de _identificatorin:tipn;Identificatorii din listă sunt despărţiţi prin virgulă.

2.6 Definirea constantelor

13/66

Page 14: Recapitulare Bac Informatica

Într-un program Pascal, constantele pot fi utilizate direct prin valoare sau printr-un identificator. Acest identificator se defineşte în partea de definire a constantelor. Astfel, constanta este utilizată în locul valorii sale, prin identificatorul său.

Exemplu: const pi=3.1415.Odată stabilită valoarea identificatorului de constantă, aceasta nu se mai poate modifica prin

instrucţiuni ale programului. Avantaje ale utilizării constantelor: economie de memorie, modificarea simplă a programelor, claritate sporită a programului.

2.7 Structura programelor. Comentarii

[program nume;] {numele programului}[uses …;] {…=biblioteci de programe}[const max=20;] { max=20 e un exemplu}[type nume_tip=tip ;] {tip e un tip de date}[var listă_de _identificatori1:tip1;][subprograme]begin programul propriu-zis;{corpul programului}end.

[]-poate să lipsească.

2.8 Expresii. Instrucţiunea de atribuire

În timpul execuţiei unui program, la întâlnirea unei expresii, calculatorul evaluează expresia respectivă, adică în acel moment variabilele din componenta expresiei au nişte valori, calculatorul va înlocui în expresie variabilele cu valorile lor şi se va obţine valoarea expresiei.

În cadrul expresiilor aritmetice, logice şi relaţionale pot fi utilizate funcţiile standard (funcţii declarate în unitul SYSTEM) următoare: - funcţii de transformare: chr, ord, trunc, round; - funcţii matematice: int, frac, sin, cos, arctan, pi,sqrt,ln,exp,abs,sqr; - proceduri şi funcţii referitoare la valori ordinale: succ, inc, pred, dec, odd;

Exista 4 grupe de prioritate:-Grupa 1 (prioritate maxima) : not, + (operator unar), - (operator unar);-Grupa 2( se mai numesc si operatori multiplicativi): and, *, /, div, mod ;-Grupa 3(se mai numesc si operatori aditivi): or, xor, +, - ;-Grupa 4 (cea mai mica prioritate si  cuprinde operatorii relationali) : <,<=,>,>=,=,<>.Instrucţiunea de atribuire se face in felul urmator : v :=expresie ;{v este o variabilă}

2.9 Citirea/scrierea datelor

Citirea datelor se realizează cu ajutorul instrucţiunii „read”. Exemplu: read(n);.Se pot citi date de la tastatură sau dintr-un fişier.

Scrierea datelor se realizează cu ajutorul instrucţiunii „write”. Exemplu:write(6);. Şi datele pot fi scrise într-un fişier.{unde n este o variabilă}

2.10 Structuri de control (instrucţiunea compusă, structuri alternative şi repetitive)

14/66

Page 15: Recapitulare Bac Informatica

Liniare:- citirea (read, ex: read(n););- scrierea (write, ex: write(n););- atribuirea (v:=expresie);- instrucţiunea vidă;- instrucţiunea compusă(begin {read(n); write(n);}end.);

Alternative:- dacă (if, ex: if n=1 then n:=2;);

Repetitive:- repetă (repeat, ex: n:=1 repeat n:=n+1; until n=4; );- cât timp (while, n:=1; while n<5 do n:=n+1; );- pentru (for, for n:=1 to 4 do write(n);).{unde n este o varialilă}

3.Subprograme 3.1. Subprograme. Mecanisme de transfer prin intermediul parametrilor

Definitie: Subprogramul reprezinta parti identificabile prin nume care se pot activa la cerere prin intermediul acestui nume.

O parte din subprogram se contruieste ca subprogram daca un algoritm cuprinde in mai multe locuri aceiasi secventa de operatii executabila pentru aceleasi date sau pentru date diferite. In loc ca subprogramul sa cuprinda in acelasi loc, acelasi grup de instructiuni, concepand grupul de intructiuni ca subprogram, el va aparea in program o singura data si se va activa de mai multe ori. Partea respectiva de program rezolva o subproblema din cele in care se descompune problema complexa. In limbajul Pascal, avem doua tipuri de subprograme : procedurile si functiile. Deosebirea intre ele consta in numarul de valori calculate si returnate programului apelat. Procedurile calculeaza mai multe valori sau nici una, iar functiile returneaza o singura valoare asociata numelui functiei. Atat procedurile cat si functiile pot fi standard(predefinite in unitul sistem), cat si nestandard(definite de utilizator). Procedurile si functiile nestandard trebuie declarate obligatoriu inainte de a fi apelate. 

O declarare de subprograme:      -un antet de supbrogram care precizeaza interfata subprogramului cu mediul     -blocul subprogramului care descrie functionarea lui interna

Domeniul de vizibilitate(valabilitate) al identificatorilor:      Prin domeniul de vizibilitate (valabilitate) se intelege zona de program in care e valabila declararea sau definirea unui identificator. Toti indentificatorii definiti sau declarati intr-un bloc sunt cunoscuti in blocul respectiv si se numesc variabile locale. Daca blocul cuprinde blocuri incluse in care identificatorii (variabile locale ale acestora) nu se definesc sau redenumesc, atunci acestea sunt cunoscute in blocurile incluse si se numesc variabile globale pentru acesta.

15/66

Page 16: Recapitulare Bac Informatica

Daca o variabila declarata intr-un bloc se redefineste atunci in blocul in care a fost redeclarata va fi variabila atribuita generata la redeclarare.

A.Procedurile

Declararea si apelul procedurilor.Parametrii formali si parametrii efectivi

Definitie:      Procedura este un subprogram care calculeaza mai multe valori accesibile sau nu programului apelant sau efectueaza anumite operatii fara sa calculeze vreo valoare.

Valorile calculate accesibile programului apelant reprezinta parametrii de iesire ai subprogramului. Acestia pot depinde de anumite valori pe care subprogramul le primeste din programul apelant, valori reprezentand parametrii de intrare. Parametrii formali sunt variabile simbolice in care lucreaza subprogramul. Ele sunt declarate in antetul subprogramului si sunt cunoscute numai in interiorul subprogramului.. Parametrii efectivi reprezinta variabilele cu care subprogramele lucreaza efectiv in momentul activarii. La apelarea procedurii se specifica parametrii efectivi sau actuali prin intermediul instructiunii procedurale      Declararea procedurii: PROCEDURE nume_procedura(lista parametrii)      -parametrii precizati la scrierea proedurii sunt parametrii formali si se separa prin “;”       -pentru fiecare parametru se precizeaza numele si tipul acestuia.

  Apelarea procedurii:          Pentru a executa o procedura aceasta trebuia apelata. La apel se da numele procedurii si valorile concrete ale parametrilor care se separa prin punct si virgula.      Ex : uses crt; procedure citire(n :integer ; k :char) ;      begin       writeln(‘Introdu un numar si litera atribuita lui!’); read(n); read(k); writeln(‘Pentru litera ‘,k,’ gasim cifra ‘,n,’.’);       end; begin clrscr; citire(n, k); end.

      Cand se apeleaza o procedura, modulul apelant a abandonat temporar, si se executa procedura. In timpul executiei procedurii, parametrii formali sunt inlocuiti in tot corpul procedurii cu parametrii actuali (valori concrete). Dupa executarea procedurii se revine in modulul apelant la linia imediat urmatoare celei care a facut apelul. Parametrii formali si parametrii efectivi nu e obligatoriu sa aiba acelasi nume dar trebuie sa existe o concordanta de numar, tip si ordine.

B.Functiile

Declararea si apelul functiilor:    

Definitie:     Functia este un subprogram care calculeaza si returneaza programului apelant o singula valoare.

Aceasta valoare este asociata numelui functiei. Iar tipul poate fi simplu, string sau reper. Valoarea returnata de functie nu poate avea alt tip structurat decat string.

16/66

Page 17: Recapitulare Bac Informatica

Declararea unei functii:  FUNCTION nume_functie(lista parametrii formali): identificator de tip;     -nume_functie reprezinta numele functiei, al carei tip este identificator de tip  -identificator de tip = nume de tip simplu: STRING sau REPER;

Blocul functiei trebuie sa contina obligatoriu o instructiune de atribuire prin care identificatorul functiei primeste valoarea unei expresii.     Identificatorul functiei nu are voie sa apara in partea dreapta a unor atribuiri decat daca functia este recursiva. 

Apelarea functeii:      - se intrerupe calculul expresiei in care a aparul apelul functiei ;     - se transmit parametrii, daca exista, exact ca la proceduri ;     - se executa functia;           Ex : uses crt; var a:integer; b:real; function f(var x:real);      begin       if x<0 then x:=-x; x:=x*10; x:=x mod 10;      end; begin clrscr; a:=12; b:=3.4567; a:=a+f(b); writeln(a+f(b)+f(b)); end.

3.2. Proceduri si functii predefinite

Definitie:

Procedurile si functiile predefinite sunt niste blocuri de instructiuni care au fost scrise de catre autori ale limbajului.

Pentru a folosi o astfel de procedura trebuie sa avem executia adica sa o apelam.

Ex. proceduri: - write -writeln Sunt folosite pentru afisarea unor date pe ecran.

Functiile predefinite sunt similare cu procedurile, dar in plus, in cazul unor executari, o functie intoarce o valoare adica noi apelam functia , ea se executa si la sfarsitul executiei ne da inapoi un rezultat. Ex: -ABC(X) returneaza mod lui z -SQR(X) returneaza X²

-SQRT(x) returneaza radical X

17/66

Page 18: Recapitulare Bac Informatica

4. Tipuri structurate de date

4.1 Tipul tablou

Tipul tablou este tipul compus, care consta dintr-un numar fix de componente, fiecare componenta având acelasi tip. La definirea tipului tablou trebuie precizat atât tipul componentelor, cât si tipul indicelui, care stabileste numarul componentelor tabloului .

1.1.1 Tipul array

Sintaxa declararii:

Nume_tip= array [l1..l2] of tip;

L1=limita inferioara a valorilor indicilor;

L2=limita superioara a valorilor indicilor;

l1,l2 de tip ordinal;

tip=tipul elementelor tabloului (tip oarecare);

Fiecare componenta a unei variabile de tip tablou poate fi specificata prin numele variabilei urmat de indice încadrat între paranteze patrate (de ex. a[4]).

Deoarece tip poate fi de orice tip, el poate fi tot un tip tablou. Astfel devine posibila definirea tipului tablou multidimensional.

-exemple de siruri;

-exemple de matrici (tablouri bidimensionale);

-exemple de tablouri tridimensionale;

-citirea si afisarea sirurilor, a matricilor;

Sa se determine câte elemente prime se afla deasupra diagonalei secundare a unei matrice cu n x n elemente naturale.

type matrice =array [1..100,1..100] of integer;

var f:text;

x,i,j,n,k,t:integer;

18/66

Page 19: Recapitulare Bac Informatica

a:matrice;

begin

assign (f,'date.in'); reset(f);

readln(f,n);

t:=0;

for i:=1 to n do

for j:=1 to n do

read(f,a[i,j]);

for i:=1 to n do

begin

for j:=1 to n do

write(a[i,j]:3);

writeln

end;

for i:=1 to n do

for j:=1 to n-i+1 do

begin

x:=0;

for k:=2 to a[i,j]-1 do

if a[i,j] mod k =0 then

x:=x+1 ;

if x=0 then t:=t+1;

end;

writeln('sunt' ,t, 'numere prime');

end.

19/66

Page 20: Recapitulare Bac Informatica

Se citeste de la tastatura o matrice de dimensiune n x n. Spuneti daca exista in matrice doua linii sau doua coloane gemene (doua linii sunt gemene daca au aceleasi elemente, eventual in alta ordine)

Ex

N=3

1 2 1

4 5 6

2 1 1

Liniile 1 si 3 sunt gemene

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

matrice =array [1..100] of sir;

var f:text;

x,i,j,n,k,t:integer;

da:boolean;

a:matrice;

procedure geamana(i,j:integer;var da:boolean);

var b,c:sir;cc: integer; k:integer; sant:integer;

begin

{b:=a[i];c:=a[j];}

for k:=1 to n do b[k]:=a[i,k];

for k:=1 to n do c[k]:=a[j,k];

repeat

sant:=0;

for k:=1 to n-1 do if b[k]>b[k+1] then

begin

cc:=b[k];b[k]:=b[k+1];b[k+1]:=cc;

sant:=1;

end;

until sant=0;

20/66

Page 21: Recapitulare Bac Informatica

repeat

sant:=0;

for k:=1 to n-1 do if c[k]>c[k+1] then

begin

cc:=c[k];c[k]:=c[k+1];c[k+1]:=cc;

sant:=1;

end;

until sant=0;

sant:=0;

for k:=1 to n do if b[k]<> c[k] then sant:=1;

if sant=0 then da:=true

else da:=false;

end;

begin

assign (f,'date.in'); reset(f);

readln(f,n);

t:=0;

for i:=1 to n do

for j:=1 to n do

read(f,a[i,j]);

for i:=1 to n do

begin

for j:=1 to n do

write(a[i,j]:3);

writeln

end;

for i:=1 to n do

for j:=i+1 to n do

21/66

Page 22: Recapitulare Bac Informatica

begin

geamana(i,J,da);

if da then begin writeln('existsa doua gemene',i,' cu ',j);j:=n;i:=n;end;

end;

if not da then writeln('nu exista gemene');

end. Alte probleme asemanatoare :

1. Verificati daca o valoare întreaga X, citita de la tastatura, se gaseste printre cele n elemente întregi ale unui vector. Elementele vectorului se vor citi de la tastatura în ordine crescatoare.

2. Sa se afle cate elemente maxime are un sir dat cu n elemente.

3. Sa se determine câte elemente prime se afla deasupra diagonalei principale a unei matrice cu n x n elemente naturale.

1. Se cunoaste un numar n si n numere citite de la tastatura. Calculati maximul lor.

program unu;

var f:text;

maX,n,i:integer;

a:array [1..100] of integer;

begin

write ('n='); readln(n);

for i :=1 to n do

begin

write('a[',i,']=');

readln(a[i]);

end;

max:=a[1];

22/66

Page 23: Recapitulare Bac Informatica

for i:=1 to n do

if a[i]>max then max:=a[i];

writeln ('max este',MAX);

Readln;

end.

4.2. Tipul sir de caractere– operatori, proceduri si functii predefinite pentru: citire, afisare, concatenare,căutare, extragere, inserare, eliminare si conversii (sir <-> valoare numerică)

declararea: var  v:string;sauvar  v:string[lmax];lmax=numărul maxim de caractere al şirului v;Citirea unei variabile de tip string se face cu read(v), afişarea ei cu write(v). Caracterele din care este formată variabila pot fi prelucrate una câte una (v[1], v[2],…,v[n]). Lungimea variabilei (numărul de caractere poate fi aflat cu ajutorul funcţiei length(v).

 Operatori, proceduri si functii predefinite pentru citire, afisare, concatenare,

cautare, extragere, inserare, eliminare si conversii (sir<-> valoare numerica)

Pos (function)

Caută într-un string un substring.Declararea: function Pos(Substr: String; S: String): Byte;Exemplu:writeln(pos(’ana’, ’ioana’); => 3writeln(pos(’Ana’, ’ioana’); => 0 Delete

Şterge un substring dintr-un string. Declararea: procedure Delete(var S: String; Index: Integer; Count:Integer); Exemplu: s:= ’Ana Maria’);delete(s,3,2);writeln(s);=> AnMaria

  Concat (function)

Concatenează mai multe stringuri. Declararea: function Concat(s1 [, s2,..., sn]: String): String;

23/66

Page 24: Recapitulare Bac Informatica

writeln(concat(’ana’+’maria’)) => afişează anamaria

 Copy (function)

 Returnează un substring dintr-un string.  Declararea: function Copy(S: String; Index: Integer; Count: Integer): String;ex.s:=copy(’ana maria’,3,4);writeln(s); => a maInsert (procedure)

Inserează un substring într-un string.Declararea:procedure Insert(Source: String; var S: String; Index: Integer);Exemplu: s:= ’ana maria’;insert(’corina’,s,4); =>anacorina maria  Length (function)

 Returnează numărul de caractere pe care le conţine un string.  Declararea: function Length(S: String): Integer;  UpCase (function)

Transformă litera mică în majusculă. Declararea: function UpCase(Ch: Char): Char;ex.s:= ’ana maria’;s[1]:=upcase(s[1]);writeln(s); => Ana maria

Probleme:

1. Se citeste o propozitie. Eliminati din ea literele a,b,c.

Rezolvare: uses crt;var s:string;beginclrscr;writeln('Introduceti o propozitie ');readln(s);while pos('a',s)<>0 do delete(s,pos('a',s),1);while pos('b',s)<>0 do delete(s,pos('b',s),1);while pos('c',s)<>0 do delete(s,pos('c',s),1);writeln;write(s);end.

24/66

Page 25: Recapitulare Bac Informatica

2.De la tastatura se citesc un numar n si n denumiri de orase. Scrieti aceste nume sub forma: prima litera mare, urmatoarele mici intr-un fisier cu numele órase.out’.

Rezolvare:uses crt;var a:array[1..100] of string; s:string; n,i:integer; f:text;beginclrscr;write('n=?');readln(n);for i:=1 to n do begin writeln('Introduceti numele unui oras '); readln(a[i]); end;for i:=1 to n do begin s:=a[i]; s[1]:=upcase(s[1]); a[i]:=s; end;assign(f,'orase.out');rewrite(f) ;for i:=1 to n do writeln(f,a[i]);close(f);

end.

4.3. Tipul înregistrare (articol)

Tipul înregistrare fixă - desemnează o structură formată dintr-un număr de component numite câmpuri.

In cadrul unui articol campurile pot fi de diferite tipuri, spre deosebire de vectori unde elementele au acelasi tip.

Sintaxa:V= record l1:tip1; l2:tip2; l3:tip3; … ln:tipn; end;

l1, l2, l3, … ln = liste de câmpuri;tip1, tip2, tip3,…tip n = tipurile câmpurilor din listele l1, l2, l3, …ln ;

Exemplu:a: record;

25/66

Page 26: Recapitulare Bac Informatica

sex, nume, culoareochi: char; h, g, v: integer; casatorit: Boolean; media: real; end;

Tipul unui câmp este oarecare, deci poate fi tot articol si se pot defini tipuri imbricate. Un nume de câmp trebuie sa fie unic numai în tipul articol în care a fost definit. Un câmp al unei variabile de tip articol este referit prin numele variabilei şi numele câmpului, separate printr-un punct.

Exemplu: read(a.nume); read (a.h, a.g, a.v); if a.v >=18 then write (‘ DA ‘) else write (‘ NU ‘);

4.3.1. Instrucţiunea WITH WITH c DO x

c= variabila de tip recordx= o singura instructiune

- Efect: in instructiunea x se adauga “ c. ” inaintea campurilor variabilei c- Este utilizata pentru a usura scrierea anevoioasa a calificarilor.

Exemplu:var a: record nume, prenume: string[30]; nota: integer;end;

…with a do begin

readln ( nume );readln ( prenume );readln ( nota );

end;

5. Fisiere text 5.1. Fisiere text. Tipuri de acces 5.2. Proceduri si functii predefinite pentru fisiere text

Sintaxa de declarare:

varf:text;     unde varf=variabila de tip fisier

assign(varf,numefis);   unde numefis= nume real al fisierului;

26/66

Page 27: Recapitulare Bac Informatica

    Efect: ataseaza variabilei varf fisierul cu numele numefis

reset(varf); -deschide pentru citire fisierul varf;

rewrite(varf); -deschide pentru scriere fisierul varf;

read(varf,v1,…vn); -citeste din fisierul varf valorile v1,…vn;

readln(varf,v1,…vn); -citeste din fisierul varf valorile v1,…vn si trece apoi la linie noua;

write(varf,e1,…,en); -scrie in fisierul varf valorile expresiilor e1,…en

writeln(varf,e1,…,en); -scrie in fisierul varf valorile expresiilor e1,…en si apoi trece la linie noua;

writeln(varf); -trece la linie noua in fisierul varf;

close(varf); -inchide fisierul varf.

Observatie importanta: din fisierele deschise pentru citire se poate doar citi, iar in cele deschise pentru rescriere se poate doar scrie. Probleme: 

1. Fie programul:

Var a,b,c,d:integer;f:text;

Begin

Assign(f,’date.in’);reset(f);

Readln(f,a,b);read(f,c);read(f,d);

Close (f);

Write(a);writeln(b);writeln(c,d);End.

Ce se va afisa pe ecran daca:

a)       fisierul contine:

2 3 4

5 6

27/66

Page 28: Recapitulare Bac Informatica

7 8

b)       fisierul contine:

2

4

6 7 8 9

2. Fie programul:

 

Var a,b,c,d:integer;f:text;

Begin

Assign(f,’a:\date.in’);rewrite(f);

Readln(a,b);read(c);read(d);

Write(f,a);writeln(f,b);writeln(c);writeln(f,d); Close (f);End.

Ce va contine fisierul daca se dau numerele urmatoare? Unde va fi el salvat?

a)

2 3 4

5 6

7 8

b)

2

4

6 7 8 9

6. Algoritmi elementari

28/66

Page 29: Recapitulare Bac Informatica

6.1. Probleme care operează asupra cifrelor unui număr

1. De la tastatura se citeşte un numar natural n .Afişaţi ultima cifră a numărului.Se observă că:- uc= ultima cifră a numărului; - n div 10 =numărul fără ultima cifrăuses crt;var n,uc:integer; p:integer;beginclrscr;read(n);uc:=n mod 10;n:=n div 10;writeln('ultima cifra este',uc);end.

2. Scrieţi un program pascal care calculează şi afişează suma cifrelor pare ale unui număr natural.

uses crt;var n,uc,s:integer; p:integer;beginclrscr;read(n);s:=0;repeatuc:=n mod 10;if uc mod 2=0 then s:=s+uc;n:=n div 10;until n=0;writeln('Suma cifrelor pare este',s);end.

3.Scrieţi un pascal care calculează cea mai mare şi cea mai mică cifră a unui număr natural dat.

uses crt;var n,max,uc,min:integer;beginclrscr;read(n);max:=0;min:=10;repeatuc:=n mod 10;if uc>max then max:=uc;if uc<min then min:=uc;n:=n div 10;until n=0;writeln('cea mai mare cifra este',max);writeln('cea mai mica cifra este',min);end.

29/66

Page 30: Recapitulare Bac Informatica

4.Se cunosc două numere.Aflaţi suma cifrelor lor.

uses crt;var a ,b,uc1,uc2,s,s1,s2:integer; p:integer;beginclrscr;read(a);read(b);s1:=0;s2:=0;repeatuc1:=a mod 10;s1:=s1+uc1;a:=a div 10;until a=0;repeatuc2:=b mod 10;s2:=s2+uc2;b:=b div 10;until b=0;s:=s1+s2;writeln('Suma celor doua numere este',s);end.

6.2. Divizibilitate. Numere prime. Algoritmul lui Euclid

Spunem că numărul natural a se divide cu d,dacă există un nr.c, astfel încât a=dxc.Ex:30 se divide cu nr.5, pentru ca există un nr.6,astfel încât 30=5x6.

Dacă d/a,atunci d se numeşte divizor al lui a şi a se numeşte multiplu al lui d.

Divizori proprii şi impropriiOrice nr.este divizibil prin 1 şi prin el însuşi.Nr.1 şi nr. însuşi se numesc divizori improprii.Ceilalţi divizori ai nr. se numesc divizori proprii.

Ex:D6={1;2;3;6}

1.Scrieţi un program pascal care calculează şi afişează produsul cifrelor divizibile cu 5 ale unui număr natural.

uses crt;var n,uc:integer; p:integer;beginclrscr;read(n);p:=1;repeatuc:=n mod 10;if uc mod 5=0 then p:=p*uc;n:=n div 10;until n=0;

30/66

Page 31: Recapitulare Bac Informatica

writeln('produsul cifrelor divizibile cu 5 este',p);end.

2.Verificaţi dacă un număr dat este perfect. Un număr este perfect dacă este egal cu suma divizorilor săi(exclusiv el). Ex: 6=1+2+3;

uses crt;var i,s,n:longint;beginclrscr;read(n);{25242}i:=1;s:=0;repeat if n mod i=0 then s:=s+i;i:=i+1;until i=n;if s=n then writeln('Nua=marul este perfect') else writeln('Numarul nu este perfect');end.

3. Calculaţi cel mai mare divizor a 2 numere naturale citite de la tastatură.Metoda 1:uses crt;var a,b,i ,min,x:integer;beginclrscr;read(a,b);if a<=b then min:=a else min:=b;for i:=1 to min doif (a mod i=0) and (b mod i=0) then x:=i;writeln('cel mai mare divizor comun este',x);end.

Numim număr prim orice nr.nat.mai mare decât 1,care are numai divizori improprii.Nr.prime sunt:2;3;5;7;11;13;17;19;23;29;31...Obs.:Singurul nr.prim şi par este 2.Pentru a afla daca un numar este prim sau nu, îl descompunem în factori primi,adica îl împărţim la toate nr.prime cu care este divizibil. Dacă este divizibil doar cu 1 si cu el însuşi,atunci nr. este prim.

Nr. prime între eleDouă numere care au cel mai mare divizor comun 1,se numesc numere prime între ele.Obs.:dacă a şi b sunt prime între ele, scriem:(a;b)=1Proprietate:Două numere consecutive sunt prime între ele.

1. Se citeşte un număr de la tastatură. Este el prim?

uses crt;var n,i,k:integer;begin

31/66

Page 32: Recapitulare Bac Informatica

clrscr;read(n);k:=0;for i:=2 to n-1 doif n mod i=0 then k:=k+1;if k=0 then writeln('Numarul este prim') else writeln('Numarul nu este prim');

end.

2.Descompunerea unui numar natural în două numere naturale prime distincte între ele.

uses crt; var k,n,a,d,j,b,i:integer;beginclrscr;read(n);k:=0;for i:=2 to n div 2 do begin {verificam daca i este prim} a:=0; for j:=2 to i-1 do if i mod j =0 then a:=1 ; if a=0 then begin b:=n-i; {verificam daca b este prim} d:=0; for j:=2 to b-1 do if b mod j=0 then d:=1 ; if d=0 then if i<>b then begin writeln(i,' ',b); k:=1; end; end; end; if k=0 then write('nu exista solutie');end.

Algoritmul lui Euclid este o metodă eficientă de calcul al celui mai mare divizor comun(CMMDC).CMMDC al două numere este cel mai mare număr care le divide pe ambele. Algoritmul lui Euclid se bazează pe principiul că cel mai mare divizor comun al două numere nu se modifică dacă numărul cel mai mic este scăzut din cel mai mare. De exemplu, 21 este CMMDC al numerelor 252 şi 105 (252 = 21 × 12; 105 = 21 × 5); întrucât 252 − 105 = 147, CMMDC al lui 147 şi 105 este tot 21. Cum cel mai mare dintre cele două numere este redus, repetarea acestui proces dă numere din ce în ce mai mici, până când unul dintre ele este 0. Când se întâmplă aceasta, CMMDC este celălalt număr, cel nenul. Inversând paşii algoritmului lui Euclid, CMMDC se poate exprima sub formă de celor două numere iniţiale, fiecare înmulţite cu un întreg pozitiv sau negativ, de exemplu: 21 = 5 × 105 + (−2) × 252.

32/66

Page 33: Recapitulare Bac Informatica

Algoritmul lui Euclid calculează eficient CMMDC a două numere oricât de mari sunt, deoarece nu necesită niciodată mai mult decât de cinci ori numărul de cifre (în bază 10) al celui mai mic întreg.Exemple:28 28 : 49=0 rest 2849 49 : 28=1 rest 21 28 : 21=1 rest 7 21 : 7 =3 rest 0 d.c= 7(ultimul rest ≠ 0)

a b c 36 : 42= 0 rest 36 b c 42 : 36= 1 rest 6 36 : 6= 6 rest 0 d.c= 6

24 24 : 17= 1 rest 717 17 : 7=2 rest 3 7 : 3=2 rest 1 3 : 1=3 rest 0 d.c=1

1. Calculaţi cel mai mare divizor comun si cel mai mic multiplu comun a 2 numere naturale citite de la tastatură.Metoda II: uses crt;var a,b,i ,min,x,c,cmmmc,cmmdc,p:integer;beginclrscr;read(a,b);repeatc:=a mod b;a:=b;b:=c;until c=0;cmmdc:=a;p:=a*b;cmmmc:=p div cmmdc;writeln('cel mai mic multiplu comun este',cmmmc);writeln('cel mai mare divizor comun este',cmmdc);end.

6.3. Sirul lui Fibonacci. Calculul unor sume cu termenul general dat

Şirul lui Fibonacci este o secvenţă de numere în care fiecare număr se obţine din suma precedentelor două din şir. Astfel, primele 10 numere ale şirului lui Fibonacci sunt:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...(primele 2 numere sunt predefinite, iar restul se obţin în mod recursiv, din suma precedentelor două: 3 = 2 + 1, 5 = 3 + 2 ...) 

Afişaţi primii n termeni ai şirului lui Fibonacci:

33/66

Page 34: Recapitulare Bac Informatica

uses crt;

var a,b,c,i,n:integer;

begin clrscr;

a:=0;

b:=1;

writeln('Cate elemente din sirul lui Fibonacci doriti sa fie afisate?');

read(n);

write(a,' ',b);

for i:=3 to n do begin c:=a+b;

write(' ',c);

a:=b;

b:=c;

end;

end.

Date de intrare: n=10

Date de ieşire: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Pentru un număr natural n dat să se calculeze expresia:

S= 1²+ 4²+ 7²+ …+ (3n-2)²

uses crt;

var a:array[1..100] of longint;

n,i,s:integer;

begin clrscr;

writeln('Care este valoarea lui n?');

read(n);

34/66

Page 35: Recapitulare Bac Informatica

for i:=1 to n do a[i]:=(3*i-2)*(3*i-2);

s:=0;

for i:=1 to n do s:=s+a[i];

writeln('Valoarea expresiei s este:',s);

end.

Date de intrare: n= 10

Date de ieşire: s= 2845

6.4. Determinare minim/maxim

Se dă un vector cu n elemente citite de la tastatură. Calculaţi maximul si minimul elementelor din vector.ă

program minmax;

var a:array[1..100] of integer;

n,i,min,max:integer;

begin

writeln('Cate elemente are vectorul?');

read(n);

writeln('Introduceti elementele vectorului!');

for i:=1 to n do

read(a[i]);

min:=a[1];

max:=a[1];

for i:=1 to n do

begin

if a[i]>max then max:=a[i];

if a[i]<min then min:=a[i];

end;

35/66

Page 36: Recapitulare Bac Informatica

writeln('Maximul elementelor din vector este ',max,' iar minimul este ',min,'.');

end.

6.5. Metode de ordonare (metoda bulelor, inserŃiei, selectiei, numărării)

Prin metoda bulelor se verifică două câte două toate elementele din vector şi dacă nu sunt ordonate corespunzator le interschimbăm.

Ex: 4 → 3 → 3 → 3 → 2 3 4 4 2 3 5 5 2 3 3 6 2 3 4 4 2 3 5 5 5 3 6 6 6 6 7 7 7 7 7 8 8 8 8 8

Pentru a ordona crescător un vector cu n elemente folosim programul urmator:

uses crt;

var a:array[1..100] of integer;

c,n,i:integer;

ok:boolean;

begin clrscr;

write('Cate elemente sunt in vector?');

read(n);

writeln('Introduceti elementele vectorului');

for i:=1 to n do read(a[i]);

writeln('Vectorul neordonat este:');

writeln;

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

repeat

ok:=true;

36/66

Page 37: Recapitulare Bac Informatica

for i:=1 to n-1 do if a[i]>a[i+1] then begin

c:=a[i];

a[i]:=a[i+1];

a[i+1]:=c;

ok:=false;

end;

until ok=true;

writeln;

writeln('Vectorul ordonat este:');

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

end.

Sortarea prin inserţie seamănă oarecum cu sortarea prin selecţie. Tabloul este împărţit imaginar în două părţi- o parte sortată şi o parte nesortată. La început, partea sortată conţine primul element al tabloului şi partea nesortată conţine restul tabloului. La fiecare pas, algoritmul ia primul element din partea nesortată şi îl inserează în locul potrivit al părţii sortate. Când partea nesortată nu mai are niciun element, algoritmul se opreşte.

Ex: Să ordonăm vectorul: 7, -5, 2, 16, 4 folosind sortarea prin inserţie.

7, -5, 2, 16, 4  nesortat

7, -5, 2, 16, 4  -5 va fi inserat 7 > -5 , schimbăm-5, 7, 2, 16, 4  2 va fi inserat 7 > 2, schimbăm-5, 2, 7, 16, 4  -5 < 2 , 2 ramâne pe loc-5, 2, 7, 16, 4  16 va fi inserat, 7 < 16, 16 ramâne pe loc-5, 2, 7, 16, 4  4 va fi inserat, 4 < 16, schimbăm-5, 2, 7, 4, 16  4 < 7 , schimbăm-5, 2, 4, 7, 16  ordonat

Pentru a ordona crescător un vector cu n elemente folosim programul urmator:

uses crt;

var a:array[1..100] of integer;

i,j,n,x,k:integer;

begin clrscr;

writeln('Cate numere sunt in vector?') ;

read(n);

for i:=1 to n do read(a[i]);

37/66

Page 38: Recapitulare Bac Informatica

j:=1;

repeat j:=j+1;

for i:=1 to j do if a[j]<a[i] then begin

x:=a[j];

for k:=j downto i+1 do a[k]:=a[k-1];

a[i]:=x;

i:=j;

end;

until j=n;

writeln('Vectorul ordonat este:');

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

end.

Ordonarea prin selecţie (metoda munimului). Vectorul este împărţit în două părţi imaginare- o parte sortată şi o parte nesortată. La început, partea sortata este goală, în timp ce partea nesortată conţine întreg tabloul. La fiecare pas, algoritmul găseşte elementul minim din partea nesortată şi îl adaugă la finalul părţii sortate. Când partea nesortată rămâne goală, algoritmul se opreşte.

Ex: Să ordonăm vectorul: 5, 1, 12, -5, 16, 2, 12, 14 utilizând sortarea prin selecţie.5, 1, 12, -5, 16, 2, 12, 14  nesortat5, 1, 12, -5, 16, 2, 12, 14  interschimbăm 5 cu -5 (partea sortata este - 5, partea nesortată este 1, 12, 5, 16, 2, 12, 14)-5, 1, 12, 5, 16, 2, 12, 14  1 rămâne pe poziţie (partea sortată este -5, 1, partea nesortată este 12, 5, 16, 2, 12, 14)-5, 1, 12, 5, 16, 2, 12, 14  interschimbăm 2 cu 12 (partea sortată este -5, 1, 2, partea nesortată este 5, 16, 12, 12, 14)-5, 1, 2, 5, 16, 12, 12, 14  5 rămâne pe poziţie (partea sortată este -5, 1, 2, 5, partea nesortată este 16, 12, 12, 14)-5, 1, 2, 5, 16, 12, 12, 14  interschimbăm 16 cu 12 (partea sortată -5, 1, 2, 5, 12 ,12, partea nesortată 16, 14)-5, 1, 2, 5, 12, 12, 16, 14  interschimbăm 16 cu 14 (ajungem la partea sortată -5, 1, 2, 5, 12, 12, 14, 16 şi partea nesortată este goală, algoritmul se opreşte)-5, 1, 2, 5, 12, 12, 14, 16  sortat

uses crt;

var a:array[1..100] of integer;

i,n,j,c,poz,min:integer;

begin clrscr;38/66

Page 39: Recapitulare Bac Informatica

write('Cate elemente sunt in vector?');

read(n);

writeln('Introduceti elementele');

for i:=1 to n do read(a[i]);

for i:=1 to n do begin

min:=a[i];

poz:=i;

for j:=i to n do if min>a[j] then begin

min:=a[j];

poz:=j;

end;

if a[poz]<>a[i] then begin

c:=poz;

a[poz]:=a[i];

a[i]:=c;

end;

end;

writeln('Vectorul ordonat este:');

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

end.

Metoda de sortare prin numărare constă în construirea unui nou vector care are aceeaşi dimensiune ca şi vectorul iniţial. Vom analiza fiecare element din primul vector şi îl vom compara cu fiecare alt element din şir pentru a putea reţine în al doilea vector numărul elementelor care sunt mai mici decât elementul considerat, astfel vom afla poziţia pe care trebuie să-l punem pe acesta.

Programul Pascal de ordonare:

uses crt;

var a,b,c:array[1..100] of integer;

k,i,x,n:integer;

39/66

Page 40: Recapitulare Bac Informatica

begin clrscr;

write('Cate elemente sunt in vector?');

read(n);

writeln('Introduceti elementele vectorului');

for i:=1 to n do read(a[i]);

k:=0;

repeat

k:=k+1;

x:=0;

for i:=1 to n do

if a[k]>a[i] then x:=x+1;

b[k]:=x;

until k=n;

for i:=1 to n do b[i]:=b[i]+1;

x:=0;

repeat

x:=x+1;

for i:=1 to n do if b[i]=x then c[x]:=a[i];

until x=n;

writeln;

writeln('Vectorul ordonat este:');

for i:=1 to n do write(c[i],' ');

end.

6.6. Interclasare Interclasarea a 2 vectori sortati deja crescator, intr-un al treila vector astfel incat acesta sa ramana tot sortat.var a,b,c:array[1..20] of integer;    i,n,j,k,x,y,m:integer;begin

40/66

Page 41: Recapitulare Bac Informatica

 write('m=');readln(m); for i:=1 to m do      begin         write('a[',i,']=');         readln(a[i]);      end; write('n=');readln(n); for i:=1 to n do      begin         write('b[',i,']=');         readln(b[i]);      end; i:=1; j:=1; k:=1; while (i<=m) and (j<=n) do      begin        if a[i]<b[j] then            begin                c[k]:=a[i];                i:=i+1;            end        else            begin                c[k]:=b[j];                j:=j+1;            end;        k:=k+1;     end; if i<=m then for x:=i to m do      begin        c[k]:=a[x];        k:=k+1;      end; if j<=n then for y:=j to n do      begin        c[k]:=a[y];        k:=k+1;      end; for i:=1 to n do write(c[i],' '); readln;end.

6.7. Metode de căutare (secventială, binară)

Căutarea secvenţială are avantaje şi dezavantaje. Unul din avantajele cautării secvenţiale il reprezinta faptul că vectorul nu trebuie ordonat crescător pentru a putea gasi numarul căutat. Un dezavantaj il reprezinta numărul de operaţii mari care trebuie effectuate pentru căutarea numarului in cazul in care vectorul ar avea dimensiuni mari iar numarul ar fi situat la sfarsitul acestuia.

De la tastatură se citeste un vector de n elemente şi un număr m. Aflaţi dacă numărul se găseste in vector si afisaţi un mesaj corespunzator.

var a:array[1..100] of integer;41/66

Page 42: Recapitulare Bac Informatica

n,i,m:integer;ok:boolean;

begin

writeln('Cate elemente are vectorul?');

read(n);

writeln('Introduceti elementele vectorului!');

for i:=1 to n do

read(a[i]);

writeln('Care este numarul pe care il cautati?');

read(m);

ok:=false;

for i:=1 to n do

if a[i]=m then ok:=true;

if ok then writeln('Numarul cautat de dumneavoastra a fost gasit!')

else writeln('Numarul cautat de dumneavoastra nu a fost gasit!');

end.

Cautarea binară. Pentru a aflat dacă un număr se gaseste sau nu intr-un vector folosind metoda cautarii binare vectorul trebuie ordonat crescator.

De la tastatură se citeste un vector cu n elemente ordonate crescător şi un numar m. Aflaţi dacă numărul se afla in vector şi afisaţi un mesaj corespunzator.

uses crt;

var a:array[1..100] of integer;

n,i,m,c,p:integer;ok:boolean;

function poz(i,j,m:integer):integer;

var mijl:integer;

begin

if i=j then if a[i]=m then poz:=i

else poz:=0

else begin42/66

Page 43: Recapitulare Bac Informatica

mijl:=(i+j) div 2;

if m<a[mijl] then poz:=poz(i,mijl,m)

else if a[mijl]=m then poz:=mijl

else poz:=poz(mijl+1,j,m);

end;

end;

begin

clrscr;

writeln('Cate elemente are vectorul?');

read(n);

writeln('Introduceti elementele vectorului!');

for i:=1 to n do

read(a[i]);

writeln('Care este numarul pe care il cautati?');

read(m);

p:=poz(1,n,m);

if p=0 then writeln('Nr. cautat nu se gaseste in vector.')

else writeln('Nr cautat se gaseste in vector.');

end.

6.8 Analiza complexităţii (considerând criteriile de eficienţă durata de executare şi spaţiu de memorie utilizat)

7. Subprograme definite de utilizator

7.1 Proceduri şi funcţii

Scrierea programului se face mult mai uşor dacă împărţim problema în subprobleme relativ independente, pentru fiecare din ele scriindu-se programe mult mai simple. De altfel, realizarea unui program de complexitate mare impune organizarea unor date şi a acţiunilor la care acestea trebuie supuse sub formă de subprograme.

Subprogramele limbajului Pascal sunt de două tipuri: proceduri funcţii.

43/66

Page 44: Recapitulare Bac Informatica

Diferenţa dintre ele constă în numărul valorilor calculate şi returnate programului apelant.

Atât procedurile cât şi funcţiile pot fi de două tipuri: standard (predefinite); nestandard (declarate în program).

Procedurile şi funcţiile nestandard trebuie obligatoriu declarate înainte de a fi apelate. In cazul general, un program Pascal e format dintr-un program principal şi dintr-un număr oarecare de proceduri şi funcţii apelabile din programul principal sau unele din altele.

Declarare şi apel

Declararea unei proceduri:procedure nume[([var] l1:tip1[;[var] l2:tip2….])];l1, l2,..., ln = lista parametrilor formali.

Apelul unei proceduri:nume (la1,la2,…,lan);la1,…,lan = lista parametrilor efectivi (actuali).

Declararea unei funcţii:function nume[([var] l1:tip1[;[var] l2:tip2….])]tip;l1, l2,..., ln = lista parametrilor formali.

Apelul unei funcţii:nume(la1,la2,...,lan);la1,…,lan = lista parametrilor efectivi (actuali).

parametrii actuali şi cei formali trebuie să corespundă în număr, tip şi ordine; dacă lista parametrilor formali este vidă, atunci sau nu există schimb de informaţii cu restul

programului, sau schimbul se execută prin intermediul variabilelor globale; spre deosebire de proceduri, funcţiile returnează ele însele un rezultat. În cadrul definirii

funcţiei, numele funcţiei poate apărea în stânga semnului egal. Ultima apariţie de acest fel returnează rezultatul funcţiei. Funcţia poate fi apelată în cadrul unor expresii (write, atribuire) în cadrul programului apelant.

Clasificarea parametrilor unei proceduri:a) După tipul parametrilor:

parametrii actuali; parametrii formali.

b) După modul de transmitere: parametrii transmişi prin valoare :

- sublista lor nu este precedată de nici un cuvânt cheie (VAR); - aceşti parametri pot fi modificaţi în corpul procedurii dar valorile noi nu se

transmit către blocul apelant, ei sunt doar parametri de intrare;

44/66

Page 45: Recapitulare Bac Informatica

- sunt asemanatori unor constante (îsi pot modifica valoarea în timpul execuţiei procedurii, dar revin la valoarea anterioară la ieșirea din execuţia procedurii);

parametri transmişi prin referinţă: - sublista lor este precedată de cuvântul cheie VAR, iar parametri actuali sunt

variabile;- aceşti parametri pot fi modificaţi în corpul procedurii, ei sunt parametri de

ieşire, nu sunt transmişi prin valoare ci se transmite adresa lor, deci în blocul apelant valorile parametrilor actuali vor fi modificate.

Proceduri şi funcţii predefinite

1. Funcţii de transformare: Function trunc(x:real):longint; - rezultatul e int(x) daca x>0 si int(x)+1 daca x<0;

trunc(-2.3)=-2;trunc(2.7)=+2;

Function round(x:real):longint;round(2.3)=2;round(2.6)=3;

2. Funcţii matematice: Function int(x:real):real; Function frac(x:real):real; Function sin(x:real):real; Function cos(x:real):real; Function arctan(x:real):real; Function pi; Function sqrt(x:real):real; Function ln(x:real):real; Function exp(x:real):real; Function abs(x); Function sqr(x);

3. Proceduri și funcţii referitoare la valori ordinale: Function succ(x); Procedure inc(var x[;n:longint]); incrementeaza x de n ori; Function pred(x); Procedure dec(var x[;n:longint]); decrementeaza x de n ori; Function odd(x:longint):Boolean; returneaza true daca x e impar, false in caz contrar;

4. Subprograme destinate tratării șirurilor: Delete Insert Str Val Concat Copy Length Pos

5. Proceduri de interes general:

Random + Randomize + Upcase

Variabile globale si variabile locale, domeniu de vizibilitate

45/66

Page 46: Recapitulare Bac Informatica

Varibilele globale sunt variabilele programului principal.Ele sunt rezervate intr-o zona speciala de date, numita segment de date.

Variabilele locale sunt variabile declarate in interiorul subprogramelor.Aceste variabile sunt memorate in segmentul de stiva dupa variabilele generate de parametri.Este sarcina programatorului sa asigure initializarea lor cu valorile dorite.La iesirea din subprogram continutul variabilelor locale se pierde.

Un termen des folosit in practica limbajelor de programare este acela de vizibilitate.A preciza vizibilitatea unei variabile inseamna a spune care sunt blocurile de unde se poate adresa(ca sa-i atribuim o valoare de exemplu).

Variabilele globale sunt vizibile la nivelul programului principal si la nivelul subprogramelor.

Variabilele locale sunt vizibile doar la nivelul subprogramului in care au fost declarate si la nivelul subprogramelor definite in acesta..

Atentie! Exista situatii in care o variabila globala nu poate fi adresata din cadrul subprogramului, adica atunci cand acesta contine declaratia unei alte variabile, cu acelasi nume.In acest caz, prin nume, se adreseaza variabila locala.Regula este urmatoarea: in cazul in care doua variabile au acelasi nume, dar vizibilitati diferite, se adreseaza intotdeauna variabila cu vizibilitatea mai redusa.Evident, in cazul existentei a doua variabile cu aceeasi vizibilitate si acelasi nume, compilatorul va da eroare de sintaxa.

7.2 Proiectarea modulară a rezolvării unei probleme

46/66

Page 47: Recapitulare Bac Informatica

Procedurile şi funcţiile nestandard trebuie obligatoriu declarate înainte de a fi apelate. In cazul general, un program Pascal e format dintr-un program principal şi dintr-un număr oarecare de proceduri şi funcţii apelabile din programul principal sau unele din altele.

Domeniul de vizibilitate al identificatorilor (elemente locale şi globale)

Declararea procedurilor în cadrul altor proceduri, fiecare din acestea cu propriile declaraţii şi definiţii ridică o problemă deosebită: domeniul de vizibilitate al identificatorilor.

          Prin domeniul de vizibilitate  (de valabilitate) înţelegem zona de program în care este cunoscută declaraţia sau definiţia unui identificator.

          Când fluxul de control intră într-un bloc, toate entităţile declarate în blocul respectiv sunt alocate pe stiva de execuţie; la părăsirea unui bloc zona de pe stivă alocată blocului este eliberată astfel încât valorile aflate acolo nu mai pot fi referite.

          Subprogramele pot fi recursive, adică se pot  apela ele însele, fie direct, fie indirect printr-un lanţ de apeluri.  Fiecare apelare a unui subprogram determină alocarea de spaţiu pe stivă pentru entităţile sale locale care sunt astfel distincte de entităţile corespunzătoare alocate în timpul altor apeluri ale aceleiaşi proceduri. Acest spaţiu este eliberat la terminarea apelării respective.

Concluzie: domeniul de vizibilitate al unui identificator este tot blocul în care acesta a fost definit, inclusiv blocurile subprogramelor decarate în bloc, cu excepţia celor care redefinesc identificatorul.

Dezvoltarea ascendentă şi dezvoltarea descendentă a programelor

In Pascal există două posibilităţi de dezvoltare a programelor:

a)      ascendentă;

b)      descendentă.

a)In programarea ascendentă subprogramele se declară în secţiunea de declaraţii a programului. Regulă generală: referirea identificatorilor numai după declararea lor. Blocurile sunt în acest caz independente. Apeluri posibile:

-          din programul principal se poate apela orice subprogram, în orice ordine;

-          dip subprogramul_i se pot apela subprogramele anterioare, în orice ordine;

 b)In programarea descendentă subprogramele se declară imbricate unul în celălalt. Apeluri posibile:

-          din programul principal se poate apela subprogramul_1;

-          din subprogramul_i se poate apela subprogramul_i+1;

In practică programarea ascendentă şi cea descendentă sunt combinate.

8. Recursivitate

47/66

Page 48: Recapitulare Bac Informatica

8.1 Prezentare generală

Un program este recursiv atunci când se autoapelează. Pentru ca autoapelul sa nu aibă loc la infinit un program recursiv trebuie să conţină o condiţie de oprire (de sfârşit).

8.2 Funcţii şi proceduri recursive

Exemple de funcţii şi proceduri recursive:

procedure P( x: integer);begin If x< >0 then if x mod 2=0 then begin

write (x) ; P (x div 2 ) end else begin

P (x-1) ; write (x) endend;

procedure f(i, k: integer) ; beginif k<=4 then begin

write (i*k) ;f (i-1 , k+1)

end;end;

function f (a, b:integer):byte;begin

if b<1 then f : = -1;else

if a mod b =0 then f:=1+f(a div b,b); else f:= 0;

end;

procedure f (n:longint);begin

write(n mod 10);if n<>0 then begin

f(n div 100); write(n mod 10); end

end;

Mai jos este verificarea procedurii anterioare :

48/66

Page 49: Recapitulare Bac Informatica

9. Metoda backtracking

9.1. Prezentare generală

Metoda backtracking este o metodă de rezolvare a problemelor prin încercări. Soluţia problemelor constă în determinarea unor valori ce îndeplnesc anumite condiţii.

Această metodă încearcă la fiecare pas alegerea unei valori dintre cele posibile. Dacă valoarea încercată îndeplineşte condiţiile problemei, atunci vom trece la pasul următor. Dacă valoarea nu îndeplineşte condiţiile, vom rămâne la acelaşi pas şi vom încerca altceva într-o ordine stabilită la începutul rezolvării problemei. Dacă nu mai avem de unde alege valori, ne vom întoarce la pasul anterior.

Dacă încercând să rezolvăm problema ne vom întoarce la pasul 0, va însemna că am determinat toate soluţiile sau că problema nu are rezolvare.            De multe ori, în aplicaţii apar probleme în care se cere gǎsirea unor soluţii de forma x=x1x2... xn unde xi A, i = 1,…,n în care x1…xn trebuie sǎ îndeplineascǎ anumite condiţii.            Am putea sǎ generǎm toate combinaţiile posibile de valori şi apoi sǎ le alegem doar pe cele convenabile. Considerând mulţimile A = {ai,1,ai,2,…,ai,n(i)}, aceste combinaţii s-ar putea construi astfel: pentru fiecare valoare posibilǎ fixatǎ pentru componenta xi, vom alege  toate valorile posibile pentru componenta xi+1 şi pentru fiecare astfel de valoare fixatǎ pentru xi+1  vom alege toate valorile posibile pentru componenta xi+2, etc.            Rezolvând problema în acest mod, deci generînd tote elementele produsului cartezian  şi verificând abia apoi dacǎ fiecare combinaţie este o soluţie, eficientǎ este scǎzutǎ.            Astfel, dacǎ de exemplu ne propunem sǎ generǎm toate cuvintele formate cu litere a,b,c, aşa încât fiecare literǎ sǎ aparǎ o singurǎ datǎ, combinaţiile posibile sunt în numǎr de 27, dintre care convin doar 6.

49/66

Page 50: Recapitulare Bac Informatica

            Tehnica Backtracking propune generarea soluţiei prin completarea vectorului x în ordine x1x2... xn şi are la bazǎ un principiu “de bun simţ”: dacǎ se constatǎ cǎ având o combinaţie parţialǎ de formǎ v1v2...v k-1 (unde vi,…,vk-1 sunt valori deja fixate), dacǎ alegem pentru xk o valoare vk şi combinaţia rezultatǎ nu ne permite sǎ ajungem la o soluţie, se renunţǎ la aceastǎ valoare şi se încearcǎ o alta (dintre cele netestate în aceastǎ etapǎ). Într-adevǎr, oricum am alega celelalte valori, dacǎ una nu corespunde nu putem avea o soluţie.            Pentru exemplu ales anterior se observǎ cǎ dacǎ notǎm cuvântul cu x1x2x3, combinaţia aax3 nu ne poate conduce la o soluţie (literele trebuie sǎ fie distincte) şi deci nu are sens sǎ mai încercǎm sǎ stabilim valori pentru x3.            Algoritmul general al metodei Backtracking            Pentru evitarea generǎrii combinaţiilor neconvenabile se procedeazǎ astfel:            Presupunem cǎ s-au gǎsit valorile v1v2…vk-1 pentru componentele x1x2... xk-1 (au rǎmas de determinat valorile pentru xk…xn). Ne ocupǎm în continuare de componenta xk. Paşii urmaţi sunt:1) Pentru început, pentru xk nu s-a testat încǎ nici o valoare.2) Se verificǎ dacǎ existǎ valori netestate pentru xk .

a) În caz afirmativ, se trece la pasul 3.b) Altfel, se revine la componenta anterioarǎ, xk-1; se reia pasul 2 pentru k=k-1.

3) Se alege prima valoare v dintre cele netestate încǎ pentru xk.4) Se verificǎ dacǎ acestǎ combinaţie parţialǎ v1v2…vk-1v ne poate conduce la un rezultat (dacǎ sunt

îndeplinite anumite condiţii de continuare).a) Dacǎ valoarea aleasǎ este bunǎ se trece la pasul 5.b) Altfel, se rǎmâne pe aceeaşi poziţie k şi se reia cazul 2.

5) Se verificǎ dacǎ s-a obţinut o soluţie .a) În caz afirmativ, se tipǎreşte aceastǎ soluţie şi se rǎmâne la aceeaşi componentǎ xk, reluându-

se pasul 2.b) Altfel se reia altgoritmul pentru urmǎtoarea componentǎ (se trece la pasul 1 pentru k=k+1).

Altgoritmul începe prin stabilirea unei valori pentru componenta x1(k=1) şi se încheie când pentru aceasta am testat toate valorile posibile şi conform pasului 2b) ar trebui sǎ revenim la componenta anterioarǎ, care în aceast caz nu existǎ.Rezumând, metoda Backtracking se foloseşte în rezolvarea problemelor care îndeplinesc condiţiile:

soluţia poate fi pusǎ sub forma unui vector S=x1x2…xn, unde xi

mulţimile Ai sunt finite şi ordonate (pentru a lua în considerare toate valorile posibile).

Înainte de a scrie programul care ne va obţine soluţiile, trebuie sǎ stabilim unele detalii cu privire la:

vectorul soluţie – câte componente are, ce menţine fiecare componentǎ. mulţimea de valori posibile pentru fiecare componentǎ (sunt foarte importante limitele

acestei mulţimi). condiţiile de continuare (condiţiile ca o valoare x[k]sǎ fie acceptatǎ). condiţia ca ansamblul de valori generat sǎ fie soluţie.

 Pe baza acestor date vom scrie apoi procedurile şi funcţiile pe care le vom apela în altgoritmul general al metodei, dat mai jos, care se poate aplica tuturor problemelor ce respectǎ condiţiile menţionate anterior. Aceste proceduri şi funcţii au o semnificaţie comunǎ, prezentând însǎ particularitǎţi în funcţie de fiecare problemǎ în parte.

Astfel, se va nota cu x vectorul care conţine soluţia; x[k] = v  va avea ca semnificaţie faptul cǎ elementul al-v-lea din mulţimea de valori ppsibile Ak a fost selectat pentru componenta xk. dacǎ mulţimea Ak are m elemente,  a1a2…am,pentru uşurinţǎ ne vom referii la indicii lor 1,2,…,m. Deci valorile posibile pentru o componentǎ vor fi 1,2,…,m în aceastǎ ordine.

Iniţial, când pentru o componentǎ nu am testat încǎ nimic, aceasta va avea valoarea 0 (un indice care nu existǎ). Aceastǎ operaţie se va realiza în procedura INIT care va avea ce parametru poziţia k.

50/66

Page 51: Recapitulare Bac Informatica

Funcţia SUCCESOR(k) verificǎ dacǎ ultima valoare aleasǎ pentru componenta xk nu a atins limita maximǎ admisǎ (indicele de valoare maximǎ). Întrucât elementele sunt testate în ordine, acest lucru este echivalent cu a verifica dacǎ mai avem valori netestate încǎ pentru aceastǎ componentǎ.

Funcţia VALIDARE(k) verificǎ dacǎ valoarea aleasǎ pentru x[k] îndeplineşte condiţiile de continuare, deci dacǎ aceastǎ combinaţie parţialǎ v1v2…vk

  poate sǎ conducǎ la o soluţie.Funcţia SOLUTIE(k) verificǎ dacǎ s-a ajuns la o soluţie finalǎ.Procedura TIPAR(k) tipǎreşte o soluţie.

Şablonul metodei backtracking:

uses crt;type stiva=array[1..100] of integer;var st:stiva; k,n:integer; as,ev:boolean;

procedure init(k:integer;var st:stiva); begin ... end;

procedure succesor(k:integer;var st:stiva;var as:boolean);begin....end;

procedure validare(k:integer;st:stiva;var ev:boolean);begin...end;

function solutie(k:integer):boolean;begin...end;

procedure tipar;begin...end;

begin...{citirea datelor}

k:=1;init(k,st);while k>0 do begin repeat succesor(k,st,as); if as then validare(k,st,ev); until (not as) or (as and ev); if as then

51/66

Page 52: Recapitulare Bac Informatica

if solutie(k) then tipar else begin k:=k+1; init(k,st); end else k:=k-1; end;end.

9.2. Probleme de generare. Oportunitatea utilizării metodei backtracking

Problemele care se rezolvă prin metoda backtracking pot fi împărţite în mai multe grupuri de probleme cu rezolvări asemănătoare, in funcţie de modificările pe care le vom face în algoritm.

Principalele grupuri de probleme sunt:a) probleme în care vectorul soluţie are lungime fixă şi fiecare element apare o singură dată în soluţie;b) probleme în care vectorul soluţie are lungime variabilă şi fiecare element poate să apară de mai multe ori în soluţie;c) probleme în plan, atunci când spaţiul în care ne deplasăm este un tablou bidimensional. Vom prezenta în cele ce urmează câteva probleme care pac parte din primul grup. Cele mai cunoscute sunt: generarea permutărilor, aranjamentelor, combinărilor generarea submulţimilor unei mulţimi generarea produsului cartezian problema damelor pe tabla de şah colorarea ţărilor de pe o hartă astfel încât oricare două ţări vecine să aibă culori diferite problema labirintului problema calului pe tabla de şah problema plăţii unei sume de bani (bancomatul) problema grafului hamiltonian (problema comis-voiajorului)

Toate problemele din acest grup au particularitatea că soluţia se obţine atunci când vectorul soluţie ajunge să conţină un anumit număr de elemente.

Probleme: Considerând că avem o tablă de şah cu n linii şi n coloane, scrieţi programul care afişeză

Modurile în care pot fi aşezate n dame pe tablă astfel încât să nu existe două dame care să se atace reciproc (două dame se atacă în cazul în care sunt situate pe aceeaşi linie, coloană sau diagonală).

uses crt;type stiva=array[1..100] of integer;var st:stiva; k,n,l:integer; as,ev:boolean;

procedure init(k:integer;var st:stiva); begin st[k]:=0; end;

procedure succesor(k:integer;var st:stiva;var as:boolean);

52/66

Page 53: Recapitulare Bac Informatica

beginif st[k]<n then begin as:=true; st[k]:=st[k]+1; end else as:=false;end;

procedure validare(k:integer;st:stiva;var ev:boolean);var i:integer;beginev:=true;for i:=1 to k-1 dobeginif st[k]=st[i] then ev:=false;if abs(k-i)=abs(st[k]-st[i]) then ev :=false;end;end;

function solutie(k:integer):boolean;beginif k=n then solutie:=true else solutie:=false;end;

procedure tipar;var i:integer;beginfor i:=1 to n do write(i,'-',st[i],' ; ');writeln;end;

beginread(n);k:=1;init(k,st);l:=0;while k>0 do begin repeat succesor(k,st,as); if as then validare(k,st,ev); until (not as) or (as and ev); if as then if solutie(k) then begin tipar; inc(l); end else begin k:=k+1; init(k,st); end else

53/66

Page 54: Recapitulare Bac Informatica

k:=k-1; end;if l=0 then write('Damele nu pot fi aranjate.') else write('Damele pot fi aranjate in ',l,' moduri.');end.

Pentru generarea numerelor cu n cifre formate cu elementele mulPentru generarea numerelor

cu n cifre formate cu elementele muţimii {0,2,8} se utilizează un algoritm backtrackingcare, pentru n=2 generază în ordine numerele 20, 22,28,80,82,88.

uses crt;type stiva = array [1..100] of integer;var a, st : stiva; n, k : integer; as, ev : boolean;

procedure init (k : integer; var st : stiva);begin st[k]:=0;end;

procedure succesor (k : integer; var st : stiva; var as : boolean);begin if st[k]<3 then begin as:=true; st[k]:=st[k]+1; end else as:=false;end;

procedure validare (k : integer; st : stiva; var ev : boolean);begin ev:=true; if (k=1) and (a[st[k]]=0) then ev:=false;end;

function solutie (k : integer) : boolean;begin if k=n then solutie:=true else solutie:=false;end;

procedure tipar;var i:integer;begin for i:=1 to n do write (a[st[i]]); writeln;end;

begink:=1;read (n);a[1]:=0;

54/66

Page 55: Recapitulare Bac Informatica

a[2]:=2;a[3]:=8;init (k, st);while k<>0 do begin repeat succesor (k, st, as); if as then validare (k, st, ev); until (not as) or (as and ev); if as then if solutie (k) then tipar else begin k:=k+1; init (k, st); end else k:=k-1; end;end.

10. Generarea elementelor combinatoriale

10.1          Permutari, aranjamente, combinari

Metoda Backtracking se aplică problemelor în care soluţia poate fi reprezentată sub forma

unui vector – x = (x1, x2, x3, …xk,… xn) € S, unde S este mulţimea soluţiilor problemei şi S = S1 x

S2 x… x Sn, şi Si sunt mulţimi finite având s elemente si xi € si , (¥)i = 1..n.

Pentru fiecare problemă se dau relaţii între componentele vectorului x, care sunt numite

condiţii interne; soluţiile posibile care satisfac condiţiile interne se numesc soluţii rezultat. Metoda

de generare a tuturor soluţiilor posibile si apoi de determinare a soluţiilor rezultat prin verificarea

îndeplinirii condiţiilor interne necesită foarte mult timp.

Metoda backtracking evită această generare şi este mai eficientă. Elementele vectorului x, primesc pe rând valori în ordinea crescătoare a indicilor, x[k] va primi o valoare numai daca au fost atribuite valori elementelor x1.. x[k-1]. La atribuirea valorii lui x[k] se verifica îndeplinirea unor condiţii de continuare referitoare la x1…x[k-1]. Daca aceste condiţii nu sunt îndeplinite, la pasul k, acest lucru înseamnă ca orice valori i-am atribui lui x[k+1], x[k+1], .. x[n] nu se va ajunge la o soluţie rezultat.

APLICAŢII REZOLVATE

Exemple:

Generarea permutărilor. Se citeşte un număr natural n. Să se genereze toate permutările

mulţimii {1, 2, 3, …,n}.

Generarea permutărilor se va face ţinând cont că orice permutare va fi alcătuită din elemente

distincte ale mulţimii A. Din acest motiv, la generarea unei permutări, vom urmări ca numerele să

fie distincte.

Prezentăm algoritmul corespunzător cazului n=3:

1 2 3

55/66

Page 56: Recapitulare Bac Informatica

1 2 2 2 21 1 1 1 1 1

1 2 33 3 3 3 11 1 1 1 2 2

1 2 3 11 1 1 2 3 32 2 2 2 2 2

se încarcă în stivă pe nivelul 1 valoarea 1;

încărcarea valorii 1 pe nivelul al 2-lea nu este posibilă, întrucât această valoare se

găseşte şi pe nivelul 1 al stivei;

încărcarea valorii 2 pe nivelul al 2-lea este posibilă, deoarece această valoare nu mai este

întâlnită;

valoarea 1 din nivelul al 3-lea se regăseşte pe nivelul 1;

valoarea 2 din nivelul al 3-lea se regăseşte pe nivelul al 2-lea;

valoarea 3 pe nivelul al 3-lea nu e întâlnită pe nivelurile anterioare; întrucât nivelul 3

este completat corect. Tipărim: 1 2 3

……

Algoritmul continuă până când stiva devine vidă.

Metoda backtracking construieşte un vector soluţie în mod progresiv începând cu

prima componentă a vectorului şi mergând spre ultima cu eventuale reveniri asupra

atribuirilor anterioare.

Metoda se aplica astfel :

1) se alege prima valoare sin S1 si I se atribuie lui x1 ;

2) se presupun generate elementele x1…x[k-1], cu valori din S1..S[k-1]; pentru generarea lui

x[k] se alege primul element din S[k] disponibil si pentru valoarea aleasa se testează

îndeplinirea condiţiilor de continuare.

Pot apărea următoarele situaţii :

a) x[k] îndeplineşte condiţiile de continuare. Daca s-a ajuns la soluţia finală (k = n)

atunci se afişează soluţia obţinută. Daca nu s-a ajuns la soluţia finală se trece la

generarea elementului următor – x [k-1];

b) x[k] nu îndeplineşte condiţiile de continuare. Se încearcă următoarea valoare

disponibila din S[k]. Daca nu se găseşte nici o valoare în S[k] care să îndeplinească

condiţiile de continuare, se revine la elementul x[k-1] şi se reia algoritmul pentru o

56/66

Page 57: Recapitulare Bac Informatica

nouă valoare a acestuia. Algoritmul se încheie când au fost luate in considerare toate

elementele lui S1.

Problemele rezolvate prin această metodă necesită timp mare de execuţie, de aceea

este indicat sa se folosească metoda numai daca nu avem alt algoritm de rezolvare.

Dacă mulţimile S1,S2,…Sn au acelaşi număr k de elemente, timpul necesar de execuţie al

algoritmului este k la n. Dacă mulţimile S1, S2.. Sn nu au acelaşi număr de elemente, atunci se

notează cu „m” minimul cardinalelor mulţimilor S1…Sn si cu „M”, maximul. Timpul de execuţie

este situat în intervalul [m la n .. M la n]. Metoda backtracking are complexitatea exponenţială, in

cele mai multe cazuri fiind ineficientă. Ea insa nu poate fi înlocuită cu alte variante de rezolvare mai

rapide în situaţia în care se cere determinarea tuturor soluţiilor unei probleme.

Generarea aranjamentelor. Se citesc n şi p. Să se genereze toate aranjamentele de n luate

câte p.

Din analiza problemei rezultă următoarele:

stiva are înălţimea p;

fiecare nivel ia valori între 1 şi n;

elementele plasate pe diverse niveluri trebuie să fie distincte.

Algoritmul este asemănător cu cel de la permutări, cu deosebirea că aici stipa are înălţimea

p.

Generarea combinărilor. Se citesc n şi p numere naturale, np. Se cere să se genereze

toate submulţimile cu p elemente ale mulţimii {1, 2, 3, …, n}.

Pentru rezolvarea problemei trebuie ţinut cont de următoarele:

stiva are înălţimea p;

elementele aflate pe niveluri diferite ale stivei trebuie să fie distincte;

pentru a evita repetiţia elementele se aşează în ordine crescătoare: pe nivelul k se va afla o

valoare mai mare decât pe nivelul k-1 şi mai mică sau egală cu n-p+k.

57/66

Page 58: Recapitulare Bac Informatica

PERMUTARI ARANJAMENTE COMBINARI

program permutari;

type stiva=array[1..20] ofinteger;

   var st:stiva;

   n,k:integer;

   as,ev:boolean;

procedure init(k:integer;var st:stiva);

begin

st[k]:=0;

end;

procedure succesor (var as: boolean; var

st: stiva; k:integer);

begin

   if st[k]<n then

begin

st[k]:=st[k]+1;

as:=true;

end

else as:=false

end;

procedure valid (var ev:boolean;

st:stiva; k:integer);

var i:integer;

begin

ev:=true;

for i:=1 to k-1

do ifst[k]=st[i] then ev:=false

end;

function solutie(k:integer): boolean;

begin

solutie:=(k=n)

end;

procedure tipar;

var i:integer;

begin

for i:=1 to n do write (st[i]);

writeln;

end;

Begin

write (’n=’); readln(n);

k:=1; init (k,st);

while (k>0) do

   begin

      repeat

            succesor (as, st, k);

           if as then valid (ev,st,k);

      until (not as) or (asand ev);

if as then

if solutie (k) then tipar

else begin

program aranjamente;

type stiva=array[1..20] ofinteger;

   var st:stiva;

   n,k:integer;

   as,ev:boolean;

procedure init (k:integer;var st:stiva);

begin

st[k]:=0;

end;

procedure succesor (var as: boolean; var st: stiva;

k:integer);

begin

   if st[k]<n then

begin

st[k]:=st[k]+1;

as:=true;

end

else as:=false

end;

procedure valid (var ev:boolean; st:stiva;

k:integer);

var i:integer;

begin

ev:=true;

for i:=1 to k-1 do if st[k]=st[i]then ev:=false

end;

function solutie (k:integer): boolean;

begin

solutie:=(k=p)

end;

procedure tipar;

var i:integer;

begin

for i:=1 to p do write (st[i]);

writeln;

end;

Begin

write (’n=’); readln(n);write(’p=’);readln(p);

k:=1; init (k,st);

while (k>0) do

   begin

      repeat

            succesor (as, st, k);

           if as then valid (ev,st,k);

      until (not as) or (as andev);

if as then

if solutie (k) then tipar

else begin

k:=k+1;

program combinari;

type stiva=array[1..20] ofinteger;

   var st:stiva;

   n,k:integer;

   as,ev:boolean;

procedure init(k:integer;var st:stiva);

begin

st[k]:=0;

end;

procedure succesor (var as: boolean; var st:

stiva; k:integer);

begin

   if st[k]<n-p+k then

begin

st[k]:=st[k]+1;

as:=true;

end

else as:=false

end;

procedure valid (var ev:boolean; st:stiva;

k:integer);

var i:integer;

begin

ev:=true;

for i:=1 to k-1 do ifst[k]=st[i] then ev:=false

if k>1 then st[k]<st[k-1]then ev:=false

end;

function solutie(k:integer): boolean;

begin

solutie:=(k=p)

end;

procedure tipar;

var i:integer;

begin

for i:=1 to p do write (st[i]);

writeln;

end;

Begin

write (’n=’); readln(n);write(’p=’); readln(p);

k:=1; init (k,st);

while (k>0) do

   begin

      repeat

            succesor (as, st, k);

           if as then valid (ev,st,k);

      until (not as) or (as andev);

if as then

if solutie (k) then tipar

else begin

58/66

Page 59: Recapitulare Bac Informatica

k:=k+1;

init (k,st)

end

else k:=k-1

end

readln;

End.

init (k,st)

end

else k:=k-1

end

readln;

End.

k:=k+1;

init (k,st)

end

else k:=k-1

end

readln;

End.

10.2 Produsul cartezian .Submultimi.

Se dau mulţimile de mai jos şi se cere produsul cartezian al lor.

A1 = {1, 2, 3, …, k1}

A2 = {1, 2, 3, …, k2}

………………………

An = {1, 2, 3, …, kn}

Exemplu: A1 = {1, 2}

A2 = {1, 2, 3}

A3 = {1, 2, 3}

A1 A2 A3 = {(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 3, 1), (1, 3, 2),

(1, 3, 3), (2, 1, 1), (2, 1, 2), (2, 1, 3), (2, 2, 1), (2, 2, 2), (2, 2, 3), (2, 3, 1), (2, 3, 2), (2, 3, 3)}.

Pentru rezolvare, se folosesc stiva ST şi un vector A ce reţine numerele k1, k2, …kn. Utilizăm

metoda backtracking, uşor modificată din următoarele motive:

a) Orice element aflat la nivelul k al stivei este valid, motiv pentru care procedura valid nu

face altceva decât să atribuie variabilei ev valoarea TRUE.

b) 9

Modul de concepere a algoritmului rezultă din cele ce urmează:

1 2 3 1

1 1 1 2 2

1 1 1 1 1 1

2 3 1 2 3

2 2 3 3 3 3

1 1 1 1 1 1

……………………………………………………………………………

Observaţii:

59/66

Page 60: Recapitulare Bac Informatica

Algoritmul prezentat aici este de tip backtracking? Întrebarea are sens pentru că este

absent mecanismul de întoarcere. Vom admite că şi aceasta este backtracking, dar

„degenerat”.

Generarea submulţimilor unei mulţimi

Generarea submulţimilor unei mulţimi A cu n elemente se poate face cu ajutorul algoritmului de generare  a combinărilor, apelându-l repetat cu valorile 1, 2, ..., n pentru a genera submulţimile cu un element, apoi cele cu două elemente, apoi cu 3 elemente etc. Această modalitate de rezolvare este şi mai complicată şi mai puţin eficientă decât următoarea, care se bazează pe generarea produsului cartezian {0,1}n. Această a doua metodă este eficientă deoarece generează 2n soluţii, adică exact atâtea câte submulţimi are o mulţime cu n elemente.Aşadar, generăm toate combinaţiile de lungime n cu valorile 0 şi 1. Pentru fiecare combinaţie parcurgem soluţia X şi afişăm elementele din mulţimea A cărora le corespund valori 1 în X.  Astfel, pentru combinaţia 001011 vom afişa elementele de pe poziţiile 3, 5 şi 6 din mulţimea iniţială.

Generarea partiţiilor unei mulţimi

Generăm partiţiilor unei mulţimi presupune împărţirea mulţimii în mulţimi nevide şi disjuncte care reunite să dea întreaga mulţime. Putem, ca şi în cazurile anterioare, să considerăm mulţimea {1,2,…,n}. Construim un vector soluţie în care pentru fiecare element vom trece submulţimea în care îl vom include. Această submulţime mai este numită şi clasă. Algoritmul generează pe rând toate modalităţile de a împărţi elementele mulţimii {1,2,…,n} folosind mai întâi o singură clasă, apoi două, ş.a.m.d. până la n clase.

11.Grafuri

11.1Grafuri neorientate

Graf neorientat, adiacenta, incidenta, grad

Definitie:Se numeste graf neorientat, o pereche ordonata de multimi (X,U), unde:

-X este o multime finita, nevida, de elemente numite varfuri sau noduri;-U este o multime de perechi neordonate de cate doua elemente din X, numite muchii

sau arce.Asadar un graf neorientat poate fi reprezentat sub forma unei figuri geometrice alcatuita din

puncte (muchii, arce) si linii drepte sau curbe care unesc aceste puncte (muchii, arce). Respectand o anumita “traditie” pe care o gasim in literatura de specialitate, vom folosi:

- pentru grafuri neorientate termenii de “varf” si “muchie”- pentru grafuri orientate termenii de “nod” si “arc”

Pentru o muchie uk=(a,b), vom spune ca:- varfurile a si b sunt adiacente si se numesc extremitatile muchiei uk;

- muchia uk si varful a sunt incidente in graf. La fel, muchia uk si varful b;

60/66

Page 61: Recapitulare Bac Informatica

- muchia (a,b) este totuna cu (b,a) (nu exista o orientare a muchiei).

Definitie:Gradul unui varf x, notat d(x) reprezinta numarul muchiilor care trec prin nodul x (incidente

cu nodul x)Un varf care are gradul 0 se numeste varf izolatUn varf care are gradul 1 se numeste varf terminal

Teorema:Intr-un graf G=(X,U) cu n varfuri si m muchii, suma gradelor tuturor varfurilor este egala

cu 2*numarul muchiilor.

LanţDefinitie :Se numeste lant in graful G, o succesiune de varfuri L=(z1, z 2,...,zk), unde z1, z 2,...,zk X, cu

proprietatea ca oricare doua varfuri consecutive sunt adiacente, adica exista muchiile [Z1, Z 2], [Z2, Z 3],..., [Zk-1, Z k] U.

Varfurile zi si z k se numesc extremitatile lantului, iar numarul de muchii care intra in componenta lantului reprezinta lungimea lantului.

Un lant poate fi interpretat ca un traseu care pleaca din varful z1 si ajunge in varful zk, trecand prin mai multe varfuri si parcurgand mai multe muchii.

Daca varfurile z1, z2, ..., zk sunt distincte doua cate doua, lantul se numeste elementar. In caz contrar, lantul este ne-elementar.

Ciclu Se numeste ciclu intr-un graf, un lant L=(z1, z2, ... , zk) cu proprietatea ca z1=zk si muchiile

[z1, z2], [z2, z3], ... , [zk-1, zk] sunt distincte doua cate doua.Daca intr-un ciclu, toate varfurile cu exceptia primului si ultimului sunt distincte doua cate

doua, atunci ciclul se numeste elementar. In caz contrar, el este ne-elementar.

Graf parţialUn graf parţial al grafului G=(X,U) este un graf G1=(X,V) astfel încât VU, adică G1 are

aceeaşi mulţime de vârfuri ca G iar mulţimea de muchii V este chiar U sau o submulţime a acesteia.Cu alte cuvinte, un graf parţial al unui graf se obţine păstrând aceeaşi mulţime de vârfuri şi eliminând o parte din muchii.

SubgrafUn subgraf al unui graf G=(X,U) este un graf H=(Y,V) astfel încât Y  X iar V conţine

toate muchiile din U care au ambele extremităţi în Y. Vom spune că subgraful H este indus sau generat de mulţimea de vârfuri Y.

Graf conexUn graf G se numeşte conex dacă pentru orice două vârfuri x şi y diferite ale sale există un

lanţ care le leagă.

Componentă conexăSe numeşte componentă conexă a grafului G=(X, U) un subgraf C=(X1, U1), conex, a lui G

care are proprietatea că nu există nici un lanţ în G care să lege un vârf din X1 cu un vârf din X-X1.

61/66

Page 62: Recapitulare Bac Informatica

Ciclu hamiltonianSe numeşte ciclu hamiltonian intr-un graf neorientat un ciclu elementar care trece prin toate

nodurile grafului.Un graf neorientat este hamiltonian dacă el conţine un ciclu hamiltonian.

Ciclu eulerianSe numeşte ciclu eulerian un ciclu care contine toate muchiile unui graf (o singură dată

fiecare).Un graf neorientat este eulerian dacă el conţine un ciclu eulerian.

Metode de reprezentare a grafurilor orientate:

1)Matricea de adiacenţă -o matrice de n linii si n coloane,unde n= nr nodurilor grafului a[i,j]=1,dacă (i,j)Є U =0,in caz contrarCu ajutorul acestei matrici putem extrage informaţii cum ar fi: -gradele nodurilor ; -putem determina nodurile izolate,terminale,adiacente; -putem determina nodurile de grad maxim sau minim; -cate muchii are graful.Exemplu:

Pentru graful din figura matricea de adiacenta este:

0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0

2)Prin liste de vecini1 2 32 1 33 1 24 55 4

11.2Grafuri orientate

Definitie:Numim graf orientat, o pereche ordonată de mulţimi G=(X,U), unde: X este o mulţime finită şi nevidă numită mulţimea nodurilor (vârfurilor); U este o mulţime formată din perechi ordonate de elemente ale lui X, numită mulţimea

arcelor (muchiilor)

Observaţii:

62/66

3)Prin lista muchiilor1 21 32 34 5

Page 63: Recapitulare Bac Informatica

Prin noţiunea de perechi ordonate nu trebuie să înţelegem că o muchie este mai mare decât alta, ci pur şi simplu că facem deosebire între o muchie de forma (x,z) şi o alta de forma (y,x). Cu alte cuvinte muchiile sunt diferenţiate prin ordinea de scriere a simbolurilor.

Arcul (x,y) nu este tot una cu arcul (y,x).

Un arc va fi de forma u= (x,y), unde x se numeşte extremitate iniţială, iar y se numeşte extremitate finală a arcului. Cu alte cuvinte, “arcul iese din nodul x şi intră în nodul y”.

La fel ca la grafurile neorientate, vom spune că nodurile x şi y sunt adiacente, iar arcul u şi nodul x sunt incidente (la fel arcul x şi nodul y).

Graful unui vârf. Mulţimile Γ şi ωGradul exterior al unui vârf x, notat d*(x), reprezintă numărul arcelor care ies din nodul x,

adică numărul arcelor de forma (x,z) ε U.

Analog, se defineşte gradul interior al unui vârf x, notat d-(x), ca fiind numărul arcelor care intră în nodul x (de forma (y,x) ε U).

Drum, circuitSe numeşte drum în graful G, un şir de noduri D={z1, z2, z3, …, zk}, unde z1, z2, z3, …,

zk aparţin lui x, cu proprietatea că oricare două noduri consecutive sunt adiacente, adică există arcele [z1, z2], [z2, z3], …, [zk-1,zk] aparţin lui U.

Practic, un drum poate fi privit ca un traseu în care toate arcele au aceeaşi orientare, dată de sensul de deplasare de la z1 la zk.

Dacă nodurile z1, z2, z3, …, zk sunt distincte două câte două, drumul se numeşte elementar. În caz contrar, drumul este ne-elementar.

Lungimea unui drum = numărul de muchii din care este format.

Se numeşte circuit într-un graf, un lanţ L={z1, z2, z3, …, zk} cu proprietatea că z1=zk şi arcele [z1, z2], [z2, z3], …, [zk-1,zk] sunt distincte două câte două.

Graf parţial şi subgrafDefiniţie: Fie graful G=(X,U). Un graf parţial al lui G, este un graf G1=(X,V), cu V U.

Altfel spus , un graf parţial G1 al lui G, este chiar G, sau se obţine din G păstrând toate vârfurile şi suprimând nişte muchii.

Definiţie: Fie graful G=(X,U). Un subgraf al lui G, este un graf G1=(Y,T), unde Y X şi T U, iar T va conţine numai muchiile care au ambele extremităţi în Y. Altfel spus, un graf parţial G1

al lui G, se obţine din G eliminând nişte vârfuri şi păstrând doar acele muchii care au ambele extremităţi în mulţimea vârfurilor rămase.

Conexitate in grafuri orientateGraf conex: Definitie:

Un graf G este conex, daca oricare ar fi doua varfuri ale sale, exista un lant care le leaga. Un graf G=(X,U) se numeste tare conex daca pentru oricare doua noduri distincte exista x,y apartinand lui X, exista in G un drum de la x la y si un drum de la y la x.

Se numeste componenta tare conexa a unui graf orientat G=(X,U) un subgraf tare conex G1=(X1,U1) al sau, maximal in raport cu acel propus.

Grafuri hamiltoniene si eulerieneDefinitie:

63/66

Page 64: Recapitulare Bac Informatica

Se numeste ciclu hamiltonian intr-un graf, un ciclu elementar care contine toate varfurile grafului.

Se numeste graf hamiltonian, un graf care contine un ciclu hamiltonian.Definitie:

Se numeste lant hamiltonian, intr-un graf, un lant elementar care contine toate varfurile grafului.Teorema:

Daca intr-un graf G=(X,U) cu n>=3 varfuri, gradul fiecarui varf x verifica conditia d(x)>=n/2,atunci graful este hamiltonian.Definitie:

Se numeste ciclu eulerian, intr-un graf, un ciclu care contine toate muchiile grafului.Se numeste graf eulerian, un graf care contine un ciclu eulerian.

Teorema:Un graf fara varfuri izolate este eulerian, daca si numai daca este conex, si gradele tuturor

varfurilor sunt numere pare.

Metode de reprezentare a grafurilor ne-orientate:Matricea de adiacenţă

Are aceeaşi semnificaţie ca în cazul grafurilor neorientate, fiecare element a[i,j], cu i,j Є { 1,2,…..,n} este: 1 dacă exisă arcul (i,j), respectiv 0 în cay contrar.

Listele vecinilorPentru fiecare nod x se construiesc două liste ale vecinilor săi:- L+(x) – lista vecinilor succesori; conţine nodurile ce sunt extremităţi finale ale arcelor care

ies din nodul x.- L- (x) – lista vecinilor predecesori; conţine nodurile ce sunt extremităţi iniţiale ale arcelor

care intră în nodul x.

Exemplu:

În graful din figura 6 de mai sus, pentru nodul x=4 avem:

- arcele care ies din nodul 4 sunt (4,2) şi (4,3). În consecinţă, lista vecinilor succesori L*(4) conţine nodurile 2 şi 3;

- în nodul 4 intră un singur arc, şi anume (3,4), motiv pentru care lista vecinilor predecesori L-(4) conţine doar nodul 3.

Prezentăm în continuare aceste liste ale vecinilor pentru graful din figura 6.Nodul x L*(x) L-(x)1 2 Vida2 Vida 1,3,43 2,4 44 2,3 3

64/66

Page 65: Recapitulare Bac Informatica

11.3Arbori

Definitie: Un graf conex si fara cicluri se numeste arbore.Teorema:

Fie un graf G=(x, u). urmatoarele afirmatii sunt echivalente:- G este arbore.- G este un graf conex, minimal in raport cu aceasta proprietate (eliminand o muchie

oarecare, se obtine un graf ne-conex).- G este un graf fara cicluri, maximal in raport cu aceasta proprietate (adaugand o

muchie oarecare, se obtine un graf care are cel putin un ciclu).In cazul arborilor, in loc de “varfuri” si “muchii”, se folosesc cu precadere termenii

sinonimi “noduri” respectiv “arce”.

Rădăcină = Nod special care generează aşezarea unui arbore pe niveluri; Această operaţie se efectuează în funcţie de lungimea lanţurilor prin care celelalte noduri sunt legate de rădăcină.

Descendent = într-un arbore cu rădăcină nodul y este descendentul nodului x dacă este situat pe un nivel mai mare decât nivelul lui x şi există un lanţ care le uneşte şi nu trece prin rădăcină.

Descendent direct / fiu = într-un arbore cu rădăcină nodul y este fiul (descendentul direct) nodului x dacă este situat pe nivelul imediat următor nivelului lui x şi există muchie între x şi y.

Ascendent = într-un arbore cu rădăcină nodul x este ascendentul nodului y dacă este situat pe un nivel mai mic decât nivelul lui y şi există un lanţ care le uneşte şi nu trece prin rădăcină.

Ascendent direct / părinte = într-un arbore cu rădăcină nodul x este părintele (ascendentul direct) nodului y dacă este situat pe nivelul imediat superior (cu număr de ordine mai mic) nivelului lui y şi există muchie între x şi y.

Fraţi = într-un arbore cu rădăcină nodul x este fratele nodului y dacă au acelaşi părinte.

Frunză = într-un arbore cu rădăcină nodul x este frunză dacă nu are nici un descendent directTeorema: Un arbore cu n varfuri are n-1 muchii.

Proprietatile care caracterizeaza un arbore:- exista un nod in care nu intra nici un arc, numit radacina arborelui.- cu exceptia radacinii, fiecare nod are proprietatea ca in el intra un singur arc.

Aceasta leaga nodul respectiv de un alt nod numit predecesor sau parinte.- dintr-un nod pot iesi unul sau mai multe arce. Fiecare astfel de arc, leaga nodul

respectiv de un alt nod numit succesor sau fiu al nodului, iar arcele care ies din acelasi nod se numesc frati.

- nodurile sunt organizate pe nivele, primul nivel fiind ocupat de nodurile-radacina. Nodurile de pe ultimul nivel se caracterizeaza prin faptul ca din ele nu mai iese nici un arc, si se numesc noduri terminale sau frunze.

- nodurile pot contine o asa-numita informatie utila, care poate fi de orice tip. De obicei aceste informatii se mai numesc si chei ale arborelui.

Arbori binariDefinitie: Un arbore cu proprietatea ca fiecare nod, cu exceptia frunzelor are cel mult doi

descendenti (succesori) se numeste arbore binar.Succesorii se vor numi, in cazul in care exista, fiul stang si fiul drept.

65/66

Page 66: Recapitulare Bac Informatica

Metode de reprezentare a arborilor :1. Metode specifice grafurilor:

-matricea de adiacenta-liste de adiacente

2. Metode specifice arborilor:-prin legaturi de tip TATA. Arborele se reprezinta sub forma unui vector t cu n componente (n reprezinta numarul de noduri). Daca t[i]=k atunci nodul I este descendent al nodului k. Daca nodul I este varf atunci t[i]=0.

Fie arborele din figura:

Nodul 1 este radacina. Atunci vectorul de tip tata este: t=0 1 1 1 3 3 3 4 7 7.

66/66