Informatica Titularizare
Informatica Titularizare
PROGRAMA
PENTRU
DISCIPLINA
INFORMATICĂ ȘI TEHNOLOGIA INFORMAŢIEI
-București-
2020
Tematica știinţifică pentru disciplina Informatică și Tehnologia
Informaţiei
1. Algoritmi
Noţiunea de algoritm și caracteristici
Pentru orice rezolvare a unei probleme cu ajutorul calculatorului, trebuie parcurse
următoarele etape:
analiza problemei;
elaborarea unui algoritm de rezolvare a problemei;
implementarea algoritmului într-un limbaj de programare.
testarea programului și corectarea erorilor.
Un algoritm este o secventa finita de operatii, ordonata si complet definita, care, pornind
de la un set de date (intrari) produce rezultate (iesiri), in urma prelucrarii automate, prin
intermediul unui program.
Un algoritm trebuie sa fie:
- bine definit ( claritate - operatiile sale sa fie specificate riguros)
- exact ( pentru a-l putea prelucra ulterior o masina automata)
- finit ( sa se termine dupa un numar finit de pasi)
- universal ( sa permita rezolvarea unei clase de probleme)
- determinist ( executat la momente diferite de timp, cu aceleasi date de intrare, produce
aceleasi rezultate).
- eficient ( etapele care compun algoritmul trebuie alese astfel încât soluţia problemei să
fie obţinută după un număr minim de pași) .
Clasificarea datelor
1. în funcţie de momentul în care se produc:
- date de intrare
- date de ieșire
- date de manevră
2. în funcţie de valoare:
- variabile
- constante
3. în funcţie de modul de compunere:
- date elementare
- structuri de date
4. în funcţie de tip:
- date numerice
- date logice
- date șiruri de caractere
Tipuri de operatori:
-operatori aritmetici;
-operatori relaţionali;
-operatori logici.
c. operatori logici
-definesc o operaţie logică
-se pot aplica numai asupra operanzilor logici
-produc un rezultat de tip logic
Algoritmul
Pasul 1. citește valoarea lui n;
Pasul 2. atribuie lui p valoarea 1;
Pasul 3. atribuie lui i valoarea 1;
Pasul 4. atribuie lui p valoarea p*i;
Pasul 5. atribuie lui i valoarea i+1;
Pasul 6. dacă i≤n atunci treci la Pasul 4, altfel treci la Pasul 7;
Pasul 7. scrie valoarea lui p.
Limbajul pseudocod folosește cuvinte cheie, adică niște cuvinte cu înţeles prestabilit,
care indică operaţia executată.
Ele se reprezinta sub forma de text si utilizeaza anumite conventii sau codificari pentru
descrierea obiectelor algoritmului.
Este una din formele cele mai utilizate de reprezentare al algoritmilor. Intr-o schema
logica apar o serie de operatii exprimate sub forma grafica, numite blocuri, etichetate cu
informatii specifice si legate intre ele prin arce orientate (sageti), intrucat indica sensul
parcurgerii.
Presupunem ca programul actioneaza asupra unor date aflate pe o asa numita banda de
intrare, iar rezultatele sunt inregistrate pe o banda de iesire.
Accesul la date se face secvential (una dupa alta).
v e v=e
compusa
DA NU
con
7. Bloc de decizie: d.
8. Blocul de ramificare (selectie) este o multime de n arce care pleaca din acelasi varf si
care sunt etichetate cu predicatele P1, …, Pn; sunt expresii cu rezultat logic: adevarat(1) si
fals(0), ce satisfac urmatoarele conditii:
SAU logic P v P 2 v …v P = 1 (cel putin unul adevarat)
SI logic P P ^ …^ P = 0 (cel mult unul sa fie adevarat)
Relatiile exprima ca una si numai una din conditii poate fi satisfacuta (adevarata).
P P … P
Efectul instructiunii consta in evaluarea predicatelor si continuarea executiei pe drumul
indicat de arcul etichetat de predicatul adevarat.
1. Structura secventiala
Schema logica Pseudocod
Actiune 1
Act.1 Actiune 2
Act.2 Actiune 3
Act.3
Actiunile structuri secventiale sunt executate succesiv in ordinea in care apar.
Implementare in C++:
Instructiuni secventiale:
Instructiunea mixta, atribuirea, instructiunea compusa (bloc)
{ i1;
i2;
i3;
.
DA NU
cond
.
.
in; }
Actiune1 Actiune2
2. Structuri decizionale
a) Alternativa
Schema logica Pseudocod
DACA cond.
ATUNCI
Act 1
ALTFEL
Act 2
SFARSIT.
Aceasta structura asigura executarea uneia dintre cele doua actiuni prevazute in functie
de o conditie data.
Implementare C++: if (daca), else (altfel).
If(expresie) instructiune1;
Else instructiune2;
SAU pseudoalternativa:
If(expresie) instructiune;
b) Selectie
Schema logica Pseudocod
ALEGE i DINTRE
i CAZ 1: act 1
CAZ 2: act 2
………………
1 2 3 n CAZ n: act n
SFARSIT.
…
act.1 act.2 act.3 act.n
3
3
i=i+m3
DA
i<=m2
NU
Implementare C++: for (pentru)
Cat timp
conditie
actiune
Repeta
NU
Conditia
de
intrare
DA
actiune
While (expresie)
NU instructiune;
c) Ciclica cu testConditia
final (cu numar cunoscut de repetitii)
Schema logica de Pseudocod
iesire
DA
Repeta
actiune
Pana cand
conditie
Algoritmi elementari
1. Prelucrarea numerelor
a). Prelucrarea cifrelor unui număr
b). Probleme de divizibilitate
Determinarea divizorilor unui număr
Algoritmul lui Euclid
Numere prime
2. Prelucrarea unor secvenţe de valori
a). Calculul unor expresii simple
MAXIM
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{cout<<"max(1,2)="<<max(1,2)<<endl;
cout<<"max(2,1)="<<max(2,1)<<endl;
cout<<"max('a','z')="<<max('a','z')<<endl;
cout<<"max(3.14, 2.72)="<<max(3.14, 2.72)<<endl;
return 0;}
MINIM
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{cout<<"min(1,2)="<<min(1,2)<<endl;
cout<<"min(2,1)="<<min(2,1)<<endl;
cout<<"min('a','z')="<<min('a','z')<<endl;
cout<<"min(3.14, 2.72)="<<min(3.14, 2.72)<<endl;
return 0;}
c). Verificarea unor proprietăţi
Determinarea divizorilor
Pentru primul program, cu alte cuvinte trebuie sa impartim numarul citit la toate numerele mai mici
decat el, sa verificam daca x se imparte exact la acel numar, si apoi sa afisam toate numerele la care x se
divide.
//Divizori
#include <iostream>
#include <math.h>
using namespace std;
int main()
{int x, d; //x=nr citit; d=numerele la care se va imparti x;
cout<<”Divizorii unui numar”<<endl;
cout<<”Introduceti numarul: “;
cin>>x;
cout<<”Divizorii numarului x sunt: “;
for (d=1; d<=x; d++) //pentru d, initial 1, pana la numarul x;
{if (x%d==0) //verif daca x se imparte exact la acel pres divizor
cout<<d<<”; “;
return 0;}}//daca da, il afisam;
Pentru a transforma un nr. din baza 10 in baza "b" se imparte nr. la b si se retine restul. Se
imparte catul obtinut la b si se retine noul rest. Procedeul continua pana obtinem cat 0. Resturile luate
in ordine inversa formeaza nr. in baza b.
Pentru a transforma un nr. din baza "b" in baza 10 se inmulteste fiecare cifra a lui n cu baza la
o putere egala cu nr. de cifre ramase si se insumeaza rezultatele incepind cu ultima cifra binara.
Exemplu: Descompunerea unui număr - (123,45)10=1*102+2*101+3*100+4*10-1+5*10-2=(123,45)10
Din baza 2 în 10 - (110011)2=1*20+1*21+0*22+0*23+1*24+1*25=1+2+16+32=(51)10
Pasii algoritmului
Pentru generarea primilor n termeni ai sirului se vor genera repetat termenii de rang i ai sirului.
Se vor folosi trei variabile de memorie:
- a1 pentru ai-2
- a2 pentru ai-1
- a3 pentru termenul curent ai.
Dupa fiecare generare a unui termen se vor actualiza valorile din variabilele a1 si a2.
Pseudocod
intreg a1, a2, a3, n, i;
inceput
citeste n;
a1←1; a2←1;
scrie a1, a2;
pentru i←3, n executa
ai←ai-2+ai-1; scrie ai;
ai-2←ai-1; ai-1←ai;
sfarsit_pentru;
sfarsit.
3. Metode de ordonare
a). Bulelor
b). Inserţiei
SORTAREA PRIN INSERARE DIRECTĂ
PREZENTAREA ALGORITMULUI
Algoritmul de sortarea prin inserare directă va sorta elementele șirului v1, v2, …, vn, iar
după sortare, elementele vectorului vor fi în ordinea v1 ≤ v2 ≤ ... ≤ vn.
Pseudocodul pentru sortarea prin inserţie directă este reprezentat prin subprogramul numit
inserare_directa care are doi parametri:
- n prin care primește un număr natural ce reprezintă lungimea vectorului
- v prin care primește un vector care memorează un șir de n numere care trebuie sortat
d). Numărării
4. Interclasare (merge sort)
Fiind date două șiruri de numere, ordonate crescător (sau descrescător), se cere să se
obţină un șir care să fie de asemenea ordonat crescător (respectiv descrescător) și care să fie
formată din elementele șirurilor date.
Ideea:
Șirul rezultat se poate obţine direct (fără o sortare a șirului final) prin parcurgerea
secvenţială a celor două șiruri, simultan cu generarea șirului cerut. Prin compararea a două
elemente din listele de intrare se va decide care element va fi adăugat în lista de ieșire.
Exemplu:
șir 1: 1, 3, 4, 5
șir 1:-1, 2, 3
Rezultat: -1, 1, 2, 3, 3, 4, 5
Se citesc „m” numere intregi sortate crescator (descrescator) .De asemenea se citesc alte
„n” numere intregi sortate crescator (descrescator). Se cere sa se afiseze cele „m+n” valori in
ordine crescatoare (descrescatoare).
Algoritm de interclasare:
Sa presupunem ca cele doua siruri de numere sortate se memoreaza in doua variabile de
tip vector A si B.
Numerele sortate vor fi memorate intr-o alta variabila de tip vector (numita C). La
fiecare pas se alege un numar care va fi memorat in C (cel care urmeaza a fi adaugat in
ordinea ceruta).
Ex:
#include<iostream>
using namespace std;
int main()
{int a[100],b[100],c[200],m,n,i,j,k;
cout<<"m=";
cin>>m;
for(i=0;i<m;i++)
{cout<<"a["<<i+1<<"]=";
cin>>a[i];};
cout<<"n=";
cin>>n;
for(i=0;i<n;i++)
{cout<<"b["<<i+1<<"]=";
cin>>b[i];};
i=j=k=0;
while(i<m && j<n)
if(a[i]<b[j])
c[k++]=a[i++];
else
c[k++]=b[j++];
if(i<m)
for(j=i;j<m;j++)
c[k++]=a[j];
else
for(i=j;i<n;i++)
c[k++]=b[i];
for(i=0;i<k;i++)
cout<<c[i]<<endl;
return 0;}
5. Metode de căutare
a). Secvenţială
Implementare C++
int CautăSecv(int x,int v[],int n)
{for(int i=0;i<n;i++)
if(x==v[i])
return 1;
return 0;}
Atenţie! În for se execută instrucţiunea vidă.
În cazul cel mai favorabil când elementul se găsește pe prima poziţie se efectuează două
comparaţii. În cazul cel mai nefavorabil, când elementul nu se găsește deloc în vector, se
efectuează 2n+1 comparaţii. În continuare este prezentată o implementare ceva mai rapidă:
Implementare C++
int CautăSecv(int x,int v[],int n)
{int i=0;
while((v[i]!=x)&&(i<n))
i++;
if(i<n)
return 1;
else
return 0;}
Cu această implementare, în cazul cel mai favorabil avem două comparaţii, iar în cazul
cel mai nefavorabil avem n+2 comparaţii.
b). Binară
Dacă elementele vectorului sunt ordonate crescător, putem să ne dăm seama dacă
elementul nu există în vector fără a fi nevoie să parcurgem toate elementele vectorului. Unul
dintre algoritmii folosiţi în acest caz este algoritmul de căutare binară. Acest algoritm are la
bază principiul înjumătăţirii repetate a domeniului în care se caută elementul, prin împărţirea
vectorului în doi subvectori. Notăm cu st primul indice al vectorului și cu dr ultimul indice
al vectorului, iar m este indicele elementului din mijloc al vectorului m=(st+dr)/2. Se
compară valoarea căutată cu valoarea elementului din mijloc. Dacă cele două valori sunt
egale înseamnă că s-a găsit elementul. Dacă nu sunt egale, vectorul v-a fi împărţit în doi
subvectori. Operaţia de căutare constă în identificarea subvectorului în care se poate găsi
elementul, prin compararea valorii căutate cu cea din mijloc, după care se divizează acest
subvector în doi subvectori ș.a.m.d. până când se găsește elementul, sau până când nu se mai
poate face împarţirea în subvectori, ceea ce înseamnă că nu s-a găsit elementul.
Exemplu: Dorim să căutăm elementul x=19 într-un vector cu 9 elemente:
5 8 11 15 17 19 20 23 26
1 2 3 4 5 6 7 8 9
19 20 23 26
6 7 8 9
5 6
Pentru rezolvarea unei probleme se pot folosi mai mulţi algoritmi. În acest caz se va
alege algoritmul cel mai eficient.
Algoritmul cel mai eficient este cel care folosește cel mai puţin resursele calculatorului
și anume:
• memoria internă;
• procesorul.
A. Memoria internă
Pentru a face economie de memorie internă, trebuie avute în vedere următoarele:
- alegerea corectă a tipului de dată pentru fiecare variabilă de memorie folosită;
- rezolvarea problemei folosind cât mai puţine variabile de memorie. Analiza datei
trebuie să se facă în două moduri la alegerea tipului de dată: - logic; - fizic.
B. Procesorul
Timplu de execuţie al unui algoritm depinde de câte valori ale datelor de intrare vor fi
prelucrate. Se definește dimensiunea datelor de intrare ca fiind numărul de valori pentru
datele de intrare ale unui algoritm. În funcţie de complexitatea algoritmului, evaluarea
timpului de execuţie se poate face prin:
a. numărul de operaţii elementare ale algoritmului;
b. timpul mediu al programului.
Exemplu:
Observatii
- Limbajul face distinctie intre literele mari si cele mici.
- Nu are importanta nici plasarea cuvintelor pe linie, nici spatiile dintre ele.
- Este permis ca tipul functiei sa lipseasca, astfel se presupune ca functia intoarce un
rezultat de tipul int.
Citiri si scrieri
Pentru efectuarea citirilor si scrierilor, trebuie utilizata directiva:
#include <iostream>
includere numele fișierului (io-intrare-iesire; stream-flux de date de la o sursa catre o dest.)
si header(antet)
înaintea textului
cin>>-pentru citire
cout<<-pentru scriere
-pentru spaţiu intre date avem: ” ”
Ex: cout<<a<<” ”<<b≪endl;
-pentru scriere pe rândul următor se fol.: endl
Tipuri de date
(tipuri fundamentale, siruri de caractere, tipuri pointeri, tipuri structurate, tipuri definite
de utilizator, stucturi dinamice de date, tipul obiect)
Tipurile fundamentale (standard – adica este cunoscut de limbaj fara a fi
definit in cadrul programului)
Tipul logic: -bool - logic, ocupa 8 biti (1 octeți) [0 sau 1]
Tipurile intregi :
-tipul unsigned char - caracter fara semn, ocupa 8 biti (1 octeți)[0, 255]
-tipul char-caracter, ocupa 8 biti (1 octeți) [-128, 127]
-tipul short int – intreg scurt, ocupa 16 biti (2 octeți)
-tipul unsigned int – intreg fara semn, ocupa 32 biti (4 octeți)
-tipul int – intreg, ocupa 32 biti (4 octeți)
-tipul unsigned long int – intreg lung fara semn, ocupa 32 biti (4 octeți)
-tipul long int – intreg lung cu semn, ocupa 32 biti (4 octeți)
-tipul long long int – intregi foarte lungi cu semn, ocupa 64 biti (8 octeți)
Variabilele de tip intreg folosesc pentru memorarea datelor codul complementar (daca
se retin cu semn) sau baza 2 (fara semn).
Caracterele se memoreaza prin codul ASCII (0-255). Deci pentru memorarea datelor
negative(cu semn) folosim codul complementar, adica: reprezentam in baza 2 numarul, adica
numarul pozitiv, dupa care schimbam cifra 1 cu 0 si invers si adunam 1. Primul bit reprezinta
semnul ‘0’-pozitiv si ‘1’-negativ. –vezi anexa 2 cls.9-
Tipurile reale:
-tipul float (mobil), ocupa 32 biti (4 octeți)
-tipul double (dublu), ocupa 64 biti (8 octeți)
-tipul long double, ocupa 80 biti (10 octeți)
Pentru memorare se foloseste reprezentarea in virgula mobila; variabilele reale se tiparesc cu
6 zecimale. - vezi anexa 2 cls.9 -
Constante
- Constante întregi: zecimale (in baza 10: 23,1239, 56)
octale (in baza 8 constanta se declara precedata de ‘0’ nesemnificativ:
0123, din care se retine nr. intreg 123(8) )
hexazecimale (in baza 16 sunt precedate de ‘0X’ sau ‘0x’: 0X1A2 adica
1A2(16) sau 0x1a2 adica 1A2(16) )
- Constante caracter: acestea se trec intre doua caractere apostrof (‘)
Se mai declara si sub forma de secvenţa escape, care începe cu caracterul (‘\’)si se termina
cu codul constantei in baza 8 sau 16 {’\141’=a, ‘\x61’=a}, deoarece exista caractere care nu
se pot declara clasic pentru ca nu pot fi tastate: Ex. caracterul newline (codul 10(10)), in octal
‘\12’, sau in hexa ‘\xa’. Caracterul newline se poate scrie si ‘\n’.
Caracterele albe sunt: blank (‘ ‘); tab orizontal (\t), tab vertical (\v), newline (\n),
cr (\r).
- Constante reale
- Constante sir de caractere
Se declara intre doua caractere (“).
Pentru a da nume constantelor(declara), folosim [Link]. :const int numar=10; constanta de
tip int numita numar are valoarea 10.
Operatori aritmetici
- minus (unar) adică acţionează asupra unui singur operand
+ plus (unar)
+ plus (binar)
- minus (binar)
* inmultire (binar)
/ impartire (binar) (DIV)
% restul impartiri intregi (binar) : R=D-I*C . (MOD)
Operatori relationali
< ex. 3<5 – expresia ia valoarea ‘1’ adica adevarat.
<=
> ex. 3>5– expresia ia valoarea ‘0’
>=
Rezultatul unei operati logice adevarate va fi „1”iar false „0”.
Operatori de egalitate
= = pentru egalitate 3==3, rezultat 1;
!= pentru inegalitate 3!=3, rezultat 0.
Operatori de incrementare si decrementare
++ pentru incrementare(adica aduna 1)
-- pentru decrementare(adica scade 1)
Daca operatorul este prefixat: ++a ; --a
Daca operatorul este postfixat: a++ ; a--
Exemple :
1. a=1, 1+a++=2, dar dupa evaluare “a” va retine valoarea “2”.
2. a=1, 1- ++a= -1, a=2.
3. 1+++a, nu are sens.
4. a=1, b=3, a++*b++=3, dar dupa evaluare a=2 si b=4.
5. a=1, b=3, ++a*++b=8, a=2 si b=4.
6. a+++a++, trebuie evitata scrierea unor astfel de expresii .
Operatori logici
! - negare logica (daca operandul este o val. dif. de ‘0’, rez. este ‘0’, altfel este ‘1’)
&& - si logic (daca ambii operanzi sunt diferiti de ‘0’, rez. este ‘1’, altfel e ‘0’)
|| - sau logic (daca cel putin un operand are o valoare diferita ‘0’, rez. este ‘1’)
Operatori de atribuire
= de atribuire
*=, /=, %=, +=, -=, <<=, >>=, &>, ^=, |=, sunt tot de atribuire.
Operatorul conditional
exp1?exp2:exp3
Daca exp1 0, se evalueaza exp2 si ignora exp3 sau invers.
Operatorul sizeof(marime)
Returneaza numarul de octeti pentru memorarea unei valori:
sizeof (expresie)
sizeof (tip)
Instructiunea do while
Are forma: do
instructiune
while(expresie);
Ex:
1. Sa se calculeze suma primelor n numere naturale:
#include<iostream>
using namespace std;
int main()
{int n,s=0,i=1;
cout<<"n="; cin>>n;
do { s+=i++;}
while(i<=n); //sau: do
cout<<"s="<<s<<endl; //{ s=s+i; i=i+1;
return 0;} // } while(i<=n);
2. Se citeste n, numar natural. Sa se descompuna in factori primi:
#include<iostream>
using namespace std;
int main()
{int n, i=2, fm;
cout<<"n=";
cin>>n;
do
{fm=0;
while(n%i==0)
{fm++; //sau: fm=fm+1;
n/=i; //sau: n=n/i;}
if (fm) cout<<i<<" la puterea "<<fm<<endl;
i++;}
while(n!=1);
return 0;}
Instructiunea FOR
Are forma generala:
for (expresieintializare ;expresietest ; expresie incrementare )
instructiune;
Pentru a opri o ciclare infinita in:
DOS – tastam CTRL+PAUSE;
WINDOWS – tastam CTRL+ALT+DEL.
Ex:
1. Listarea numerelor 5, 4, 3, 2, 1.
#include<iostream>
using namespace std;
int main()
{int i;
for (i=5;i>=1;i--)
cout<<i<<" ";
return 0;}
2. Sa se listeze alfabetul in ordine inversa.
#include<iostream>
using namespace std;
int main()
{char car;
for (car='z';car>='a';car--)
cout<<car<<endl;
return 0;}
3. Sa se efectueze suma primelor n numere naturale. Exemplu: n=3. S=1+2+3=6.
#include<iostream>
using namespace std;
int main()
{int i, n, s=0;
cout<<"n=";
cin>>n;
for (i=1;i<=n;i++)
s+=i; /*sau: s=s+i;sau: for (i=1;i<=n;s+=i++);*/
cout<<"suma primelor n numere naturale este"<<s;
return 0;}
4. Sa se calculeze suma: s=0,1+0,2+…+0,9.
#include<iostream>
using namespace std;
int main()
{int i;
float s;
for (i=1;i<=9;i++)
s+=(float)i/10;
cout<<s;
return 0;}
sau:
#include<iostream>
using namespace std;
int main()
{double s=0, i;
for (i=0.1;i<=0.9;i+=0.1)
s=s+i; // sau: s+=i;
cout<<s;
return 0;}
Daca s si i sint de tip float, rezultatul este eronat deoarece numerele reale se reprezinta
aproximativ si pot aparea erori !
5. Sa se calculeze suma : 1+1*2+1*2*3+…+1*2*…*n
#include<iostream>
using namespace std;
int main()
{int i, n, s=0, p=1;
cout<<"n=";
cin>>n;
for (i=1;i<=n;i++)
{p*=i; // p=p*i;
s+=p; // s=s+p;}
cout<<s;
return 0;}
6. Sa se afiseze cel mai mare numar citit. Ex: Daca avem n=4, iar numerele sunt –7, 9, 2, 3,
se va afisa 9.
#include<iostream>
using namespace std;
int main()
{int i,max,n,nr;
cout<<"n="; cin>>n;
cout<<"nr"; cin>>nr;
max=nr;
for(i=2;i<=n;i++)
{cout<<"nr"; cin>>nr;
if(nr>max)max=nr;}
cout<<"maximul este"<<max;
return 0;}
7. Sa se afiseze numarul obtinut prin inversarea cifrelor sale.
#include<iostream>
using namespace std;
int main()
{int n, ninv;
cout<<"n=";
cin>>n;
for (ninv=0;n>0;)// sau for (ninv=0;n>0;n/=10)
{ninv=ninv*10+n%10; // ninv=ninv*10+n%10;
n=n/10;}
cout<<ninv;
return 0;}
Functii
Daca utilizam functii matematice trebuie inclus fisierul #include<math.h>,
#include<stdlib.h>, sau #include<cstdlib.h> in code blocks.
Exemplu de prototip : int t (int, float); iar apelata arata asa int t (7, 9.2);
floor #include<math.h>
double floor (double x);
calculeaza [x] a lui x (rotunjirea se face in minus)
floor (123.78)=123 floor(-23.34)=-24
ceil #include<math.h>
double ceil(double x);
ceil(123.78)=124
ceil(-23.34)=-23
cos #include<math.h>
double cos (double x);
calculeza valoarea functiei cos
cos(x):R [-1,1]
sin #include<math.h>
double sin (double x);
calculeaza valoarea functiei sin(x):R [-1,1]
tan #include<math.h>
double tan (double x);
calculeaza valoarea functiei tg(x):R-{kп+п/2|kєz} R
exp #include<math.h>
double exp(double x);
Calculeaza functia ex: R R+*
log #include<math.h>
double log(double x);
Calculeaza functia ln(x):R+* R unde ln(x)=loge(x)
log 10 #include<math.h>
double log 10(double x);
Calculeaza functia lg(x):R+* R, unde lg(x)=log10(x);
pow #include<math.h>
double pow( double x, double y);
Calculeaza xy.
Tablouri in c++
Ex: int v[100];
Am declarat un vector cu 100 de componente de tip intreg.
Ex: int a[10][9];
Am declarat o matrice (tablou) care are 10 linii si 9 coloane. Ele se adreseaza astfel:
a[0][0], a[0][1], … a[9][8].
Ex:
1. Acest program citeste si tipareste variabila un vector.
Initial se citeste „n ”(nr. comp.). Dupa aceasta se citesc, pe rand, toate componentele.
Sa presupunem ca s-a citit n=3. Apoi se citesc 3 numere intregi, cate unul pentru
fiecare componenta, si anume 6, 3, 4.
Citirea s-a facut cu ajutorul unei „for ”, unde variabila de ciclare reprezinta chiar
indicele componentei care se citeste.
In final se tipareste continutul componentelor citite
#include<iostream>
using namespace std;
int main()
{int v[100],n,i;
cout<<"numarul de componente";
cin>>n;
for (i=0;i<n;i++)
{cout<<"v["<<i+1<<"]=";
cin>>v[i];}
for(i=0;i<n;i++)
cout<<v[i]<<endl;
return 0;}
2. Programul de mai jos utilizeaza doi vectori, cu componente de tip float.
Citim vectorul ”a ”.
Se face atribuirea pe componente.
La sfarsit se tipareste vectorul „b ”.
#include<iostream>
using namespace std;
int main()
{int n,i;
float a[50],b[50];
cout<<"numarul de componente";
cin>>n;
for(i=0;i<n;i++)
{cout<<"a["<<i+1<<"]=";
cin>>a[i];}
for(i=0;i<n;i++)
b[i]=a[i];
for(i=0;i<n;i++)
cout<<b[i]<<endl;
return 0;}
3. Se citeste si se tipareste un tablou. Initial se citesc numarul de linii si coloane ale
tabloului (m si n).
#include<iostream>
using namespace std;
int main()
{int m,n,i,j,a[9] [9];
cout<<"m=";
cin>>m;
cout<<"n=";
cin>>n;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{cout<<"a["<<i+1<<','<<j+1<<"]=";
cin>>a[i][j];}
for(i=0;i<m;i++)
{for(j=0;j<n;j++)
cout<<a[i][j]<<' ';
cout<<endl;}
return 0;}
Maxim, minim
Se citeste un vector cu „n” componente intregi.
Sa se afiseze cel mai mare numar intreg gasit.
#include<iostream>
using namespace std;
int main()
{int v[9],n,i,max;
cout<<"n=";
cin>>n;
for(i=0;i<n;i++)
{cout<<"v["<<i+1<<"]=";
cin>>v[i];}
max=v[0];
for(i=1;i<n;i++)
if(v[i]>max)
max=v[i];
cout<<"valoarea maxima este"<<max;
return 0;}
Elemente distincte
Se citeste „n” si o variabila de tip „array ”cu „n ” componente intregi.
- se compara valoarea retinuta de prima componenta cu valorile retinute de
componentele de la 2 la n;
- se compara valoarea retinuta de a doua componenta cu valorile retinute de
componentele de la 3 la n;
- …………………………………………………….
Daca in urma comparatiilor nu se gasesc doua valori egale rezulta ca numerele sunt
distincte.
#include<iostream>
using namespace std;
int main()
{int v[9],n,i,j,gasit;
cout<<"n=";
cin>>n;
for (i=0;i<n;i++)
{cout<<"v["<<i+1<<"]=";
cin>>v[i];}
gasit=0;
for (i=0;i<n && !gasit;i++)
for (j=i+1;j<n && !gasit;j++)
if(v[i]==v[j])
gasit=1;
if(gasit)
cout<<"numerele nu sunt distincte";
else cout<<"numerele sunt distincte";
return 0;}
MULTIMI
A. TESTUL DE APARTENENTA
Se citeste o multime A de numere intregi. Se citeste un numar intreg “e ”. Sa se decida daca
“e” apartine lui A.
-o variabila ”gasit” va retine, initial, valoarea 0;
-apoi se testeaza fiecare element al multimii „A” daca este sau nu egal cu numarul retinut de
„e”;
-in caz de egalitate variabila gasit va retine „1” .
#include<iostream>
using namespace std;
int main()
{int mult[9], n, e, i, gasit;
cout<<"numarul de elemente al multimii";
cin>>n;
for(i=0;i<n;i++)
{cout<<"mult[ "<<i+1<<"]=";
cin>>mult[i];}
cout<<"e=";
cin>>e;
gasit=0;
for(i=0;i<n && !gasit;i++)
if(mult[i]==e)
gasit=1;
if(gasit)
cout<<"elementul apartine multimii ";
else
cout<<"elementul nu apartine multimii";
return 0;}
Metode de sortare
Cautare binara
-Se citesc „n” numere intregi sortate crescator.
-Se citeste un numar intreg „nr”.
-Sa se decida daca ”nr” se gaseste in sirul celor ”n” numere citite.
Aplicatii cu matrice
Zone speciale în matrice pătratice
1. Diagonala principală și secundară
Diagonala principală
Diagonala secundară
caracterizate de relația:
i+j=n+1
Relația dintre coordonate comună tuturor elementelor din această zonă este:
i<j
i>j
Observații
În practică, prelucrarea elementelor se poate realiza fie exclusiv pe diagonale sau pe zonele
identificate mai sus (de exemplu: ordonarea diagonalelor, verificarea simetriei sau a
triangularității), fie prin parcurgerea tuturor elementelor matricei și prelucrarea diferențiată în
funcție de relația dintre coordonate (de exemplu: completarea elementelor cu anumite valori,
calculul simultan al mai multor rezultate obținute pentru fiecare zonă în parte).
Diagonala secundară
for (i = 1; i <= n; i++)
<prelucrează a[i][n - i + 1]>
Deasupra diagonalei principale
for (i = 1; i <= n - 1; i++)
for (j = i + 1; j <= n; j++)
<prelucrează a[i][j]>
if (i + j < n + 1)
<prelucrează a[i][j] – deasupra diag. secundară>
if (i + j > n + 1)
<prelucrează a[i][j] – sub diag. secundară>
}
Problemă propusă
Se citesc elementele întregi ale unei matrice pătratice A de ordin n.
a) diagonala principală
b) diagonala secundară
c) elementele aflate sub diagonala principală
d) elementele aflate deasupra diagonalei secundare
Determinați elementul minim, elementul maxim și suma elementelor din fiecare dintre
zonele a), b), c), d).
Zone speciale
Zona Nordică
i < j și i + j < n + 1
Zona Sudică
i > j și i + j > n + 1
Zona Vestică
i > j și i + j < n + 1
Zona Estică
i < j și i + j > n + 1
1. Interschimbare linii
Se citeste un tablou cu „m” linii si ”n” coloane.
Se citesc doua numere naturale ”x” si ”y”, cuprinse intre ” l ” si ”m”.
Se cere sa se interschimbe linia ”x” cu linia ”y”.
Ex:
#include<iostream>
using namespace std;
int main()
{int mat[10][10],m,n,i,j,x,y,man;
cout<<"m=";
cin>>m;
cout<<"n=";
cin>>n;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{cout<<"mat["<<i+1<<","<<j+1<<"]=";
cin>>mat[i][j];
cout<<endl;}
cout<<"x=";
cin>>x;
cout<<endl<<"y=";
cin>>y;
cout<<endl;
for(i=0;i<m;i++)
{for(j=0;j<n;j++)
cout<<mat[i][j]<<" ";
cout<<endl;}
for(j=0;j<n;j++)
{man=mat[x-1][j];
mat[x-1][j]=mat[y-1][j];
mat[y-1][j]=man;}
cout<<endl;
for(i=0;i<m;i++)
{for(j=0;j<n;j++)
cout<<mat[i][j]<<" ";
cout<<endl;}
return 0;}
2. Spirala
-Se citeste un tablou cu „n” linii si „n” coloane.
-Se cere sa se afiseze elementele tabloului in ordinea rezultata prin parcurgerea acestuia in
spirala, incepand cu primul element din linia „1” in sensul acelor de ceas.
Ex:
Afisam elementele aflate pe fiecare latura a fiecarui patrat in ordinea ceruta, avind grija ca
elementele aflate in colturi sa nu fie afisate de doua ori!
#include<iostream>
using namespace std;
int main()
{int mat[10][10],n,i,j,k;
cout<<"n=";
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{cout<<"mat["<<i<<','<<j<<"]=";
cin>>mat[i][j];}
for(k=1;k<=n/2+1;k++)
{for(i=k;i<=n-k+1;i++)
cout<<mat[k][i]<<endl;
for(i=k+1;i<=n-k+1;i++)
cout<<mat[i][n-k+1]<<endl;
for(i=n-k;i>=k;i--)
cout<<mat[n-k+1][i]<<endl;
for(i=n-k;i>=k+1;i--)
cout<<mat[i][k]<<endl;}
return 0;}
Am lucrat cu indicii intre ‚1 ‚ si „n”.
SIRURI DE CARACTERE
Pentru atribuirea unui sir de caractere se folosesc anumite functii, care sunt chemate de
fisierul antet <cstring>, vechiul<string.h>.
Cele mai uzuale functii sunt:
1.
- strlen - size_t strlen(char*);
Are rolul de a returna lungimea efectiva a unui sir fara caracterul nul.
size _t - este un tip intreg, utilizat in adresarea memoriei definit in „cstring”.
Progamul citeste un sir si afiseaza numarul de caractere pe care le are sirul citit.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char a[100];
[Link](a,100);
cout<<" Sirul citit are "<<strlen(a)<<" caractere " ;
return 0;}
2.
- strcpy - char *strcpy(char* dest, char* sursa);
Are rolul de copia sirul de adresa ”sursa ” la adresa „dest ”. Copierea se termina dupa ce a
fost copiat caracterul nul. Se returneaza adresa „dest ”.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char a[100]="un sir",b[100]="alt sir";
strcpy(a,b);
cout<<a;
return 0;}
In progam se copiaza in vectorul „a ” sirul ”b ”.
Va afisa „alt sir ”.
Aceasta copiere simuleaza atribuirea „a=b ”.
3.
- strcat - char *strcat(char* dest, char* sursa);
Are rolul de a adauga sirului de adresa “dest ” sirul de adresa “sursa ”.
Sirul „sursa ”ramane nemodificat.
Progamul următor tipareste”mama merge ”:
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char a[20]=" mama ",b[100]=" merge " ;
strcat(a,b);
cout<<a;
return 0;}
4.
- strncat - char *strncat(char *dest, const char *sursa, size_t nr);
Are acelasi rol ca „strcat ” cu deosebirea ca adauga sirului destinatie primii „[Link]” ai
sirului sursa. Adaugarea caracterelor se face inaintea caracterului nul. Functia returneaza
adresa de inceput a sirului destinatie.
5
- strchr - char *strchr(char *s, int c);
Are rolul de a cauta caracterul „c ” in sirul „s ”si a afisa din acel punct.
Cautarea se face de la stinga la dreapta.
Exemplu: Se cauta in sirul „a ” caracterul „t ”. Programul va tipari sirul „ta este ”.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char a[20]=" aceasta este ";
cout<<strchr(a,'t');
return 0;}
Aplicatia 1:
Indicele in cadrul vectorului a caracterului cautat se obtine ca diferenta intre doua valori de
tipul char*. Descazutul este adresa returnata de functie, iar scazatorul este adresa vectorului
in care se face cautarea. Programul tipareste indicele primei aparitii a caracterului ‘t’, si
anume 4.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char a[20]="Acesta este";
cout<<strchr(a,'t')-a;
return 0;}
Aplicatia 2:
Se citeste un sir si un caracter. Daca acesta este gasit in sir se tipareste indicele primei
aparitii a caracterului in sirul solicitat.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char a[100],*t,c;
cout<<"introduceti sirul";
[Link](a,100);
cout<<"caracterul cautat";
cin>>c;
t=strchr(a,c);
if (t)
cout<<"Indicele este "<<t-a;
else
cout<<"Sirul nu contine acest caracter";
return 0;}
Ob:
Variabila t este de tipul char*.
Testul de apartenenta a caracterului la sir s-a facut prin a vedea daca variabila t retine sau nu
0.
Aplicatia 3:
Se listeaza indicii tuturor aparitiilor caracterului citit in sir.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char a[100], *t,c;
cout<<"Introduceti sirul!"<<endl;
[Link](a,100);
cout<<"Caracterul cautat!"<<endl;
cin>>c;
t=a-1;
do
{t++;
t=strchr(t,c);
if (t)
cout<<"Indicele este..."<<t-a<<endl;}
while (t);
return 0;}
6.
- strrchr - char *strrchr (const char *s, int c);
Are acelasi rol cu „strchr”, cu deosebirea ca returneaza adresa ultimei aparitii a caracterului.
7.
- strcmp - int strcmp (const char *s1, const char*s2);
Are rolul de a compara doua siruri de caractere.
Exemplu:
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char a[100],b[100];
int semnal;
cout<<"introduceti sirul a"<<endl;
cin>>a;
cout<<"introduceti sirul b"<<endl;
cin>>b;
semnal=strcmp(a,b);
if(semnal<0)
cout<<"a<b";
else
if(semnal>0)
cout<<"a>b";
else
cout<<"a=b";
return 0;}
Aplicatia 1:
Se citesc n cuvinte care vor fi sortate alfabetic.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char cuvinte[10][25],man[25];
int i,n,gasit;
cout<<"n=";
cin>>n;
for(i=0;i<n;i++)
{cout<<"cuvant";
cin>>cuvinte[i];}
do
{gasit=0;
for(i=0;i<n-1;i++)
if(strcmp(cuvinte[i],cuvinte[i+1])>0)
{strcpy(man,cuvinte[i]);
strcpy(cuvinte[i],cuvinte[i+1]);
strcpy(cuvinte[i+1],man);
gasit=1;}}
while(gasit);
for(i=0;i<n;i++)
cout<<cuvinte[i]<<endl;
return 0;}
8.
- strstr - char *strstr(const char *s1, const char *s2);
Are rolul de a identifica daca sirul „s2” este subsir al sirului „s1”.
Aplicatia 1:
Se citesc doua siruri de caractere si se testeaza daca al doilea este subsir al primului. In caz
afirmativ, programul tipareste si indicele caracterului de inceput al subsirului.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char sir[1000],subsir[25],*t;
cout<<"introduceti textul";
[Link](sir,1000);
[Link]();
cout<<"introduceti subsirul cautat";
[Link](subsir,25);
t=strstr(sir,subsir);
if(t) cout<<"este subsir si are indicele"<<t-sir;
else cout<<"nu este subsir";
return 0;}
Aplicatia 2:
Stergerea tuturor aparitiilor unui subsir din cadrul unui sir. Imediat ce am identificat adresa
de inceput a subsirului, restul sirului (fara subsir ) este copiat pe pozitia de inceput a
subsirului.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char sir[1000],subsir[25],*p;
int lung_subsir;
cout<<"introduceti textul";
[Link](sir,1000);
[Link]();
cout<<"introduceti subsirul";
[Link](subsir,25);
lung_subsir=strlen(subsir);
p=strstr(sir,subsir);
while(p)
{strcpy(p,p+ lung_subsir);
p=strstr(p,subsir);}
cout<<sir;
return 0;}
Aplicatia 7:
Inlocuirea tuturor aparitiilor unui subsir cu alt subsir.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char sir[100],man[100],sterg[25],adaug[25],*p;
int lung_sterg,lung_adaug;
cout<<"introduceti textul";
[Link](sir,100);
[Link]();
cout<<"inlocuim subsirul";
[Link](sterg,25);
[Link]();
cout<<"cu subsirul";
[Link](adaug,25);
lung_sterg=strlen(sterg);
lung_adaug=strlen(adaug);
p=strstr(sir,sterg);
while(p)
{man[0]=0; //subsir vid;
strncat(man,sir,p-sir);
strcat(man,adaug);
strcat(man,p+lung_sterg);
strcpy(sir,man);
p=strstr(p+lung_adaug,sterg);}
cout<<sir;
return 0;}
9.
- stricmp - int stricmp( char *s1,char *s2);
Are acelasi rol ca strcmp numai ca nu face distinctie intre literele mari si mici.
10.
- strtok - char *strtok( char *s1, const char *s2);
Aplicatia 1:
Se citeste un sir de caractere. Entitatile se considera a fi cuvinte – siruri de caractere care nu
sunt albe – separate prin blank-uri si/sau virgule. Programul listeaza entitatile depistate, care
incep cu ‘p’ fiecare pe un rind.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char sir[1000], separator[]=" , ", *p;
[Link](sir, 1000);
p=strtok(sir,separator);
while(p)
{cout<<p<<endl;
p=strtok(NULL, separator);}
return 0;}
11.
- strcspn - size_t strcspn ( const char *s1, const char *s2);
Are rolul de a returna nr. de caractere ale sirului „s1” - caractere consecutive care incep
obligatoriu cu primul caracter - care nu se gasesc in sirul „s2”.
12.
- strspn - size_t strspn( char *s1, char *s2);
Are rolul de a returna nr. de caractere ale sirului „s1” - caractere consecutive care incep
obligatoriu cu primul caracter - care se gasesc in sirul „s2”;
Aplicatia 1:
Se citeste un sir de caractere care nu contine caractere albe. Se verifica daca sirul este alcatuit
exclusiv din caractere numerice.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char cuvint[100],cifre[]="0123456789";
cout<<"introduceti cuvintul";
cin>>cuvint;
if(strspn(cuvint,cifre)==strlen(cuvint))
cout<<"numeric";
else
cout<<"nenumeric";
return 0;}
Aplicatia 2:
Se citeste un sir de caractere care nu contine caractere albe. Se verifica daca sirul este alcatuit
exclusiv din caractere nenumerice.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char cuvint[100],cifre[]="0123456789";
cout<<"introduceti cuvintul ";
cin>>cuvint;
if (strcspn(cifre,cuvint)==10)
cout<<"corect ";
else
cout<<"incorect ";
return 0;}
13.
- strlwr - char *strlwr(char *s);
Converteste toate literele mari in litere mici.
14.
- strupr - char *strupr(char *s);
Converteste toate literele mici in litere mari.
Ex:
Cuvintul citit se tipareste cu litere mari.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char a[20];
cout<<"introduceti cuvintul ";
cin>>a;
cout<<strupr(a);
return 0;}
15.
- strpbrk - char *strpbrk(char *s1, char *s2);
Aplicatia 13:
Se citesc doua cuvinte. Se cere sa se afiseze toate caracterele primului cuvint care se regasesc
in al doilea.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{char cuvint1[10], cuvint2[10],*p;
cout<<"introduceti primul cuvint";
cin>>cuvint1;
cout<<"introduceti al doilea cuvint";
cin>>cuvint2;
p=strpbrk(cuvint1,cuvint2);
while(p)
{cout<<p[0]<<endl;
p++;
p=strpbrk(p,cuvint2);}
return 0;}
16.
- atof - double atof (const char *s);
Converteste un sir catre tipul double.
17.
- _atold - long double _atold(const char *s);
Converteste un sir catre tipul long double.
18.
- atoi - int atoi(const char *s);
Convertește un sir către tipul int.
19.
- atol - long atol(const char *s);
Converteste un sir catre tipul long int.
Aplicatia 14:
Se citeste un text. Sa se calculeze suma valorilor numerice intilnite in text.
#include<iostream>
#include<cstring>
#include<stdlib.h>
using namespace std;
int main()
{char sir[1000],separator[]=" ",cifre[]="0123456789.+-",*p;
double s=0;
[Link](sir,1000);
p=strtok(sir,separator);
while(p)
{if(strspn(p,cifre)==strlen(p))
s+=atof(p);
p=strtok(NULL,separator);}
cout<<"suma numerelor intilnite in sir este"<<s;
return 0;}
20.
- ecvt - char* ecvt(double valoare, int poz, int* zec, int* semn);
- valoare - valoarea de convertit;
- poz - nr. de pozitii ocupate de sir;
- zec - adresa unei variabile de tip int, care retine nr zecimalelor pe care le are nr.;
- semn - adresa unei variabile de tip int, care are rolul de a memora –1-pt negativ si 0-pt
pozitiv.
Are rolul de a converti o valoare double catre un sir.
Ex:
#include<stdlib.h>
using namespace std;
int main()
{double numar;
int zec,semn;
char numar_sir[20]="",numar_prel[20]="";
cout<<"n= ";
cin>>numar; /*convertesc numarul si tiparesc rezultatul
asa cum este furnizat de functie*/
strcpy(numar_sir,ecvt(numar,19,&zec,&semn));
cout<<"sirul este"<<numar_sir<<" "<<zec<<" "<<semn<<endl;
//prelucrez sirul pentru a tipari rezultatul asa cum
//este asteptat de utilizator.
if(semn)
strcat(numar_prel,"-");
strncat(numar_prel,numar_sir,zec);
strcat(numar_prel,".");
strncat(numar_prel,numar_sir+zec,3);
cout<<numar_prel;
return 0;}
21.
- itoa - char *itoa(int valoare, char *sir, int baza);
Are rolul de a converti o valoare tip int in sir, care este memorat in variabila sir.
22.
- ltoa - char *ltoa (long value, char *sir, int baza);
Are acelasi efect ca „ itoa ” cu deosebirea ca se converteste catre sir o valoare de tip long int.
23.
- ultoa - char *ultoa(unsigned long value, char *sir, int baza);
Are acelasi efect ca ” itoa ” cu deosebirea ca se converteste catre sir o valoare de tip
unsigned long.
24.
- strtol - long strol(const char *s, char **endptr, int radix);
Are rolul de a converti un sir catre long.
Aplicatia 15:
#include<iostream>
#include<cstring>
#include<stdlib.h>
using namespace std;
int main()
{char numar[20],*adresa;
long v;
cin>>numar;
v=strtol(numar,&adresa,10);
if(adresa-numar !=strlen(numar))
cout<<"data contine caractere nenumerice";
else
if (v<10 || v>20)
cout<<"data numerica in afara limitei";
else
cout<<v<<endl;
return 0;}
25.
- strtod - double strtod(const char *s, char **endptr);
Converteste un sir catre double.
26.
- _strtold - long double _strtold(const char *(s), char **endptr);
Converteste un sir catre long double.
27.
- strtoul - unsigned long strtoul(const char *s, char **endptr, int radix);
Converteste un sir catre unsigned long.
Tipul inregistrare
Presupunem ca dorim sa prelucram date referitoare la mai multi elevi.
1. Numele - char[20];
2. Prenume - char[20];
3. Nota matematica - float;
4. Nota informatica - float;
5. Varsta - int;
In C++ exista un tip de date numit „ struct ”.
Forma generala:
struct [nume structura]
{
[<tip><nume variabila[, nume variabila, …]>];
[<tip><nume variabila[, nume variabila, …]>];
…………….
} [lista de variabile];
struct elev
{
char nume [20], prenume[20];
float nota_mate, nota_info;
int varsta;
} inr 1,inr 2; //aceste variabile pot fi declarate si: elev inr1, inr2;
Inregistrari imbricate
struct elev
{
char nume[20], prenume[20];
struct
{
int clasa;
float note[20];
}situatie;
int varsta;
};
sau:
struct elev1
{
char nume[20], prenume[20];
struct
{int clasa;
float note[20];
}situatie_1, situatie_2;
int varsta;
};
Fisierul text
Se caracterizeaza prin:
- datele sunt memorate sub forma unei succesiuni de caractere.
- fiecare caracter este memorat prin utilizarea codului ASCII.
- un fisier text se termina cu marcajul EOF(end of line), care se genereaza cu Ctrl+Z.
- fisierul text se considera alcatuit din una sau mai multe linii, separate de marcajul newline (
\n ) care se genereaza la apasarea tastei Enter.
- o variabilă specială, numită pointer reține întotdeauna un octet al fișierului.
Schema unui fisier text:
pointer
Observatii:
1. Orice editor de texte, deci si cel din C++, lucreaza cu fisiere text.
2. Pana in prezent am lucrat cu doua tipuri de fisiere text si anume cu „cin” si „cout”.
- fisierul „cin” este privit ca fiind de intrare mai precis datele sunt citite din fisierul „cin”.
- fisierul „cout” este privit ca unul de iesire, adica in loc ca progamul sa scrie intr-un fisier
memorat pe suport magnetic, acesta scrie pe monitor, deci in fisierul „cout”.
3. In / din fisierele text putem scrie sau citi cu sau fara format.
Sa presupunem ca vrem sa scriem o data reala. Daca nu precizam conditiile in care aceasta sa
fie scrisa, de exemplu, intotdeauna cu semn, chiar daca este plus, aliniata stanga sau dreapta
intr-un camp cu un numar fix de pozitii, numarul de zecimale cu care sa apara etc., atunci
spunem ca scriem fara format, altfel scriem cu format.
Fisiere binare
- Fisierele sunt alcatuite din mai multe inregistrari de acelasi tip. Din acest motiv se mai
numesc si cu tip:
o Inregistrarile sunt de tip „int”;
o Inregistrarile sunt de un tip descris cu „struct”;
- Datele sunt memorate in format intern, in cod complementar.
- Fisierele binare se termina cu „EOF”ca si cele text.
[Link] se creeze un fisier binar cu „n” inregistrari de tip „struct”, in care fiecare inregistrare
retine numele unei persoane si varsta sa. Datele de intrare se preiau de la tastatura.
#include<iostream>
#include<fstream>
using namespace std;
struct persoana
{char nume[30];
int varsta;};
int main()
{fstream f("c:\\[Link]", ios::out|ios::binary);
persoana p, *adr_p=&p;
char x;
int n,i;
cout<< "numarul de persoane";cin>>n;[Link]();
for(i=0;i<n;i++)
{cout<<"Numele";[Link]([Link],30);[Link](x);
cout<<"Varsta";cin>>[Link];[Link](x);
[Link]((char*)adr_p,sizeof (p));}
[Link]();
return 0;}
- intrucat lucram cu un fisier binar il vom deschide cu binary;
- am deschis structura corespunzatoare si am declarat variabila „p”, de acelasi tip;
- variabile de tip pointer adr_p este inițializată cu adresa variabilei „p”;
- dupa citirea variabilei „p”, urmeaza scrierea acesteia in fisier. Deci folosim functia ”write”
care scrie ”n” caractere ale unui sir și nu insereaza caracterul nul. Ea are forma: write(char*
nume, int n);
- „Pacalim” calculatorul sa scrie, de fapt continutul variabilei „p”, astfel: adresa de inceput a
variabilei „p”, o convertim catre un sir de caractere prin utilizarea operatorului de conversie
explicita. Numarul de caractere care trebuie scrise este dat de lungimea variabilei „p”. In
acest moment calculatorul „crede” ca scrie un sir de caractere. Daca e sir de caractere, nu
este cazul sa faca conversiile necesare. Dar el preia informatia in format intern si o scrie
asa…
[Link] se listeze fisierul creat anterior
Functia ”eof()” nu ne ajuta.
Vom folosi functia ”read”: read(char* nume,int n);
- si citeste cele „n” caractere ale unui fisier intr-o variabila de tip vector caractere.
#include<iostream>
#include<fstream>
using namespace std;
struct persoana
{char nume[30];
int varsta;};
int main()
{persoana p, *adr_p=&p;
fstream g("c:\\[Link]", ios::in|ios::binary);
while(g. read((char*) adr_p, sizeof(p)))
cout<<[Link]<<" "<<[Link]<<endl;
[Link]();
return 0;}
3. Sa se scrie un program care adauga la sfarsitul fisierului creat la exs.1, alte „n”
inregistrari. Deosebirea dintre cele doua programe va fi ca la declararea fisierului, in loc de
ios::out, se scrie ios::app.
-În prelucrarea fisierului binar se folosesc urmatorii termeni:
- creare;
- exploatare;
- actualizare: -stergere;
-modificare;
-adaugare.
POINTERI
1.1 NOTIUNEA DE ADRESA A UNEI VARIABILE
Am invatat faptul ca memoria interna poate fi privita ca o succesiune de octeti. Pentru
a-i distinge acestia sunt numerotati. Numarul de ordine al unui octet se numeste adresa lui.
Orice variabila ocupa un nr de octeti succesivi. De exemplu, o variabila de tip int
ocupa doi octeti (in varianta BORLAND C++ 3.0). Adresa primului octet al variabilei se
numeste adresa variabilei.
Observatii:
-Nu trebuie confundata adresa unei variabile cu valoarea pe care aceasta o memoreaza.
-Uneori, in loc de adresa a unei variabile vom folosi termenul pointer!
-In unele cazuri, adresa unei variabile se scrie sub o forma mai complicata: adrese liniare.
Adresa
7 variabilei
a
a adra adradra
- In programul următor variabila a, de tip elev este inițializată, iar variabila adra de tip
pointer catre variabila de tip elev este inițializată cu adresa variabilei a. Programul tipareste
de doua ori continutul variabilei a.
#include<iostream>
#include<cstring>
using namespace std;
struct elev
{char nume[20],prenume[20];};
int main()
{elev a,*adra=&a;
strcpy([Link],"carolina");
strcpy([Link],"florin");
cout<<(*adra).nume<<"+"<<(*adra).prenume<<endl;
cout<<adra->nume<<"+"<<adra->prenume;
return 0;}
- Observati modul in care am obtinut continutul unui camp al variabilei a, pornind de la
pointerul catre a: (*adra).nume. De ce este nevoie de paranteze?
Operatorul ’.’ - numit operator de selectie, are prioritatea 1, deci maxima.
Operatorul ’*’ - unar, numit si operator de dereferentiere, are prioritatea 2, deci mai mică.
Prin urmare in absenta parantezelor rotunde, se incearca mai intai evaluarea expresiei
[Link], expresie care n-are sens!
Parantezele schimba ordinea de evaluare, se evalueaza mai intai *adra, expresie care are
sens.
- Pentru astfel de selectie in loc sa folosim trei operatori se poate unul singur, operatorul de
selectie indirecta: ’->’. Acesta acceseaza un camp al unei structuri pornind de la un pointer
(adresa) catre acea structura. El are prioritate maxima. Astfel, in loc sa scriem (*adra).nume,
vom scrie mai simplu, adra->nume.
- In progamul următor, variabilei a i se atribuie valoarea 3. Variabilei adr i se atribuie adresa
variabilei a. Variabila a este incrementata, pornind de la continutul variabilei adr. Se
afiseaza de doua ori continutul variabilei a, pornind de la adresa retinuta de adr si de numele
ei.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{int a=3, *adr=&a;
++*adr;
cout<<*adr<<" "<<a;}
Observatii:
-Intre variabile de tip pointer sunt permise atribuiri doar in cazul in care au acelasi tip pointer
(retin adrese catre acelasi tip de variabile).
Exemplu:
int *adr1, *adr2;
float *adr3;
Atribuirea adr1=adr2 este corecta.
Atribuirea adr3=adr2 nu este corecta.
In acest caz se utilizeaza operatorul de conversie explicita. De aceasta data, pentru ex.
anterior, atribuirea: adr3=(float*)adr2 este corecta.
Programul următor tipareste continutul primului octet al unei variabile de tip int.
#include<iostream>
using namespace std;
int main()
{int a=3,*adr_int=&a;
char *adr_char=(char*)adr_int;
cout<<(int)*adr_char;}
Variabilei adr_char i-am atribuit adresa variabilei de tip intreg. Pentru. afisare, am folosit
din nou operatorul de conversie explicita (pt ca data sa nu fie afisata ca un caracter).
Mai elegant, aceeasi secventa poate fi scrisa si asa:
{int a=3;
char *adr_char=(char*)&a;
cout<<(int)*adr_char;}
RETINETI: octetii unei variabile numerice sunt retinuti in memorie in ordine inversa.
- In C++ exista si tipul pointer catre variabile de orice tip numit void*.
Unei variabile de tip void* ii putem atribui continutul oricarei variabile de tip pointer, dar
invers nu este posibil.
Ex:
In conditiile:
int a=3, *adr_int =&a;
void *adr_gen;
Atribuirea: adr_gen=adr_int ; este corecta.
Atribuirea: adr_int=adr_gen ; nu este corecta.
Programul următor afiseaza in binar continutul primului octet al unei variabile de tip int.
#include<iostream>
using namespace std;
int main()
{int a=11,j;
char *adr_byte=(char*)&a, masca=128;
cout<<endl;
for (j=0;j<8;j++)
{if(*adr_byte & masca)
cout<<1;
else
cout<<0;
*adr_byte=*adr_byte<<1; //sau *adr_byte<<=1;}}
O variabila numita masca, retine 128 adica 10000000 in binar. Ea foloseste pt efectuarea
intersectiei logice intre continutul octetului si masca. Daca bitul aflat pe prima pozitie este 0,
programul va tipari 0, iar daca acelasi bit este 1, programul va tipari 1. Dupa fiecare
intersectie logica intre continutul octetului care trebuie afisat se deplaseaza catre stanga, pt a
putea afisa continutul urmatorului bit.
Prin subprogram vom intelege un ansamblu alcatuit din tipuri de date, variabile si
instructiuni scrise in vederea unei anumite prelucrari (calcule, citiri, scrieri) si care poate fi
utilizat (rulat) doar daca este apelat de un program sau de alt subprogram.
- In C++, subprogramele sunt de tip functie.
- Parametri care se utilizeaza in antetul functiei se numesc parametri formali.
- Parametri care se utilizeaza la apel se numesc parametri efectivi.
Ex 1: Sa se calculeze E1=1+1/2+1/3+...+1/n.
#include<iostream>
using namespace std;
double subp(int n)
{double s=0;
int i;
for (i=1;i<=n;i++)
s+=1./i;
return s;}
int main()
{int n;
cout<<"n= " ;
cin>>n;
cout<<subp(n);}
Ex 2: Sa se calculeze E2=(1+1/2+1/3+...+1/n)n.
#include<iostream>
using namespace std;
double subp(int n)//n – parametru formal
{double s=0;
int i;
for(i=1;i<=n;i++)
s+=1./i;
return s;}
int main()
{int n,i;
double rez,prod=1;
cout<<"n= ";
cin>>n;
rez=subp(n);// n- parametru efectiv
for(i=1;i<=n;i++)
prod*=rez;
cout<<prod;}
Ex 3: Sa se tipareasca vectorul sortat.
#include<iostream>
using namespace std;
void citesc(int vt[10],int n)
{int i;
for(i=0;i<n;i++)
{cout<<"v["<<i+1<<"]=";
cin>>vt[i];}}
void sortez(int vt[10],int n)
{int gasit,i,man;
do
{gasit=0;
for(i=0;i<n-1;i++)
if(vt[i]>vt[i+1])
{man=vt[i];
vt[i]=vt[i+1];
vt[i+1]=man;
gasit=1;}}
while (gasit!=0);}
void scriu(int vt[10],int n)
{int i;
for(i=0;i<n;i++)
cout<<vt[i];}
int main()
{int vt[10],n;
cout<<"n= ";
cin>>n;
citesc (vt,n);
sortez (vt,n);
scriu (vt,n);}
DECLARAREA VARIABILELOR
Variabilele declarate in corpul functiilor, inclusiv in cel al functiei „main ( )”, se numesc
variabile locale.
- O variabila se caracterizeaza prin 4 atribute:
1. Clasa de memorare
2. Vizibilitate
3. Durata de viata
4. Tipul variabilei
1. Clasa de memorare - precizeaza locul unde este memorata variabila respectiva.
Sistemul de operare aloca fiecarui program trei zone distincte in memoria interna in care
se gasesc memorate variabilele programului.
O variabila poate fi memorata in:
-segmentul de date ;
-segmentul de stiva ;
-in Heap ;
-intr-un registru al microprocesorului ;
2. Vizibilitatea – precizeaza liniile textului sursa din care variabila respectiva poate fi
accesata .
Astfel avem :
a. Vizibilitate la nivel de bloc ( instructiune compusa );
b. Vizibilitate la nivel de fisier – in cazul in care programul ocupa un singur fisier
sursa;
c. Vizibilitatea la nivel de clasa – este in legatura cu programarea pe obiecte.
3. Durata de viata – reprezinta timpul in care variabila respectiva are alocat spatiu in
memoria interna .
Astfel avem :
a. Durata statica – variabila are alocat spatiu in tot timpul
executiei programului.
b. Durata locala – variabila are alocat spatiu in timpul in
care se executa instructiunile blocului respectiv.
c. Durata dinamica – alocarea si dezalocarea spatiului
necesar variabilei respective se face de catre programator prin operatori sau functii
speciale.
VARIABILE GLOBALE
Se declara in afara corpului oricarei functii ca in exemplul următor:
#include<iostream>
using namespace std;
int a;//este inițializată implicit cu zero.
int t()
{a=3;
cout<<a;}
int b;//este inițializată implicit cu zero.
int main()
{b=4;
cout<<a<<endl;
cout<<b<<endl;
t();
return 0;}
Variabilele „a” si „b” sunt globale - pot fi utilizate de toate functiile care urmeaza in textul
sursa declaratiei variabilei respective.
- la declarare, variabilele globale sunt initializate cu „0”.
Atributele variabilelor globale sunt:
1. Clasa de memorare - segmentul de date;
2. Vizibilitatea - in cazul in care declaratiile acestora sunt inaintea tuturor functiilor,
acestea sunt vizibile la nivelul intregului program (fisier);
De exemplu ”a” poate fi accesata din toate functiile, iar ”b” numai din „main()”.
3. Durata de viata a variabilelor globale este statica. Au spatiu rezervat in tot timpul
executiei programului.
VARIABILE LOCALE
Sunt declarate in corpul functiilor.
1. Clasa de memorare - segmentul de stiva;
E posibil ca acestea sa fie alocate in registrele microprocesorului, caz in care declaratia lor
trebuie precedata de cuvantul cheie „Register” - Register int b=4;
- variabilele locale nu sunt initializate implicit cu „0”.
2. Vizibilitatea variabilelor locale este la nivelul blocului la care au fost declarate.
3. Durata de viata a variabilelor locale este atata timp cat dureaza executia blocului
respectiv.
#include<iostream>
using namespace std;
int a;
void t()
{int a=4;
{int a=3;
cout<<a<<endl;}
cout<<a<<endl;}
int main()
{a=5;
t();
cout<<a;
return 0;}
TRANSMITEREA PARAMETRILOR
Parametrii care se gasesc in antetul functiei se numesc parametri formali, iar cei din
instructiunea de apel se numesc parametrii efectivi.
Ex: acest program contine o functie care calculeaza suma a doua numere naturale.
#include<iostream>
using namespace std;
int suma(int a, int b)
{return a+b;}
int main()
{int c=4,d=3;
cout<<suma(2,3)<<endl;
cout<<suma(2+7,3-1*2)<<endl;
cout<<suma(c,d)<<endl;
cout<<suma(1.9,3.3)<<endl;
return 0;}
- a si b sunt parametri formali
- Parametri efectivi sunt : 2, 3
2+7, 3-1*2;
c, d;
1.9, 3.3;
- Numarul parametrilor formali trebuie sa coincida cu numarul parametrilor efectivi. Exista si
o exceptie.
- Tipul parametrilor formali trebuie sa coincida cu tipul parametrilor efectivi.
- Pentru memorarea parametrilor subprogramele folosesc segmentul de stiva, pentru
variabilele locale.
- Memorarea parametrilor transmisi se face de la stanga la dreapta.
Exista doua mecanisme de transmitere a parametrilor, transmiterea prin valoare si
transmiterea prin referinta:
A. Transmiterea prin valoare se utilizeaza atunci cand suntem interesati ca subprogramul sa
lucreze cu acea valoare, dar in prelucrare, nu ne intereseaza ca parametrul efectiv (cel din
blocul apelant) sa retina valoarea modificata in subprogram.
Se pot transmite prin valoare:
1. Valorile retinute de variabile;
2. Expresii (acestea pot contine si functii).
1. Valorile retinute de variabile. In acest caz, parametrii efectivi trebuie sa fie numele
variabilelor.
Ex:
#include<iostream>
using namespace std;
void test(int n)
{n+=1;
cout<<n<<endl;}
int main()
{int n=1;
test(n);
cout<<n<<endl;
return 0;}
Parametrul n este transmis prin valoare.
In main(), avem declarata variabila n, care este inițializată cu 1.
Apelam functia. La apel, se rezerva spatiu in stiva, spatiu care are numele
parametrului (deci tot n) si este initializat cu valoarea memorata de variabila n a
programului principal. In acest moment avem doua variabile n si ambele retin
valoarea 1
In functie, variabila n este incrementata(adica la vechiul continut se adauga 1).
Evident, este vorba de variabila rezervata in cadrul ei.
Tiparim continutul variabilei n (cea din stiva), deci se tipareste 2.
La iesirea din functie, variabila n( din stiva) se pierde-adica nu mai are spatiu
alocat. Prin urmare, valoarea 2 este pierduta.
In main()se tipareste continutul variabilei n, adica 1.
2. Parametri efectivi sunt expresii, care mai intai se evalueaza.
Ex:
#include<iostream>
using namespace std;
void test (int n)
{cout<<n<<endl;}
int main()
{test(3);
test(3+4*5);
return 0;}
In functie se creeaza o variabila, retinuta in segmentul de stiva, numita n, care la
primul apel retine valoarea 3 si la al doilea valoarea 23. La iesirea din functie continutul
acestei variabile se pierde.
Asa cum am aratat, transmiterea parametrilor prin valoare se utilizeaza atunci cand nu
ne intereseaza ca, la intoarcerea din subprogram, parametrul efectiv sa retina valoarea
modificata acolo. Intrebare: daca n-ar exista decat transmiterea prin valoare, ar fi posibil sa
modificam valoarea anumitor variabile care sunt declarate in blocul apelant? Raspunsul este
afirmativ, daca lucram cu variabile de tip pointer. Functia intersc interschimba valorile
obtinute de doua variabile ale programului principal. Ea primeste ca parametri adresele celor
doua variabile.
#include<iostream>
using namespace std;
void intersc (int *x,int *y)
{int man;
man=*x;*x=*y;*y=man;}
int main()
{int a=2,b=3;
intersc(&a,&b);
cout<<a<<" "<<b;
return 0;}
Rețineți acest mecanism! El este general. Știați că, în limbajul C, acesta este singurul
mecanism de transmitere al parametrilor?
Tablourile NU se transmit prin valoare în C / C++.
Ele se degradează la pointer către primul element, deci sunt transmise efectiv prin
referință (adresă). De ce? Așa cum am învățat, numele tabloului este un pointer către
componentele sale. Prin valoare se transmite acest nume; cu ajutorul lui putem accesa
componentele tabloului.
In programul următor functia vector initializeaza vectorul transmis ca parametru, iar in
main()se afiseaza rezultatul.
#include<iostream>
using namespace std;
void vector(int x[10])
{for(int i=0;i<10;i++)
x[i]=i;}
int main()
{int a[10];
vector(a);
for(int i=0;i<10;i++)
cout<<a[i]<<" ";
return 0;}
B. Transmiterea prin referinta. Parametri sunt transmisi prin referinta atunci cand ne
intereseaza ca la revenirea din subprogram variabila transmisa sa retina valoarea stabilita in
timpul executiei subprogramului.
In cazul transmiterii prin referinta parametri formali trebuie sa fie referinte la variabile
ale parametrilor actuali(efectivi) (vezi tipul referinta prezentat prin capitolul anterior).
In cazul transmiterii prin referinta subprogramul retine in stiva, adresa variabilei
In acest caz ne putem intreba care este mecanismul prin care, desi pentru o variabila
transmisa se retine adresa ei, in subprogram putem adresa variabila normal (nu indirect)? La
compilare, orice referinta la variabila respectiva, este ”tradusa” ca adresare indirecta.
Programul următor utilizeaza o functie care interschimba valorile retinute de doua
variabile. Acestea sunt transmise prin referinta.
#include<iostream>
using namespace std;
void intersc(int &a, int &b)
{int man=a;a=b;b=man;}
int main()
{int x=2,y=3;
intersc(x,y);
cout<<x<<" "<<y;
return 0;}
Definirea si declararea unui subprogram
A defini un subprogram inseamna a-l scrie efectiv, dupa structura anterior prezentata.
O problema importanta este locul unde se defineste subprogramul.
A declara un subprogram inseamna a-l anunta. Un subprogram nedeclarat nu poate fi
folosit. Definitia unui subprogram tine loc si de declaratie!
Programul următor contine doua functii: s1 si s2. Definitiile ambelor functii se gasesc
inaintea functiei main(). Din acest motiv ele pot fi apelate din main(). Definitia functiei s1
este inaintea definitiei lui s2, deci functia s1 poate fi apelata din s2. In schimb, din s1 nu
poate fi apelata functia s2, pentru ca definitia lui s2 este dupa cea a lui s1.
#include<iostream>
using namespace std;
void s1()
{cout<<"Eu sunt s1"<<endl;}
void s2()
{s1();
cout<<"Eu sunt s2"<<endl;}
int main()
{s1();s2();}
In situatia prezentata, se poate, totusi, ca s1 sa apeleze pe s2, chiar daca sunt definite in
aceeasi ordine.
In astfel de cazuri se foloseste prototipul functiei (antetul urmat de ’;’). Prototipul are
rolul de a declara o functie. El nu contine definitia acestuia.
#include<iostream>
using namespace std;
void s2();
void s1()
{s2();
cout<<"Eu sunt s1"<<endl;}
void s2()
{cout<<"Eu sunt s2"<<endl;}
int main()
{s1();
return 0;}
Programatorii c++ obisnuiesc sa scrie mai intai prototipurile tuturor functiilor utilizate
de program -fara main()- iar dupa functia main() sa le defineasca. In acest fel orice
functie-mai putin main()-poate fi apelata prin oricare alta:
#include<iostream>
using namespace std;
void s1();//prototip s1
void s2();//prototip s2
int main()
{s1();
return 0;}
void s1()
{s2();
cout<<"Eu sunt s1"<<endl;}
void s2()
{cout<<"Eu sunt s2"<<endl;}
Aplicatii care folosesc subprograme
Ex 1: Sa se tipareasca cmmdc si cmmmc a doua nr.
#include<iostream>
using namespace std;
int cmmdc(int m,int n)
{while (m!=n)
if (m>n)
m-=n;
else
n-=m;
return m;}
int main()
{int cm,m,n;
cout<<"m=";
cin>>m;
cout<<"n=";
cin>>n;
cm=cmmdc(m,n);
cout<<"cmmdc="<<cm<<" "<<"cmmmc="<<m*n/cm;}
Ex 2: Sa se tipareasca cmmdc al valorilor retinute de un vector.
#include<iostream>
using namespace std;
int v[9],n;
int cmmdc(int m,int n)
{while(m!=n)
if (m>n)
m-=n;
else
n-=m;
return m;}
int main()
{int i,cm;
cout<<"n=";
cin>>n;
for(i=0;i<n;i++)
cin>>v[i];
cm=cmmdc(v[0],v[1]);
for(i=2;i<n;i++)
cm=cmmdc(cm,v[i]);
cout<<cm;}
Ex 3: Sa se tipareasca toate nr palindrom(121) aflate intre m si n.
#include<iostream>
using namespace std;
int palin(int i)
{int isalv=i,iinv=0;
while(i!=0)
{iinv=iinv*10+i%10;
i=i/10;}
return isalv==iinv;}
int main()
{int m,n,i;
cout<<"m=";
cin>>m;
cout<<"n=";
cin>>n;
for(i=m;i<n;i++)
if (palin(i)!=0)
cout<<i<<endl;}
Ex 4: Sa se tipareasca toate nr superpalindrom(121)2 aflate intre m si n.
#include<iostream>
using namespace std;
long palin(long i)
{long isalv=i,iinv=0;
while (i!=0)
{iinv=iinv*10+i%10;
i=i/10;}
return isalv==iinv;}
int main()
{long m,n,i;
cout<<"m=";
cin>>m;
cout<<"n=";
cin>>n;
for(i=m;i<n;i++)
if(palin(i)!=0)
if(palin(i*i)!=0)
cout<<i<<" "<<i*i<<endl;}
Ex 5: Programul complet cu functiile de citire si afisare a datelor unui elev este urmãtorul:
#include<iostream>
using namespace std;
typedef struct
{char nume[20];
char prenume[20];
float media;}Elev;
void citire_elev(Elev &e)
{cout<<"Nume: "; cin>>[Link];
cout<<"Prenume: "; cin>>[Link];
cout<<"Media: "; cin>>[Link];}
void afisare_elev(Elev e)
{cout<<"Nume: "; cout<<[Link]<<endl;
cout<<"Prenume: "; cout<<[Link]<<endl;
cout<<"Media: "; cout<<[Link]<<endl;}
int main()
{ Elev e;
citire_elev(e);
afisare_elev(e);
return 0;}
Ex 6: Programul complet cu functiile de citire si afisare a datelor elevilor cu struct imbric
este urmãtorul:
#include<iostream>
using namespace std;
typedef struct
{char nume[20];
char prenume[20];
float media;}Elev;
void citire_elevi(Elev e[],int &n)
{int i;
cout<<"n="; cin>>n;
for(i=1;i<=n;i++)
{cout<<"Nume: "; cin>>e[i].nume;
cout<<"Prenume: "; cin>>e[i].prenume;
cout<<"Media: "; cin>>e[i].media;}}
void afisare_elevi(Elev e[],int n)
{int i;
for(i=1;i<=n;i++)
{cout<<"Nume: "; cout<<e[i].nume<<endl;
cout<<"Prenume: "; cout<<e[i].prenume<<endl;
cout<<"Media: "; cout<<e[i].media<<endl;}}
int main()
{Elev e[31];
int n;
citire_elevi(e,n);
afisare_elevi(e,n);
return 0;}
STRUCTURI DE DATE
STRUCTURA DE TIP LISTA LINIARA
Definiție
O listă liniară este o colecție de n≥0n \ge 0n≥0 noduri X1,X2,…,XnX_1, X_2, \dots, X_nX1,X2,…,Xn aflate
într-o relație de ordine. Operațiile permise sunt:
Alocare secvențială: lista este stocată într-un vector. Operațiile necesită un efort mare de calcul
pentru inserții sau ștergeri.
Alocare înlănțuită: fiecare nod conține un pointer către următorul, facilitând inserția și ștergerea
rapidă a nodurilor.
Crearea listelor
3 adr2 7 adr3 9 0
Dacă se citește un nou număr (de exemplu 4), atunci acesta se adaugă într-o înregistrare
aflată la începutul listei, în următoarele etape:
a) Se alocă spaţiu pentru noua înregistrare, se completează câmpul numeric, iar adresa
următoare este cea din v, deci a primului element al listei.
3 adr2 7 adr3 9 0
adrn+1
3 adr2 7 adr3 9 0
Ex 1: Se aloca spatiu pt o variabila de tip complex, care este inițializată, afisata si stearsa.
#include<iostream>
using namespace std;
struct complex
{int m,n;};
int main()
{complex* adr;
adr=new complex;// // alocare dinamică
adr->m=7;//care este inițializată, afisata si stearsa.
adr->n=5;
cout<<adr->m<<" "<<adr->n<<endl;
delete adr;} // eliberare memorie
Ex 2: Se creeaza o lista liniara simplu inlantuita cu 3 noduri care retin 1, 2, 3.
#include<iostream>
using namespace std;
struct nod
{int info;
nod* adr_urm;};
int main()
{nod *c,*d,*v;
v=new nod;
v->info=1;
c=new nod;
c->info=2;
v->adr_urm=c;
d=new nod;
d->info=3;
d->adr_urm=0;
c->adr_urm=d;
c=v;
while(c)
{cout<<c->info<<" ";
c=c->adr_urm;}}
Ex 3: Modul de lucru cu o lista liniara simplu inlantuita memorata in HEAP.
#include<iostream>
using namespace std;
struct nod
{int info;
nod* adr_urm;};
nod *v = nullptr, *sf = nullptr;
void adaugare(nod*& v, int val)
{nod* c;
if(!v)
{v=new nod;
v->info=val;
v->adr_urm=0;
sf=v;}
else
{c=new nod;
sf->adr_urm=c;
c->info=val;
c->adr_urm=0;
sf=c;}}
void inserare_dupa(nod*& v,int val, int val1)
{nod *c,*d;
c=v;
while(c->info!=val)
c=c->adr_urm;
d=new nod;
d->info=val1;
d->adr_urm=c->adr_urm;
c->adr_urm=d;
if (d->adr_urm==0)
sf=d;}
void inserare_inainte(nod*& v,int val,int val1)
{nod *c,*d;
if(v->info==val)
{d=new nod;
d->info=val1;
d->adr_urm=v;
v=d;}
else
{c=v;
while(c->adr_urm->info!=val)
c=c->adr_urm;
d=new nod;
d->info=val1;
d->adr_urm=c->adr_urm;
c->adr_urm=d;}}
void sterg(nod*& v,int val)
{nod *c,*man;
if(v->info==val)
{man=v;
v=v->adr_urm;}
else
{c=v;
while(c->adr_urm->info!=val)
c=c->adr_urm;
man=c->adr_urm;
c->adr_urm=man->adr_urm;
if(man==sf)
sf=c;}
delete man;}
void listare(nod* v)
{nod* c=v;
while(c)
{cout<<c->info<<" ";
c=c->adr_urm;}
cout<<endl;}
int main()
{int i;
for(i=1;i<=10;i++)
adaugare(v,i);listare(v);
inserare_dupa(v,1,15);listare(v);
inserare_dupa(v,10,25);listare(v);
inserare_dupa(v,25,26);listare(v);
inserare_inainte(v,1,44);listare(v);
inserare_inainte(v,3,43);listare(v);
inserare_inainte(v,26,52);listare(v);
sterg(v,52);listare(v);
sterg(v,44);listare(v);
sterg(v,5);listare(v);}
Avantajul utilizării listei alocate dublu înlănţuit este dat de faptul că o astfel de listă poate fi
parcursă în ambele sensuri.
Operaţiile pe care le facem cu o listă dublu înlănţuită sunt următoarele:
1) creare;
2) adăugare la dreapta;
3) adăugare la stânga;
4) adăugare în interiorul listei;
5) ștergere din interiorul listei;
6) ștergere la stânga listei;
7) ștergere la dreapta listei;
8) listare de la stânga la dreapta;
9) listare de la dreapta la stânga.
Ex : Modul de lucru cu o lista liniara dublu inlantuita memorata in HEAP.
#include <iostream>
using namespace std;
struct nod
{int info;
nod *ast, *adr;};
nod *st, *dr;
int n, m, i;
void adaugare(nod*& st, nod*& dr)
{cout << "n=";
cin >>n;
st = new nod;
st->info = n;
st->ast = st->adr = nullptr;
dr = st;}
void adaugare_dr(nod*& dr)
{cout << "n=";
cin >> n;
nod* d = new nod;
d->info = n;
d->ast = dr;
d->adr = nullptr;
dr->adr = d;
dr = d;}
void inserare_dupa(nod*& st, int m)
{nod *d = st, *e;
while(d->info != m)
d = d->adr;
if (!d)
{cout << "Elementul nu exista!\n";
return;}
cout << "n=";
cin >> n;
e = new nod;
e->info = n;
e->ast = d;
e->adr = d->adr;
if (d->adr != nullptr)
d->adr->ast = e;
else
dr = e; // dacă inserez după ultimul element, actualizez dr
d->adr = e;}
void inserare_inainte(nod*& st, int m)
{nod *d = st, *e;
while(d->info != m) // caut nodul cu info = m
d = d->adr;
cout<<"n=";
cin>>n;
e = new nod; // aloc nodul nou
e->info = n;
e->adr = d; // îl leg în fața lui d
e->ast = d->ast;
d->ast->adr = e; // refacem legăturile nodului anterior
d->ast = e;
if(d == st) // dacă am inserat înaintea primului nod
st = e;} // st devine nodul nou
void sterg(nod*& st, int m)
{nod* d = st;
while(d->info != m)
d = d->adr;
if (!d)
{cout << "Elementul nu exista!\n";
return;}
if (d->ast != nullptr)
d->ast->adr = d->adr;
else
st = d->adr; // şterg primul nod
if (d->adr != nullptr)
d->adr->ast = d->ast;
else
dr = d->ast; // şterg ultimul nod
delete d;}
void listare(nod*& st)
{nod* d = st;
while(d)
{cout << d->info << endl;
d = d->adr;}}
int main()
{cout << "Lista cu o inreg" << endl;
adaugare(st, dr);
cout << "Cate inreg se adauga?";
cin >> m;
for(i = 1; i <= m; i++)
adaugare_dr(dr);
cout << "Listare de la stanga la dreapta" << endl;
listare(st);
cout << "Inserare la dreapta dupa..." << endl;
cin >> m;
inserare_dupa(st, m);
cout << "Acum listez de la stanga la dreapta" << endl;
listare(st);
cout << "Stergem inreg..." << endl;
cin >> m;
sterg(st, m);
cout << "Listare de la stanga la dreapta" << endl;
listare(st);}
//&-adica param nostru dr se poate schimba dupa prima rulare
d->ast->adr=d->adr;/*campul urm al comp ant comp de sters(denotata de adresa sa d->ast)va
contine adresa comp care urma in lista componentei de sters*/
d->adr->ast=d->ast;/*campul ant al comp ce urma comp de sters(denotata prin d->adr)va
contine adresa comp anterioare comp de sters*/
O coadă este o listă pentru care toate inserările sunt făcute la unul din capete, toate
ștergerile (consultările, modificările) la celălalt capăt. Coada funcţionează pe principiul FIFO
(First In First Out) -"primul intrat primul ieșit". Este cu totul nerecomandabilă alocarea
secvenţială a cozii, deoarece în această situaţie, are loc un fenomen de migraţie a datelor
către ultimele componente ale vectorului (cele de indice mare).
Alocarea dinamică înlănţuită a cozii. O variabilă v va reţine adresa elementului care
urmează a fi scos (servit). O alta, numită sf, va reţine adresa ultimului element introdus în
coadă. Figura următoare prezintă o coadă în care primul element care urmează a fi scos are
adresa în v, iar ultimul introdus are adresa în sf.
v sf
7 3 5 2
Mecanismul recursivitatii
Se doreste calculul lui n! folosind o functie recursiva.
Pentru a scrie o functie recursiva care efectueaza acelasi calcul, vom porni de la o
definitie recursiva a lui n!. Aceasta este:
n!=fact(n)= n N
De exemplu, pentru a calcula 3!, procedam astfel:
3!=fact(3)=3xfact(2)=3x2xfact(1)=3x2x1xfact(0)=3x2x1x1=6.
Functia recursiva fact nu face altceva decat sa transcrie definitia recursiva
prezentata anterior:
#include<iostream>
using namespace std;
int fact(int n)
{if(!n) return 1;
else
return n*fact(n-1);}
int main()
{int n;
cout<<"n=";
cin>>n;
cout<<endl;
cout<<n<<"!="<<fact(n);
return 0;}
Observati ca functia fact se autoapeleaza. Autoapelul se realizeaza prin:
Return n*fact(n-1).
Care este mecanismul prin care subprogramele se pot autoapela? Sa ne amintim modul in
care subprogramele memoreaza parametrii transmisi:
Pentru memorarea parametrilor, subprogramele folosesc o zona de memorie
numita stiva (mai exact, aceasta zona se numeste segment de stiva).
Memorarea parametrilor transmisi se face in ordinea in care acestia figureaza in
antet: de la stanga la dreapta.
Pentru parametri transmisi prin valoare, se memoreaza valoarea transmisa, iar
pentru cei transmisi prin referinta se memoreaza adresa variabilei.
In cadrul subprogramului, parametrii transmisi si memorati in stiva sunt
variabile. Numele lor este cel din lista parametrilor formali.
In capitolul anterior am studiat proprietatile structurii numita stiva. Exact aceleasi
proprietati le are si segmentul de stiva. Singura diferenta este data de faptul ca
gestiunea segmentului de stiva este facuta automat de catre calculator. Mai exact,
codul in limbaj masina, obtinut in urma compilarii, contine secvente prin care se
gestioneaza segmentul de stiva.
La apelul subprogramului se depun in stiva, in ordine, parametrii transmisi. De
asemenea, tot in stiva se rezerva spatiu pentru variabilele locale (cele declarate in
subprogram). Acesta este un prim nivel al stivei.
In cazul in care subprogramul se autoapeleaza pe un al doilea nivel se depun din
nou parametrii transmisi si se rezerva un nou spatiu pentru variabilele locale.
fib(n)=
ack(m,n)=
Remarcam ca, in ultima linie a acestei definitii, are loc o dubla invocare recursiva a
functiei: o data pentru calcularea celui de-al doilea argument si inca o data pentru calcularea
valorii functiei. Exista totusi si situatii in care inlocuirea recursiei prin iteratie necesita
folosirea unei stive.
Din exemplele de mai sus, constatam urmatoarele:
in definitia unei functii recursive trebuie sa fie obligatoriu prevazute si conditii de
terminare in care valoarea intoarsa este calculata direct, fara a mai recurge la
invocarea recursiva a aceleiasi functii;
algoritmul trebuie sa fie astfel conceput, incat dupa efectuarea unui numar finit de
apeluri recursive sa fie satisfacute conditiile de terminare
Exista si posibilitatea ca recursia sa fie indirecta: in corpul functiei f este invocata functia
g, iar in corpul functiei g este invocata functia f. Cercul acestor invocari succesive poate sa
contina mai mult de doua functii
Procedurile nu au valoare intoarsa, ci numai efect lateral. In consecinta folosirea
procedurilor recursive se bazeaza pe cumularea efectelor laterale, care consta in modificarea
valorilor unor variabile globale sau valorilor parametrilor proceduri. In limbajul Java nu
exista variabile globale, dar pot fi modificate valorile unor campuri ale clasei careia ii
apartine metoda recursiva sau a unor componente ale obiectelor primite ca parametri.
Aceeasi functie poate fi, de regula, calculata atat printr-un algoritm iterativ, cat si prin
unul recursiv. Uneori insa, iteratia este mult mai rapida decat recursia si consuma mai putina
memorie. In schimb, utilizarea functiilor sau procedurilor recursive este mai eleganta si face
algoritmul mai usor de inteles si de verificat. In plus, folosirea recursivitatii este o tehnica
foarte eficienta de concepere a algoritmilor. Din aceasta cauza, multi algoritmi sunt
conceputi mai intai in varianta lor recursiva si apoi, numai daca aceasta varianta necesita
timp de calcul sau memorie prea mare, se cauta si o varianta iterativa.
De foarte multe ori, trecerea de la varianta recursiva la cea iterativa a algoritmului se face
prin inlocuirea apelurilor recursive cu un ciclu.
Ex 1: pentru calcularea factorialului se poate folosi;
- fie functia recursiva:
#include<iostream>
using namespace std;
int fact(int n)
{if(n==0) return 1; /*conditia de incheiere a recursiei*/
else
return n*fact(n-1);} // invocarea recursiva
int main()
{int n;
cout<<"n=";
cin>>n;
cout<<endl;
cout<<n<<"!n="<<fact(n);
return 0;}
- fie varianta iterativa:
#include<iostream>
using namespace std;
int main()
{int n,i,f;
cout<<"n=";
cin>>n;
f=1;
for(i=2;i<=n;i++) // ciclul de repetare/iterare a valorilor
f*=i;
cout<<endl;
cout<<n<<"!n="<<f;
return 0;}
Ex 2: functia Manna-Pnueli;
- rezolvare recursiva:
#include<iostream>
using namespace std;
int n;
int manna(int n)
{if(n>=12)
return n-1;
else
return manna(manna(n+2));}// dubla invocare recursiva
int main()
{cout<<"n=";
cin>>n;
cout<<manna(n);
return 0;}
Ex 3: functia Fibonacci;
- rezolvare recursiva:
#include<iostream>
using namespace std;
int n;
int fib(int n)
{if(!n)
return 0;
else
if(n==1)
return 1;
else
return fib(n-1)+fib(n-2);}
int main()
{cout<<"n=";
cin>>n;
cout<<fib(n);
return 0;}
- rezolvare iterativa:
#include<iostream>
using namespace std;
int main()
{int n, i, f0=0, f1=1, f2;
cout<<"n=";
cin>>n;
if(!n)
cout<<f0;
else
if(n==1)
cout<<f1;
else
{for(int i=2;i<=n;i++)
{f2=f0+f1; f0=f1; f1=f2;}
cout<<f2;}
return 0;}
Aplicatii
1 daca n=1;
T(n)=
T( )+1 altfel.
Daca n nu este de forma 2 , atunci exista k astfel incat:
2 <n<2 =>k<T(n))≤k+1;
In concluzie, numarul maxim de operatii este:
k+1=[log n]+1
0 n=1;
T(n)= 2T( )+n altfel.
Avem:
T(n)=T(2 )=2(T(2 )+2 )=2T(2 )+2 =2(T(2 +2 )+2 =2T(2 )+2 +2
=…2 +2 +…+2 =n+n+…+n=n*k=n* log n
de k ori de k ori
Sortarea prin interclasare are complexitate T(n)=O(nlogn)
𝑂(𝑛log𝑛), in cel mai nefavorabil caz (vector deja sortat, pivot prost ales) 𝑂(𝑛2).
Sortarea rapida efectueaza in medie n*log2n operatii, adica in medie complexitate de
Rezolvare:
Daca n=1, se face mutarea ab, adica se muta discul de pe tija a pe tija b.
Daca n=2, se fac mutarile ac, ab, cb.
In cazul in care n>2 problema se complica. Notam cu H(n,a,b,c,) sirul mutarilor celor n
discuri de pe tija a pe tija b, utilizand ca tija intermediara, tija c.
Conform strategiei DIVIDE ET IMPERA incercam sa descompunem problema in alte
doua subprobleme de acelasi tip, urmand apoi combinarea solutiilor.
In acest sens, observam ca mutarea celor n discuri de pe tija a pe tija b, utilizand ca tija
intermediara tija c, este echivalenta cu:
- mutarea a n-1 discuri de pe tija a pe tija c, utilizand ca tija intermediara tija b;
- mutarea discului ramas pe tija b;
- mutarea a n-1 discuri de pe tija c pe tija b, utilizand ca tija intermediara tija a.
Parcurgerea celor 3 etape permite definirea recursiva a sirului H(n,a,b,c) astfel:
Exemple:
Pentru n=2 avem:
H(2,a,b,c)=H(1,a,c,b),ab,H(1,c,b,a)=ac,ab,cb.
Pentru n=3 avem:
H(3,a,b,c)=H(2,a,c,b),ab,H(2,c,b,a)=H(1,a,b,c),ac,H(1,b,c,a),ab,H(1,c,a,b),cb,H(1,a,b,c)=ab,a
c,bc,ab,ca,cb,ab.
#include<iostream>
using namespace std;
char a,b,c;
int n;
void han (int n,char a,char b,char c)
{if (n==1) cout<<a<<b<<endl;
else
{han(n-1,a,c,b);
cout<<a<<b<<endl;
han(n-1,c,b,a);}}
int main()
{cout<<"N=";cin>>n;
a='a' ;b='b' ;c='c' ;
han(n,a,b,c);
return 0;}
H
o xv(i), yv(i)
x,y
L
Pentru a se afla in interiorul dreptunghiului gaura trebuie sa indeplineasca simultan
conditiile:
1) xv(i)>x;
2) xv(i)<x+L;
3) yv(i)>y;
4) yv(i)<y+H.
Daca facem o taietura verticala prin aceasta gaura, obtinem doua dreptunghiuri:
1) x, y, xv(i)-x, H;
2) xv(i), y, L+x-xv(i), H.
In urma unei taieturi pe orizontala se obtin cele doua dreptunghiuri:
1) x, y, L, yv(i)-y;
2) x, yv(i), L, H+y-yv(i).
#include<iostream>
using namespace std;
int l,h,i,n,xf,yf,lf,hf,xv[10],yv[10];
void dimp (int x,int y,int l,int h,int& xf,int& yf,
int& lf,int& hf,int xv[10],int yv[10])
{int gasit=0,i=1;
while(i<=n && !gasit)
if(xv[i]>x && xv [i]<x+l && yv[i]>y && yv[i]<y+h)
gasit=1;
else i++;
if(gasit)
{dimp(x,y,xv[i]-x,h,xf,yf,lf,hf,xv,yv);
dimp(xv[i],y,l+x-xv[i],h,xf,yf,lf,hf,xv,yv);
dimp(x,y,l,yv[i]-y,xf ,yf,lf,hf,xv,yv);
dimp(x,yv[i],l,h+y-yv[i],xf,yf,lf,hf,xv,yv);}
else
if(l*h>lf*hf)
{xf=x; yf=y;lf=l;hf=h;}}
int main()
{cout<< "n=";cin>>n;
for (int i=1;i<=n;i++)
{cout<<"x["<<i<<"]="; cin>>xv[i];
cout<<"y["<<i<<"]="; cin>>yv[i];}
cout<<"l=";cin>>l;cout<<"h=";cin>>h;
dimp (0,0,l,h,xf,yf,lf,hf,xv,yv);
cout<<"x="<<xf<<"y="<<yf<<"l="<<lf<<"h="<<hf;
return 0;}
Tehnica backtracking
5.1Aspecte teoretice
Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan
urmatoarele conditii:
solutia lor poate fi pusa sub forma unui vector S=x1, x2, …, xn, cu x1ϵA1, x2ϵA2, …,
xnϵAn;
multimile A1, A2, …, An sunt multimi finite, iar elementele lor se considera ca se afla intr-
o relatie de ordine bine stabilita;
nu se dispune de o alta metoda de rezolvare, mai rapida
Observatii:
nu ptr. toate problemele n este cunoscut de la inceput;
x1, x2, …, xn pot fi la randul lor vectori;
in multe probleme, multimile A1, A2, …, An coincid.
Observatie: tehnica Backtracking are ca rezultat obtinerea tuturor solutiilor problemei. In
cazul in care se cere o singura solutie, se poate forta oprirea, atunci cand a fost gasita.
Pentru usurarea intelegerii metodei, vom prezenta o rutina unica (aplicabila
oricarei probleme), rutina care este elaborata folosind structura de stiva. Rutina va
apela functii care au intotdeauna acelasi nume si care, din punct de vedere al metodei,
realizeaza acelasi lucru. Sarcina rezolvitorului este sa scrie explicit, pentru fiecare
problema in parte, functiile apelate de rutina backtracking.
Evident, o astfel de abordare conduce la programe lungi. Nimeni nu ne opreste
ca, dupa intelegerea metodei, sa scriem programe scurte, specifice fiecarei probleme in
parte.
Am aratat ca orice solutie se genereaza sub forma de vector. Vom considera ca
generarea solutiilor se face intr-o stiva. Astfel x1ϵA1 se va gasi pe primul nivel al
stivei, x2ϵA2 se va gasi pe al doilea nivel al stivei, xkϵAk se va gasi pe nivelul k al
stivei. In acest fel, stiva (notata st) va arata ca mai jos:
xk
…
x2
x1
st
Nivelul k+1 al stivei trebuie initalizat (pentru a alege, in ordine, elementele multimii
k+1). Initializarea trebuie facuta cu o valoare aflata (in relatia de ordine considerata pentru
multimea Ak+1) inaintea tuturor valorilor posibile din multime.
De exemplu, pentru generarea permutarilor multimii {1, 2, …, n}, orice nivel al stivei
va lua valori de la 1 la n. Initializarea unui nivel (oarecare) se face cu valoarea 0. Functia de
initializare se va numi Init().
Gasirea urmatorului element al multimii Ak+1, element netestat, se face cu
ajutorul functiei int Am _Succesor(). Daca exista succesor acesta este pus in stiva si
functia returneaza 1, altfel functia returneaza 0.
Testul daca s-a ajuns sau nu la solutia finala se face cu ajutorul functiei int
Solutie()
Solutia se tipareste cu ajutorul functiei Tipar().
Testarea conditiilor de continuare (adica daca avem sansa sau nu ca prin
valoarea aflata pe nivelul k+1 sa ajungem la solutie) se face cu functia int E_Valid() care
intoarce 1, daca conditiile sunt indeplinite sau 0 in caz contrar.
Rutina backtracking:
void back()
{int AS;
k=1;Init();
while(k>0)
{do {} while((AS =Am_Succesor()) && !E_Valid());
if(AS)
if(Solutie()) Tipar();
else{k++;Init();}
else k--;}}
Observatii:
Pe un anumit nivel (k) se cauta succesorul atat timp cat exista succesor care nu este
valid. Variabila AS are rolul de a retine daca, atunci cand s-a iesit din ciclu, am avut
succesor, caz in care acesta este valid (contrar nu s-ar fi iesit din ciclu ).
Toate variabilele cum ar fi stiva (st) nivelul la care s-a ajuns (k), sunt variabile
globale.
Problemele rezolvate prin aceasta metoda necesita un timp indelungat de rulare. Din
acest motiv este bine sa utilizam metoda numai atunci cand nu avem la dispozitie un alt
algoritm, mai eficient.
Mentionam ca exista probleme ptr. care nu se cunosc algoritmi eficienti de rezolvare,
deci backtracking este indicat.
Rezolvarea iterativa propusa incalca principiul stivei atunci cand verificam conditiile
de continuare, atunci cand tiparim solutia gasita, pentru ca accesam orice nivel al stivei.
Consider ca o structura trebuie folosita ca atare atunci cand este strict necesar. De
exemplu, chiar si segmentul de stiva al programului poate fi accesat oriunde. Asta nu
inseamna ca acolo nu se utilizeaza din plin "mecanismul" stivei.
Rutina prezentata corespunde variantei iterative.
1 2 3
1 2 2 2 2
1 1 1 1 1 1
1 2 3
3 3 3 3 1
1 1 1 1 2 2
1 2 3 1
1 1 1 2 3 3
2 2 2 2 2 2
Observam ca a treia dama nu poate fi plasata in linia a 3-a. Incercam atunci plasarea celei de-
a doua dame in coloana a 4-a. A treia dama nu poate fi plasata decat in
D
coloana a 2-a. D
D D
D
In aceasta situatie dama a 4-a nu mai poate fi asezata. Incercand sa avansam cu dama a 3-a,
observam ca nu este posibil sa o plasam nici in coloana a 3-a, nici in coloana a 4-a, deci o
vom scoate de pe tabla. Dama a doua nu mai poate avansa, deci si ea este scoasa de pe tabla.
Avansam cu prima dama in coloana a 2-a. A doua dama nu poate fi asezata decat in coloana
a 4-a.
D D
D
Dama a 3-a se aseaza in prima coloana. Acum este posibil sa plasam a 4-a dama in coloana a
3-a si astfel am obtinut o solutie a problemei.
D D
D D
D D
D
Algoritmul continua in acest mod pana cand trebuie scoasa de pe tabla prima dama.
Pentru reprezentarea unei solutii putem folosi un vector cu n componente (avand in
vedere ca pe fiecare linie se gaseste o singura dama ). Exemplu: pentru solutia gasita
avem vectorul st ce poate fi asimilat unei stive.
Doua dame se gasesc pe aceeasi diagonala daca si numai daca este indeplinita
conditia:
3 ST(4)
1 ST(3) In general ST(i)=k semnifica faptul
4 ST(2) ca pe linia i dama ocupa pozitia k.
ST(1)
2
Exemplu: in tabla 4×4 avem situatia:
D D
D D
sau situatia:
st(1)=1 i=1 st(1)=3 i=1
st(3)=3 j=3 st(3)=1 j=3
| st(1) - st(3) | = | 1 – 3 | = 2 | st(i) - st(j) | = | 3 – 1 | = 2
| i - j | = | 1- 3 | = 2 |i-j|=|1-3|=2
Programul de generare a tuturor solutiilor problemei celor n dame, are o singura
conditie suplimentara, in functia E_Valid, fata de programul de generare a permutarilor.
#include<iostream>
#include<stdlib.h>
using namespace std;
int st[100],n,k;
void init()
{st[k]=0;}
int am_succesor()
{if(st[k]<n)
{st[k]++;
return 1;}
else
return 0;}
int e_valid()
{for(int i=1;i<k;i++)
if(st[k]==st[i] || abs(st[k]-st[i])==abs(k-i))
return 0;
return 1;}
int solutie()
{return k==n;}
void tipar()
{cout<<endl;
for(int i=1;i<=n;i++)
cout<<st[i]<<" ";
cout<<endl;}
void back()
{int as;
k=1;
init();
while(k>0)
{do {} while((as=am_succesor()) && !e_valid());
if(as)
if(solutie())
tipar();
else
{k++;
init();}
else
k--;}}
int main()
{cout<<"n=";
cin>>n;
back();
return 0;} Complexitate timp:O(n!) (mult mai mic decât
permutările brute, datorită tăierilor), de spațiu:O(n) (stiva de niveluri)
Ex 3: Produsul cartezian a n multimi. Se dau multimile de mai jos si se cere
produsul cartezian al lor.
A1={1, 2, ……….., k1}
A2={1, 2, ……….., k2}
…………………….
An={1, 2, ………., kn}.
Exemplu: A1={1,2}, A2={1,2,3}, A3={1,2,3}.
A1xA2xA3={(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 si un vector A care retine numerele k1, k2, ..., kn,
utilizam metoda backtracking, usor modificata din urmatoarele motive:
orice element aflat pe nivelul k al stivei este valid, motiv pentru care functia
E_valid nu face altceva decat sa returneze 1.
limita superioara pe nivelul k al stivei este data de a[k].
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
…………………………………………………………………
a[1], a[2], ..., a[k] nu contine elementele multimilor, ci dimensiunile lor.
Observatii : Acest algoritm a mai fost prezentat in capitolul anterior. Algoritmul prezentat
aici este de tip backtracking? Intrebarea are sens pentru ca este absent mecanismul de
intoarcere. Vom admite ca si acesta este backtracking, dar “degenerat”.
#include<iostream>
#include<stdlib.h>
using namespace std;
int st[10],a[10],n,k;
void init()
{st[k]=0;}
int am_succesor()
{if(st[k]<a[k])
{st[k]++;
return 1;}
else
return 0;}
int e_valid()
{return 1;}
int solutie()
{return k==n;}
void tipar()
{for(int i=1;i<=n;i++)
cout<<st[i]<<endl;}
void back()
{int as;
k=1;
init();
while(k>0)
{do {} while ((as=am_succesor()) && !e_valid());
if(as)
if(solutie())
tipar();
else
{k++;
init();}
else
k--;}}
int main()
{cout<<"numar total de multimi";
cin>>n;
for(int i=1;i<=n;i++)
{cout<<"a["<<i<<"]=";
cin>>a[i];}
back();
return 0;}
Ex 4: Generarea aranjamentelor. Se citesc n si p. Sa se genereze toate
aranjamentele de n luate cate p.
Din analiza problemei rezulta urmatoarele:
stiva are inaltimea p;
fiecare nivel ia valori intre 1 si n;
elem. plasate pe diverse niveluri trebuie sa fie distincte;
Algoritmul este asemanator cu cel de la permutari, cu deosebirea ca aici stiva are
inaltimea p.
#include<iostream>
using namespace std;
int st[10],n,k,p;
void init()
{st[k]=0;}
int am_succesor()
{if(st[k]<n)
{st[k]++;
return 1;}
else
return 0;}
int e_valid()
{for(int i=1;i<k;i++)
if(st[k]==st[i])
return 0;
return 1;}
int solutie()
{return k==p;}
void tipar()
{for(int i=1;i<=p;i++)
cout<<st[i];
cout<<endl;}
void back()
{int as;
k=1;
init();
while(k>0)
{do {} while((as=am_succesor()) && !e_valid());
if(as)
if(solutie())
tipar();
else
{k++;
init();}
else
k--;}}
int main()
{cout<<"n=";
cin>>n;
cout<<"p=";
cin>>p;
back();
return 0;}
Ex 5: Generarea combinarilor se citesc n si p numere naturale n p. Se cere sa se
genereze toate submultimile cu p elemente ale multimii {1, 2, ..., n}
Pentru rezolvarea problemei trebuie tinut cont de urmatoarele:
Stiva are inaltimea p;
Elementele aflate pe niveluri diferite ale stivei trebuie sa fie distincte;
Pentru a evita repetitia elementele se aseaza in ordine crescatoare: pe nivelul k se va
afla o valoare mai mare decat pe nivelul k-1 si mai mică sau egala cu n-p+k.
#include<iostream>
using namespace std;
int st[10],n,k,p;
void init()
{if(k>1)
st[k]=st[k-1];
else
st[k]=0;}
int am_succesor()
{if(st[k]<n-p+k)
{st[k]++;
return 1;}
else
return 0;}
int e_valid()
{return 1;}
int solutie()
{return k==p;}
void tipar()
{for(int i=1;i<=p;i++)
cout<<st[i];
cout<<endl;}
void back()
{int as;
k=1;
init();
while(k>0)
{do {} while((as=am_succesor()) && !e_valid());
if(as)
if(solutie())
tipar();
else
{k++;
init();}
else
k-- ;}}
int main()
{cout<<"n=";
cin>>n;
cout<<"p=";
cin>>p;
back();
return 0;}
N-are rost sa apelam E_valid.
Ex 6: Problema colorarii hartilor. Fiind data o harta cu n tari, se cer toate solutiile de
colorare a hartii, utilizand cel mult 4 culori, astfel incat doua tari cu frontiera comuna sa fie
colorate diferit. Este demonstrat faptul ca sunt suficiente numai 4 culori pentru ca orice harta
sa poata fi colorata.
Pentru exemplificare, vom considera urmatoarea harta unde tarile sunt numerotate cu cifre
cuprinse intre 1 si 5:
1 4
2 5
Matricea A este simetrica. Pentru rezolvarea problemei se utilizeaza stiva st, unde nivelul k
al stivei simbolizeaza tara k, iar st[k] culoarea atasata tarii k. Stiva are inaltimea n si pe
fiecare nivel ia valori intre 1 si 4.
#include<iostream>
using namespace std;
int st[10],a[20][20],n,k;
void init()
{st[k]=0;}
int am_succesor()
{if(st[k]<4)
{st[k]++;
return 1;}
else
return 0;}
int e_valid()
{for(int i=1;i<=k-1;i++)
if(st[i]==st[k] && a[i][k]==1)
return 0;
return 1;}
int solutie()
{return k==n;}
void tipar()
{cout<<" / Varianta ";
for(int i=1;i<=n;i++)
cout<<"Tara "<<i<<" culoarea "<<st[i]<<"\n";}
void back()
{int as;
k=1;
init();
while(k>0)
{do
{as=am_succesor();
if(as)
e_valid();}
while((as) && !e_valid());
if(as)
if(solutie())
tipar();
else
{k++;
init();}
else
k--;}}
int main()
{cout<<endl<<"Numarul de tari n=";
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i-1;j++)
{cout<<"a["<<i<<","<<j<<"]=";
cin>>a[i][j];
a[j][i]=a[i][j];}
back();
return 0;}
Ex 7: Problema comis-voiajorului. Un comis-voiajor trebuie sa viziteze un numar n
de orase. Initial, acesta se afla in unul dintre ele, notat 1. Comis voiajorul doreste sa nu treaca
de doua ori prin acelasi oras, iar la intoarcere sa revina in orasul 1. Cunoscand legaturile
existente intre orase, se cere sa se tipareasca toate drumurile posibile pe care le poate efectua
comis-voiajorul.
Exemplu: in figura alaturata sunt simbolizate cele 6 orase, precum si drumurile existente
intre ele.
2 3
1
4
6 5
Legaturile existente intre orase sunt date in matricea An,n. Elementele matricei A pot fi 0 sau
1 (matricea este binara)
2 De la orasul 1 la orasul 2
1
2
2 Orasul 2 se mai gaseste in stiva, deci nu este acceptat.
1
3
De la orasul 2 la orasul 3 exista drum; prin orasul 3 nu s-a mai trecut, orasul 3
2
este acceptat.
1
Algoritmul continua in acest mod pana se ajunge din nou la nivelul 1, caz in care algoritmul
se incheie.
Un succesor, intre 2 si n, aflat pe nivelul k al stivei, este considerat valid daca sunt
indeplinite simultan urmatoarele conditii:
nu s-a mai trecut prin orasul simbolizat de succesor, deci acesta nu se regaseste in
stiva;
exista drum intre orasul aflat pe nivelul k-1 si cel aflat pe nivelul k;
daca succesorul se gaseste pe nivelul n, sa existe drum de la el la orasul 1.
#include<iostream>
using namespace std;
int st[10],a[20][20],n,k;
void init()
{st[k]=1;}
int am_succesor()
{if(st[k]<n)
{st[k]++;
return 1;}
else
return 0;}
int e_valid()
{if(!a[st[k-1]][st[k]])
return 0;
else
for(int i=1;i<=k-1;i++)
if(st[i]==st[k])
return 0;
if(k==n && !a[1][st[k]])
return 0;
return 1;}
int solutie()
{return k==n;}
void tipar()
{for(int i=1;i<=n;i++)
cout<<"Nodul"<<st[i]<<endl;
cout<<"-------"<<endl;}
void back()
{int as;
k=2;
init();
while(k>0)
{do{}while((as=am_succesor()) && !e_valid());
if(as)
if(solutie())
tipar();
else
{k++;
init();}
else
k--;}}
int main()
{int i,j;
cout<<"Numar de noduri"<<endl;
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=i-1;j++)
{cout<<"a["<<i<<”,”<<j<<"]=";
cin>>a[i][j];
a[j][i]=a[i][j];}
st[1]=1;
back();
return 0;}
Backtracking recursiv
Problemele incluse in acest capitol sunt rezolvate prin utilizarea tehnicii backtracking,
insa aceasta ca idee de cautare a solutiilor, nu ca rutina standardizata.
Ex 1: Problema celor n dame. Fiind data o tabla de sah n×n, se cer toate solutiile de
aranjare a n dame, astfel incat sa nu se afle doua dame pe aceiasi linie, coloana sau diagonala
(damele sa nu se atace reciproc).
#include<iostream>
#include<stdlib.h>
using namespace std;
int t[20],n; /*memorăm fiecare soluție într-un vector t, considerând că o căsuță k
a vectorului reprezintă linia k iar conținutul ei, adică t[k] va conține numărul
coloanei în care vom plasa regina*/
void tipar()
{for(int i=1;i<=n;i++)
cout<<t[i];
cout<<endl;}
void dame(int k)
{int i,j,corect;
if(k==n+1) //k a dep niv compl,pt ca nu se stie inca daca e sol pîn la dame(k+1);
tipar();
else
{for(i=t[k]+1;i<=n;i++)
{t[k]=i;//pe poz k incerc sa pun toate valorile de la 1 la n.
corect=1;
for(j=1;j<k;j++)//pt j<=k abs (t[k]-t[k])==abs(k-k))
if(t[j]==t[k] || abs(t[k]-t[j])==abs(k-j))//sa nu fie pe aceeasi coloana si diagonala
corect =0;
if(corect)
dame(k+1);}} //urca un nivel in stiva
t[k]=0;} //initializam cu zero nivelul respectiv in stiva daca nu e solutie
int main()
{cout<<"n=";
cin>>n;
dame(1);
return 0;}
0 1 1 0
A= 0 0 0 1
0 1 1 1
1 0 0 0
Suprafata inchisa este data de elementele A(1, 1), A(2, 1), A(2, 2), A(2, 3), A(3,1).
Consideram coordonatele (2, 3) ale unui punct situat in interiorul acestei suprafete.
Dupa executia programului, matricea trebuie sa arate astfel:
1 1 1 0
A= 1 1 1 1
1 1 1 1
1 0 0 0
a) Algoritmul se dovedeste extrem de util in colorarea unei suprafete inchise atunci cand
sunt cunoscute coordonatele unui punct situat in interiorul ei. Acest algoritm este
cunoscut si sub denumirea de algoritm FILL.
Pentru rezolvare se foloseste functia Scriu(), care se autoapeleaza. Initial, matricea se
bordeaza cu doua linii si doua coloane ce contin elemente care au valoarea 1. Acesta are ca
scop evitarea testului de iesire din matrice.
Functia Scriu() functioneaza astfel:
- testeaza daca elementul matricei la care s-a ajuns are valoarea 0;
- in caz afirmativ, acesta ia valoarea 1, iar functia se autoapeleaza pentru fiecare dintre
elementele invecinate (sus, jos, dreapta, stinga);
- in caz contrar, se iese din functie.
#include<iostream>
using namespace std;
int a[10][10],i,j,m,n,x,y;
void scriu(int x,int y,int a[10][10])
{if(a[x][y]==0)
{a[x][y]=1;
scriu(x+1,y,a);
scriu(x,y+1,a);
scriu(x-1,y,a);
scriu(x,y-1,a);}}
int main()
{cout <<"M=";cin>>m;
cout<<"N=";cin>>n;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{cout<<"a["<<i<<","<<j<<"]=";
cin>>a[i][j];}
for(i=1;i<=n;i++)
{a[0][i]=1;
a[m+1][i]=1;}
for(i=1;i<=m;i++)
{a[i][0]=1;
a[i][n+1]=1;}
cout<<"x";cin>>x;
cout<<"y=";cin>>y;
for(i=1;i<=m;i++)
{for(j=1;j<=n;j++)
cout<<a[i][j];
cout<<endl;}
scriu(x,y,a);
cout<<endl<<endl;
for(i=1;i<=m;i++)
{for(j=1;j<=n;j++)
cout<<a[i][j];
cout<<endl;}
return 0;}
Ex 6: Problema fotografiei (aplicaţie FILL). O fotografie alb-negru este prezentata
sub forma unei matrice binare. Ea infatiseaza unul sau mai multe obiecte. Portiunile
corespunzătoare obiectului (sau obiectelor) in matrice au valoarea 1. Se cere sa se determine
daca fotografia reprezintă unul sau mai multe obiecte.
In matricea următoare sunt reprezentate doua obiecte:
In matricea de mai jos este reprezentat un singur obiect.
0110
A= 0001
0111
1000
Ca si in problemele anterioare, spre a evita testul iesirii din matrice, aceasta este
bordata cu linii si coloane avand valoarea 0. Algoritmul este tot cel din problema anterioara
(FILL), dar aici cautarea se face pe 8 directii.
In programul principal se citeste matricea si se cauta primul element 1 printre
elementele acesteia. Se apeleaza apoi functia compact() care are rolul de a marca cu 0 toate
elementele matricei care apartin acestui obiect identificat. La revenire, se testeaza daca mai
exista elemente cu valoarea 1 in matrice. In caz afirmativ, se poate trage concluzia ca in
fotografie aveam initial mai multe obiecte; astfel, fotografia continea un singur obiect.
#include<iostream>
using namespace std;
int a[10][10],i,j,m,n,x,y,gasit;
void compact (int x,int y,int a[10][10])
{if(a[x][y])
{a[x][y]=0;
compact(x-1,y,a);
compact(x-1,y+1,a);
compact(x,y+1,a);
compact(x+1,y+1,a);
compact(x+1,y,a);
compact(x+1,y-1,a);
compact(x,y-1,a);
compact(x-1,y-1,a);}}
int main()
{cout<<"M=";cin>>m;
cout<<"N=";cin>>n;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{cout<<"a["<<i<<','<<j<<"]=";
cin>>a[i][j];}
for(i=1;i<=n;i++)
{a[0][i]=0;
a[m+1][i]=0;}
for(i=1;i<=m;i++)
{a[i][0]=0;
a[i][n+1]=0;}
x=0;
do
{x++;
y=0;
do
{y++;}
while(y!=n && a[x][y]!=1);}
while((x!=m) && a[x][y]!=1);
compact(x,y,a);
gasit=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(a[i][j]==1)
gasit=1;
if(gasit)
cout<<"mai multe obiecte";
else
cout<<"un obiect";
return 0;}
Greedy
Eficienta de transport este 1 pentru primul obiect, 4 pentru al doilea si 2 pentru al treilea. In
concluzie, obiectul 2 se încarca in întregime in rucsac, obţinând un câștig de 4 si ramane o
capacitate de transport de 2 unitati de greutate. Se încarcă 2/3 din obiectul 3 pentru care se
obţine câștigul 4. Castigul obţinut in total este 8. Se remarca strategia GREEDY prin
alegerea obiectului care va fi transportat, alegere asupra căreia nu se revine.
// problema rucsacului
#include<iostream>
using namespace std;
double c[9],ef[9],g[9],gv,man,cistig;
int n,i,man1,inv,ordine[9];
int main()
{cout<<"greutatea ce poate fi transportata=";
cin>>gv;
cout<<"numar de obiecte=";
cin>>n;
for(i=1;i<=n;i++)
{cout<<"c["<<i<<"]=";
cin>>c[i];
cout<<"g["<<i<<"]=";
cin>>g[i];
ordine[i]=i;
ef[i]=c[i]/g[i];}
do
{inv=0;
for(i=1;i<=n-1;i++)
if(ef[i]<ef[i+1])
{man=ef[i];
ef[i]=ef[i+1];
ef[i+1]=man;
man=c[i];
c[i]=c[i+1];
c[i+1]=man;
man=g[i];
g[i]=g[i+1];
g[i+1]=man;
inv=1;
man1=ordine[i];
ordine[i]=ordine[i+1];
ordine[i+1]=man1;}}
while(inv);
i=1;
while(gv>0 && i<=n)
{if(gv>g[i])
{cout<<"obiectul "<<ordine[i]<<' '<<1<<endl;
gv-=g[i];
cistig+=c[i];}
else
{cout<<"obiectul "<<ordine[i]<<' '<<gv/g[i]<<endl;
cistig+=c[i]*gv/g[i];
gv=0;}
i++;}
cout<<"cistig total = "<<cistig;
return 0;}
Programarea orientată pe obiecte
Principiile programării orientate pe obiecte
5.2 Încapsularea
Definitie. Prin încapsulare intelegem mecanismul prin care datele (variabilele) si functiile
(numite in acest caz si metode) sunt plasate impreuna, intr-o unica structura.
In C++ aceasta se realizeaza printr-un tip abstract, numit class. In C++ se face distinctie intre
clasa, care este tipul abstract, si obiectul propriu-zis, care este instantierea clasei respective.
Iată formă simplificată a tipului de clasă:
class
{ [private]
date;
metode;
[protected]
date;
metode;
[public]
date;
metode; }
Între paranteze drepte sunt trecuţi modificatorii public, protected, private. Un modificator
are efect până la întâlnirea altuia, sau pînă la sfîrșitul definiţiei.
- modificatorul private are rolul de a interzice accesul la date și metode din afara
obiectului;
- modificatorul public are rolul de a permite accesul afara obiectului la date și metode;
- modificatorul protected va fi prezentat în alt context.
În absenţa modificatorilor, este interzis accesul la date și metode din afara obiectului.
Exemplu.
La matematică va-ti întâlnit cu numere complexe! Ele sunt de forma: z=x+iy, unde x, y
R. In C++ există mai multe tipuri care reţin numere reale! Prin mecanismul OOP
incercăm să construim singuri un tip care permite memorarea și prelucrarea numerelor
complexe.
class complex Un numar complex cuprinde:
{ - partea reala x;
public: - partea imaginara y;
float x, y; - o functie care returneaza modulul:
float modul();
};
Descrierea numarului complex o vom face intr-un tip separat, numit complex:
#include<math.h>
class complex
{public:
float x, y;
float modul();};
float complex: :modul()
{return sqrt(x*x+y*y);}
Definirea funcţiei modul (metodă a clasei complex) s-a făcut în afara clasei
respective. Pentru a preciza faptul că funcţia este metodă a clasei complex, utilizâm în
antetul definiţiei operatorul “: :”, numit și operator de rezoluţie:
float complex: :modul()
Există posibilitatea ca funcţia să fie definită în interiorul clasei. In acest caz ea va fi tratată de
compilator ca funcţiei inline. Reamintim că pentru o astfel de funcţie orice apel este înlocuit
prin codul ei. Astfel se obţine o economie de timp - cea necesară saltului la cod și revenirii -
dar se mărește codul programului. Din acest motiv vom prefera să definim funcţia în afara
clasei.
Ex 1: Programul următor utilizează un obiect complex pentru care atribuie valori părtii reale
si imaginare apoi le tipăreste împreună cu modulul acestuia.
#include<iostream>
#include”[Link]”
using namespace std;
int main()
{complex z ;
z.x=3; z.y=4;
cout<<z.x<<” “<<z.y<<” “ <<[Link]();
return 0;
getche();}
Obiectul propriu zis a fost declarat ca o variabilă. El se numeste z.
Obiectul este, de fapt, instantierea clasei din care face parte.
Ca si în cazul tipului struct accesul la datele(metodele) membre se realizează prin
numele obiectului urmat de operatorul ”.” si de numele variabilei (metodei): z.x, z.y,
[Link]().
Prin utilizarea obiectului de tip complex, construit acum, putem lucra “aproape” la fel ca
si cum limbajul ar contine tipul complex.
Ex 2: Programul următor citeste un vector de numere complexe si tipareste cel mai mare
modul al acestora.
#include<iostream>
#include”[Link]”
using namespace std;
int main()
{complex v[100] ;
int n,i;
float max;
cout<<”n=”;cin>>n;
for(i=0;i<n ;i++)
{cout<<”Numarul complex “<<i+1<<endl;
cout<<”Partea reala “; cin>>v[i].x;
cout<<”Partea imaginara ” cin>>v[i].y;}
max=v[0].modul();
for(i=1;i<n;i++)
if(v[i].modul()>max)
max=v[i].modul();
cout<<max;
return 0;}
Ex 3: Programul următor sorteaza un vector de numere complexe, descrescator, in functie de
modulul lor.
#include<iostream>
#include”[Link]”
using namespace std;
int main()
{complex v[100], man;
int n,i, inversari;
cout<<”n=”;cin>>n;
for(i=0;i<n ;i++)
{cout<<”Numarul complex “<<i+1<<endl;
cout<<”Partea reala “; cin>>v[i].x;
cout<<”Partea imaginara ” cin>>v[i].y;}
do
{inversari=0;
for(i=0;i<n-1;i++)
if(v[i].modul()<v[i+1].modul())
{man=v[i];
v[i]=v[i+1];
v[i+1]=man;
inversari=1;}}
while(inversari);
for(i=0;i<n;i++)
cout<<v[i].x<<” “<<v[i].y<<endl;
return 0;}
Revenim asupra declaratiilor obiectelor. Fie declaratia: complex a, b; Au fost declarate două
obiecte numite a si b.
Întrebarea 1: care este mecanismul ce permite declararea (instantierea) obiectelor?
În absenta altor definitii, clasei i se atasează în mod implicit o metodă specială, numita,
constructor, care are rolul de a permite declararea obiectelor. În acest fel se alocă spatiul de
memorie necesară obiectelor declarate. De asemenea, numele lor pot fi folosite pentru
accesarea datelor si metodelor. Un astfel de constructor il numim constructor generat implicit
si are următoarele caracteristici:
- nu are parametrii formali;
- consecinta absentei parametrilor formali este dată de faptul că nu este permisă initializarea
la declarare a datelor membru;
- nu se generează, în cazul în care clasa are atasat un alt constructor, fara parametri.
Întrebarea 2: programatorul poate înzestra clasa cu o metodă constructor proprie?
Răspunsul este afirmativ, cu mentiunea că este necesar să respectăm anumite reguli
suplimentare, comparativ cu o metodă obisnuită.
- O metodă constructor are întotdeauna numele clasei din care face parte. Ea este apelată
automat la declararea obiectelor.
- Un constructor este o functie fără tip. Cu toate acestea, în dreptul tipului nu se trece
cuvântul cheie void.
Observatii importante:
- Functiile obtinute prin supraîncărcarea operatorilor au aceeasi prioritate si asociativitate cu
operatorii respectivi;
- Functiile obtinute prin supraîncărcarea operatorilor au aceeasi n-aritate ca si
operatorii respectiv. Astfel:
Dacă operatorul este unar si functia este unară deci nu are parametri;
Dacă operatorul este binar si functia este binară. Aceasta înseamnă că are un singur
parametru.
- Operatorul ’?:’ nu poate fi supraîncărcat.
- In cazul supraîncarcarii operatorilor "++" si " - - " nu se face distinctie între aplicarea a
postfixată si prefixată.
Anumiti operatori prezintă particularităti în legătură cu supraîncărcarea. Vom prezenta câtiva
dintre acestia.
Ex 2: Supraincărcarea operatorului [ ].
Acest operator este binar. De exemplu a[3] se poate scrie ca *(a+3). Vom lua un
exemplu, simplu. Dorim sa retinem un vector, ca tip class. Astfel, o functie va putea intoarce
un vector, ceea ce constituie un avantaj. De asemenea, dorim ca data membru sa fie privata si
accesul la ea sa aiba loc exclusiv prin intermediul unor metode. In aceste conditii obtinem
programul următor:
#include<iostream>
using namespace std;
class vector
{int v[100];
public:
void in(int,int);
int out(int);};
void vector::in(int i, int x)
{v[i]=x ;}
int vector::out(int i)
{return v[i] ;}
int main()
{vector a ;
[Link](3,5);
cout<<[Link](3);}
Observati modul de accesare a unei componente:
- [Link](3,5); componenta 3 ia valoarea 5.
- [Link](3); valoarea retinuta de componenta 3.
Accesul la componentele vectorului este deosebit de greoi. Suntem tentati sa avem un acces
de genul a[3]. Aceasta conduce la ideea supraincarcarii operatorului [ ]. Pornim de la forma
sa generala:
expresie1[expresie2]
Functia corespondenta ei este operatorul[ ]. Vom inlocui expresie1 cu obiectul curent, iar
expresie2 cu indicele de adresare. Metoda operator[ ] va intoarce un sinonim al componentei
accesate.
#include<iostream>
using namespace std;
class vector
{int v[100];
public:
int& operator[](int i);};
int& vector: :operator[](int i)
{return v[i] ;}
int main()
{vector a ;
a[3]=5;
cout<<a[3];}
Ex 3: Supraincărcarea operatorului ( ).
De regula, operatorul ( ) este supraincarcat in scopul permiterii accesului simplificat la datele
unui obiect. In exemplul următor supraincarcam operatorul ( ) pentru a avea acces simplificat
la elementele unei matrice.
#include<iostream>
using namespace std;
class matrice
{int v[10] [5];
public:
int& operator( ) (int i, int j);};
int& matrice::operator( ) (int i, int j)
{return v[i] [j] ;}
int main()
{matrice a ;
a(3,2)=71;
cout<<a(3,2);}
Ex 4: Supraincărcarea operatorului = .
Se pot face atribuiri între obiecte, asa cum suntem obisnuiti. În astfel de cazuri avem o
copiere bit de bit. Mecanismul este simplu: fiecare dată a obiectului aflat in dreapta
operatorului este copiată către data corespunzătoare aflata în stânga.
Nu întotdeauna o astfel de atribuire este satisfăcătoare. Pentru a demonstra aceasta vom porni
de la un exemplu. Programul următor utilizează o clasă numită string. Clasa a fost
construită in scopul efectuării anumitor operatii cu siruri de caractere. Din acest
motiv, fiecare obiect contine adresa din HEAP a sirului atasat, dar nu contine sirul.
Fie două obiecte a si b. Presupunem că a retine adresa sirului "un text", iar b retine adresa
sirului "alt text". Scriem expresia a=b. În ipoteza în care operatorul = nu este supraîncărcat
obiectul a va retine adresa sirului atasat lui b. Pe de o parte, sirul care avea adresa în obiectul
a se pierde, dar rămâne alocat în HEAP, chiar dacă nu mai avem adresa lui. Pe de altă parte,
a si b vor retine adresa unui sir. Dacă, de exemplu, stergem pe b, a va retine adresa unui sir
inexistent.
Datorita celor aratate, inzestram clasa cu un constructor de copiere care efectueaza
urmatoarele:
- alocă spatiu în HEAP – un număr de octeti care sa permita copierea;
- copiază sirul.
Tot asa, supraîncărcam operatorul = cu o metodă care efectuează următoarele:
- eliberează spatiul ocupat de sirul a;
- alocă spatiu în HEAP - număr de octeti care să permită copierea;
- efectueaza copierea.
#include<iostream>
#include <cstring>
using namespace std;
class string
{char* adr;
public:
//constructor
string(char sir[])
{adr=new char[strlen(sir)+1];
strcpy(adr,sir);}
//constructor de copiere
string(string& x)
{adr=new char[strlen([Link])+1];
strcpy(adr, [Link]);}
void operator=(string& x)
{delete adr;
adr=new char[strlen([Link])+1];
strcpy(adr, [Link]);}
void tip()
{cout<<adr<<endl;}};
int main()
{string a(“mama”),b(“bunica”),c=a;
[Link]();[Link]();[Link]();
a=b;[Link]();[Link]();}
Există posibilitatea ca anumite functii, care nu apartin unei clase să poată accesa datele
private ale acesteia, caz in care functiile respective se numesc „functii prieten”.
Pentru a atasa unei clase o functie prieten introducem în interiorul definitiei sale prototipul
functiei prieten, precedat de cuvântul cheie friend.
O functie prieten nu poate accesa datele direct, asa cum poate o metodă a clasei respective, ci
prin intermediul parametrului de tip obiect transmis.
Ex 1: Clasa complex, definită mai jos, are functia prieten modul(), care returnează modulul
numărului complex.
#include<iostream>
#include<math.h>
using namespace std;
class complex
{float x, y;
public:
complex(float, float);
friend float modul(complex& z);};
complex::complex(float v1, float v2)
{x=v1;
y=v2;}
float modul(complex& z)
{return sqrt(z.x*z.x+z.y*z.y);}
int main()
{complex z(3,4);
cout<<modul(z);}
În C++ operatorii pot fi supraîncărcati prin functii prieten.
Ex 2: Dorim sa efectuam suma dintre un număr complex si unul real. Pentru aceasta vom
folosi o functie prieten care supraîncarcă operatorul +. Pentru ca o operatia să fie comutativa,
adică să se poată face si suma dintre un număr real si un număr complex,
vom folosi o altă functie prieten, în care ordinea parametrilor este inversă fată de cea
anterioară.
Vezi exemplul următor:
#include<iostream>
#include<math.h>
using namespace std;
class complex
{float x, y;
public:
complex(float, float);
friend float modul(complex& z);
friend complex operator+(complex& z, float nr);
friend complex operator+( float nr, complex& z);};
complex::complex(float v1, float v2)
{x=v1;
y=v2;}
float modul(complex& z)
{return sqrt(z.x*z.x+z.y*z.y);}
complex operator+(complex& z, float nr)
{complex t(z.x+nr, z.y) ;
return t ;}
complex operator+( float nr, complex& z)
{complex t(z.x+nr, z.y) ;
return t ;}
int main()
{complex z(3,4);
z=z+7 ;
z=3+z ;
cout<<modul(z);}
5.3 Mostenirea
Definitie. Prin mostenirese intelege acea proprietate a claselor prin care un tip nou construit
poate prelua datele si metodele unui tip mai vechi. In C++ acest mecanism mai este cunoscut
sub numele de „derivare a claselor”.
Evident, clasei nou construite i se pot adauga noi date si metode.
Prin acest procedeu se preia soft deja facut care se dezvolta. Avantajul urias al acestui
procedeu este ca persoana care preia un anumit soft trebuie sa cunoasca doar
documentatiade utilizare a soft-ului preluat.
Ideea de baza este urmatoarea: fiind date clasele X1, X2, …Xn, putem construi clasa Xn+1 care
are, pe linga datele si metodele claselo enumerate, date si metode proprii. Clasele X 1, X2, …
Xn se numesc clase de baza, iar clasa Xn+1 clasa derivata.
Ex 1: Clasa numar contine o data membru n si o metoda membru tip(). Clasa numar_d este
derivata din clasa numar. Prin urmare, un obiect obtinut prin instantierea acesteia, are data
membru n si metoda tip(). Pe linga acestea, clasa numar_d are o noua metoda tip(). In
paragraful următor vom analiza rolul modificatorului public din:
class numar_d : public numar
#include<iostream>
using namespace std;
class numar
{public :
int n;
void tip()
{cout<<n<<endl;}};
class numar_d : public numar
{public :
void cit()
{cout<<”n=”;
cin>>n;}};
int main()
{numar_d a;
[Link]();
[Link]();}
Ex 2: Clasa Complex ne permite sa lucram usor cu numere complexe. In timpul utilizarii
acestei clase ne-am dat seama ca ar fi bine sa contina o metoda booleana numita real( ), care
ne permite sa testam daca numarul complex este real sau nu. Dispunem de documentatia
clasei Complex. Nu-i o problema sa definim o clasa noua, numita Complex_d, care contine
datele si metodele clasei Complex, dar care dar care include si noua metoda.
#include<iostream>
#include”[Link]”
using namespace std;
class complex_d : public complex
{public :
int real;};
int complex_d : : real( )
{return y==0;}
int main()
{complex_d z;
z.x=3;
z.y=1;
if ([Link]())
cout<<”numarul este real”;
else
cout<<”numarul nu este real”;}
Unui obiect al clasei de baza i se poate atribui un obiect al unei clase care este derivata
din ea.
Unui obiect al unei clase derivate nu i se poate atribui un obiect al clasei de baza. Se
presupune ca o clasa derivata are date in plus.
Ex 3: Nimeni nu ne opreste sa inzestram clasa derivata cu o metoda obtinuta prin
supraincarcarea operatorului =. Dar si aici datele care apartin exclusiv clasei derivate iau
valori arbitrare (in exemplul următor 0).
#include<iostream>
using namespace std;
class numar
{public:
int m;};
class numar_d : public numar
{public :
int n;
void operator=(numar& x)
{m=x.m;
n=0;}};
int main()
{numar a;
numar_d b;
b.m=3;
b.n=4;
a=b;
cout<<a.m<<endl;
b=a; //nu ar fi permisa
cout<<b.m<<” ”<<b.n;}
O clasa derivata poate contine o functie cu acelasi nume si cu aceeasi lista de
parametri formali ca una a clasei de baza.
Ex 4: In exemplul următor clasa de baza (numar) are o metoda numita tip( ), in care lista
parametrilor formali este vida. Clasa derivata are pe linga metoda tip( ), mostenita, o alta
numita tot tip( ), cu aceeasi lista a parametrilor formali (tot vida). Prin [Link]( ) se apeleaza
metoda tip( ) proprie clasei derivate. In cazul in care dorim sa apelam metoda tip( ) a
clasei de baza scriem: [Link] : : tip( ). Cele doua metode cu acelasi nume difera doar
prin mesajul afisat inaintea tiparirii valorii retinute de variabila.
#include<iostream>
using namespace std;
class numar
{public:
int i;
void tip( )
{cout<<”numar”<<i<<endl;}};
class numar_d : public numar
{public :
void tip( )
{cout<<”numar_d”<<i<<endl;}};
int main()
{numar_d a;
a.i=3;
[Link]( );
a=b;
[Link] : : tip( );}
In situatia in care in clasa derivata se defineste o noua data cu aceleasi nume ca una a
clasei de baza, nu se semnaleaza eroare. Un obiect rezultat ca instantiere a unei clase
derivate va avea doua date cu acelasi nume. Implicit se adreseaza variabila definita in
clasa derivata, dar este posibil sa adresam si data clasei de baza la fel ca in cazul
functiilor.
Ex 4:
#include<iostream>
using namespace std;
class numar
{public:
int i;};
class numar_d : public numar
{public :
int i;};
int main()
{numar_d a;
a.i=2;
[Link] : : i=3;
cout<<a.i<<” “<<[Link] : : i;}
In urma utilizarii obiectelor Multime s-a constatat ca ar mai fi nevoie de doua metode:
1. Un constructor care sa permita citirea unei multimi dintr-un fisier text,in care elementele
se gasesc toate pe o linie.
2. O metoda care sa returneze numarul de elemente ale multimii, numita Card( ).
Ex 1: Pentru aceasta vom construi o noua clasa numita Multime_g, care mosteneste clasa
Multime. La noul tip de obiect se adauga metodele de mai sus si se obtine:
#include<fstream>
#include „[Link]”
using namespace std;
class Multime_g : public Multime
{public:
Multime_g(char Nume_fis[20]);
Multime_g {};
int Card( );};
5.4 Polimorfism
Programare dinamică
6.1. Generalităţi
Fie o problemă a cărei rezolvare este cerută pentru un număr natural n dat. Uneori se
poate aplica un raţionament de genul: dacă știm să rezolvăm problema pentru toate valorile
strict mai mici decât n, atunci putem rezolva problema și pentru n dat. Dacă este așa, atunci,
pe baza aceluiași raţionament, înseamnă că dacă știm să rezolvăm problema pentru toate
valorile strict mai mici decât n-1, atunci știm să rezolvăm problema pentru n-1 și, așa cum
am arătat, pentru n. Repetând acest raţionament ajungem să rezolvăm problema pentru n=1
și, eventual, pentru n=2. O astfel de problemă este foarte ușor de rezolvat. După care
rezolvăm problema pentru n=3, apoi n=4, ș.a.m.d., până se ajunge la acel n cerut de
problemă. De aici rezultă necesitatea găsirii unor relaţii de recurenţă.
O persoană trebuie să urce n scări. Se știe că persoana respectivă poate urca fie o scară, fie
două deodată. Întrebarea este: în câte moduri poate urca persoana n scări?
O primă idee este de a descompune pe n ca sumă de 1 și 2 în toate modurile posibile și de a
număra soluţiile. Problema se poate rezolva aplicând tehnica Backtracking (exerciţiu!). Dar
în acest caz obţinem un timp exponenţial…
O rezolvare prin programarea dinamică se poate face în felul următor:
- dacă n=1, o scară se poate urca într-un singur fel;
- dacă n=2, se poate urca o scară și apoi o altă scară (un fel) sau deodată două scări (altă
modalitate), prin urmare, există două modalităţi de a urca două scări.
Până acum am rezolvat problema pentru n=1 și pentru n=2. Dacă notăm cu un numărul de
feluri în care se pot urca n scări, atunci știm că u1=1 și u2=2.
Acum, pentru a urca n scări putem proceda astfel: se urcă n-2 scări și deodată două scări sau
se urcă n-1 scări, după care se mai urcă o scară. În câte feluri se pot urca n-2 scări? În un-2
feluri. În câte feluri se pot urca n-1 scări? În un-1 feluri. Atunci, n scări se pot urca în un=un-
1+un-2 feluri. De ce le-am adunat? Pentru că în acest fel se obţin doar soluţii diferite. Orice
soluţie care provine din un-1 se termină prin a urca la sfârșit o scară și orice soluţie care
provine din un-2 se termină prin a urca la sfârșit două scări. Dacă soluţiile sunt diferite,
atunci se pot aduna.
Astfel, am obţinut o relaţie de recurenţă binecunoscută. Acum, problema se reduce la a
calcula un din această relaţie. Deja știm să rezolvăm o astfel de relaţie, revedeţi recursivitatea
(aţi întâlnit-o la șirul lui Fibonacci). Mai mult, un se poate calcula în O(n), adică liniar.
Tot atunci când aţi studiat recursivitatea aţi văzut că rezolvarea prin utilizarea mecanismului
recursivităţii a acestei relaţii este catastrofală din punct de vedere al timpului de calcul, fiind
exponenţială.
În programarea dinamică, de cele mai multe ori, pentru a rezolva o problemă se scrie o
relaţie de recurenţă. Relaţia de recurenţă se rezolvă apoi iterativ.
Problema prezentată face parte din categoria problemelor de numărare. În acest capitol veţi
întâlni și alte probleme de numărare.
Prin programare dinamică puteţi rezolva și probleme de optim în care se cere o soluţie care
să maximizeze sau să minimizeze o anumită funcţie. În acest caz, criteriile de mai jos vă pot
fi de folos. Menţionăm că înţelegerea lor se face în timp, studiind mai multe exemple, motiv
pentru care este bine ca, atunci când rezolvaţi o problemă, să reveniţi asupra lor.
Se consideră o problemă în care rezultatul se obţine ca urmare a unui șir de decizii D1, D2,...,
Dn. În urma deciziei D1, sistemul evoluează din starea S0 în starea S1, în urma deciziei D2,
sistemul evoluează din starea S1 în starea S2, ..., în urma deciziei Dn, sistemul evoluează din
starea Sn-1 în starea Sn.
Dacă D1, D2,....Dn este un șir de decizii care conduce sistemul în mod optim din S0 în Sn,
atunci trebuie îndeplinită una din condiţiile următoare (principiul de optimalitate):
1) Dk...Dn este un șir de decizii ce conduce optim sistemul din starea Sk-1 în starea Sn, ∀k,
1≤k≤n;
2) D1...Dk este un șir de decizii care conduce optim sistemul din starea S0 în starea Sk, ∀k,
1≤k≤n;
3) Dk+1...Dn, D1...Dk sunt șiruri de decizii care conduc optim sistemul din starea Sk în
starea Sn, respectiv din starea S0 în starea Sk, ∀k, 1≤k≤n.
⇒ Dacă principiul de optimalitate se verifică în forma 1), spunem că se aplică programarea
dinamică metoda înainte.
⇒ Dacă principiul de optimalitate se verifică în forma 2), spunem că se aplică programarea
dinamică metoda înapoi.
⇒ Dacă principiul de optimalitate se verifică în forma 3), spunem că se aplică programarea
dinamică metoda mixtă.
Programarea dinamică se poate aplica problemelor la care optimul general implică optimul
parţial.
Dacă drumul cel mai scurt între București și Suceava trece prin Focșani, atunci porţiunea din
acest drum, dintre București și Focșani, este cea mai scurtă, ca și porţiunea dintre Focșani și
Suceava (dacă n-ar fi așa, drumul considerat între București și Suceava nu ar fi optim).
Faptul că optimul general determină optimul parţial, nu înseamnă că optimul parţial
determină optimul general.
Fiind date drumurile cele mai scurte de la București la Cluj și de la Cluj la Suceava, nu
înseamnă că drumul optim de la București la Suceava trece prin Cluj.
Cu toate acestea, faptul că optimul general impune optimul parţial ne este de mare ajutor:
căutăm optimul general, între optimele parţiale, pe care le reţinem la fiecare pas. Oricum,
căutarea se reduce considerabil.
6.2. Problema triunghiului
Enunţ. Se consideră un triunghi de numere naturale format din n linii. Prima linie conţine
un număr, a doua două numere, ..., iar ultima, n numere naturale. Cu ajutorul acestui triunghi
se pot forma sume de numere naturale în felul următor:
se pornește cu numărul din linia 1;
succesorul unui număr se află pe linia următoare plasat sub el (aceeași coloană) sau pe
diagonală la dreapta (coloana crește cu 1).
Care este cea mai mare sumă care se poate forma astfel și care sunt numerele care o
alcătuiesc?
Exemplu: Pentru n=4, se consideră triunghiul de mai jos:
2
35
634
5614
Se pot forma mai multe sume:
S1=2+3+6+5=16;
S2=2+5+4+1=12;
Sk=2+3+6+6=17 (care este și suma maximă).
Rezolvare. Cum am putea rezolva această problemă?
A) O primă idee ar fi să încercăm o abordare a ei prin metoda Greedy. Aceasta presupune ca,
la fiecare pas, să selectăm de pe linia respectivă cel mai mare element dintre cele două care
pot fi alese. Astfel, de pe linia 1 selectăm 2, de pe linia a 2-a, 5, de pe linia a 3-a, 4, iar de pe
linia a 4-a, 4. Înseamnă că suma este 2+5+4+4=15. Observăm că în acest fel nu am reușit să
obţinem suma maximă. De ce? Când facem o alegere care maximizează suma la un moment
dat, s-ar putea să nu mai putem alege pentru liniile următoare elementele care maximizează
suma. Urmăriţi soluţia optimă din exemplul dat. Prin urmare, "soluţia" propusă nu este
corectă.
B) Să încercăm altfel. Se cere suma maximă. Atunci ar trebui să considerăm toate
"drumurile" posibile de la prima linie la ultima. Pentru fiecare astfel de drum să calculăm
suma care se poate forma și să selectăm suma maximă. Este corectă o astfel de rezolvare?
Evident, da. Cum am putea genera toate aceste drumuri? Dacă am spus "toate", atunci ne
gândim la metoda Backtracking. Mai jos, prezentăm programul obţinut aplicând acest
algoritm:
int t[50][50],sol[50],
drum[50],n,i,j,max=0;
void back(int k)
{int i,j,s=t[1][1];
if (k==n+1)
{for (i=2;i<=n;i++)
s+=t[i][sol[i]];
if (s>max)
{for (i=1;i<=n;i++)
drum[i]=sol[i];
max=s;}}
else
{for (i=sol[k-1];
i<=sol[k-1]+1;i++)
{sol[k]=i;
back(k+1);}}}
int main()
{cout<<"n="; cin>>n;
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
{cout<<"t["<<i<<','
<<j<<"]=";
cin>>t[i][j];}
sol[1]=1;
back(2);
cout<<"Suma maxima"<<endl;
for (i=1;i<=n;i++)
cout<<drum[i]<<" ";}
Să observăm că se pot forma 2n-1 sume de acest fel.
Exerciţiu. Demonstraţi prin inducţie că numărul de sume care se pot forma este corect.
A lua în considerare toate aceste sume nu este eficient, pentru că avem un algoritm în O(2n).
Am putea accepta o astfel de soluţie, cu toate consecinţele ei, numai dacă n-ar exista o alta,
eficientă.
Exerciţiu. Pentru a testa modul în care funcţionează acest algoritm, modificaţi programul
pentru a accepta intrări de la un fișier text, creaţi un astfel de fișier și analizaţi timpul în care
se obţine soluţia pentru n=40.
C) Încercăm să rezolvăm problema prin aplicarea metodei programării dinamice. Verificăm
principiul programării dinamice. Fie un șir de n numere care respectă condiţiile problemei și
care formează suma maximă: n1, n2, ..., ni, ..., nn. Este clar că numerele de la ni ... nn
formează o sumă maximă în raport cu sumele care se pot forma începând cu numărul ni.
Dacă această sumă nu ar fi maximă, atunci ar exista o altă alegere de numere care ar
maximiza-o. Înlocuind în șirul iniţial numerele de la ni ... nn cu cele alese pentru a maximiza
suma, vom obţine o soluţie în care suma este mai mare.
Pentru exemplul dat, cunoaștem soluţia optimă: 2+3+6+6. Aceasta înseamnă că, dacă de pe
linia 2 se pornește cu 3, cea mai mare sumă care se poate forma, în condiţiile problemei, este
3+6+6.
Aceasta contrazice ipoteza. În această situaţie, se poate aplica programarea dinamică, metoda
înainte.
Vom forma un triunghi, de la bază către vârf, cu sumele maxime care se pot forma cu fiecare
număr. Dacă citim triunghiul de numere într-o matrice T și calculăm sumele într-o matrice C,
vom avea relaţiile următoare:
C[n,1]:=T[n,1];
C[n,2]:=T[n,2];
C[n,n]:=T[n,n];
Pentru linia i (i<n), cele i sume maxime se obţin astfel:
C[i,j]=max{T[i,j]+C[i+1,j],T[i,j]+C[i+1,j+1]},
i∈{1,2,...,n-1}, j∈{1,...,i}.
Să rezolvăm problema propusă ca exemplu.
Linia 4 a matricei C va fi linia n a matricei T:
5 6 1 4.
Linia 3 se calculează astfel:
C[3,1]=max{6+5,6+6}=12;
C[3,2]=max{3+6,3+1}=9;
C[3,3]=max{4+1,4+4}=8;
Vom avea:
12 9 8
5614
Linia 2:
C[2,1]=max{3+12,3+9}=15;
C[2,2]=max{5+9,5+8}=14;
15 14
12 9 8
5614
Linia 1:
C[1,1]=max{2+15,2+14}=17;
17
15 14
12 9 8
5614
Aceasta este și cea mai mare sumă care se poate forma.
Pentru a tipări numerele luate în calcul se folosește o matrice numită DRUM în care pentru
fiecare i∈{1,...,n-1} și j∈{1,...,i} se reţine coloana în care se găsește succesorul lui T[i,j].
#include <iostream>
int t[50][50],c[50][50],
drum[50][50],n,i,j;
int main()
{ cout<<"n=";
cin>>n;
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
{ cout<<"t["<<i<<','
<<j<<"]=";
cin>>t[i][j];}
for (j=1;j<=n;j++)
c[n][j]=t[n][j];
for (i=n-1;i>=1;i--)
{ for (j=1;j<=i;j++)
if (c[i+1][j]<c[i+1][j+1])
{ c[i][j]=t[i][j]+
c[i+1][j+1];
drum[i][j]=j+1;}
else
{ c[i][j]=t[i][j]+c[i+1][j];
drum[i][j]=j;}}
cout<<"suma maxima= "
<< c[1][1]<<endl;
i=1; j=1;
while (i<=n)
{ cout<<t[i][j]<<endl;
j=drum[i][j];
i++;}}
6.3. Subșir crescător de lungime maximă
Enunţ. Se consideră un vector cu n elemente întregi. Se cere să se tipărească cel mai lung
subșir crescător al acestuia.
Exemplu. Pentru n=5 se dă vectorul V=(4,1,7,6,7). În acest caz, subșirul tipărit va fi: 4,7,7.
Rezolvare. Problema se poate rezolva pornind de la ideea de a calcula, pentru fiecare
element al vectorului, lungimea celui mai lung subșir crescător care se poate forma începând
cu el. În final, este selectat elementul din vector cu care se poate forma cel mai lung subșir
crescător și acesta este listat.
L(k)={1+max L(i)|V(i)≥V(k), i={k+1,...,n}},k∈{1,2,...,n}.
În practică, folosim un vector L cu n componente, unde L(k) are semnificaţia explicată.
Pentru exemplul nostru vom avea:
L=(3,3,2,2,1).
Componentele vectorului L au fost calculate astfel:
cel mai lung subșir care se poate forma cu elementul 7, aflat pe ultima poziţie, are
lungimea 1;
cel mai lung subșir care se poate forma cu elementul 6, aflat pe poziţia 4, are lungimea 2
(1+L(5)), pentru că pe poziţia 5 se găsește elementul 7 care este mai mare decât 6;
cel mai lung subșir care se poate forma cu elementul aflat pe poziţia 3 are lungimea 2
(1+L(5)) deoarece 7 este egal cu 7;
algoritmul continuă în acest mod până se completează L(1).
După aceasta se calculează maximul dintre componentele lui L, iar cel mai lung subșir
crescător format din elementele vectorului V va avea lungimea dată de acest maxim. Pentru a
lista efectiv acel subșir de lungime maximală se procedează astfel:
se caută maximul din vectorul L precum și indicele t, la care se găsește acest maxim;
se afișează V(t);
se găsește și se listează primul element care este mai mare sau egalcu V(t) și are lungimea
mai mică cu 1 (max-1), se actualizează valoarea max cu max-1;
algoritmul continuă până când se epuizează toate elementele subșirului.
Programul este următorul:
#include <iostream.h>
int v[20],l[20],n,i,k,max,t;
int main()
{ cout<<"n="; cin>>n;
for (i=1;i<=n;i++)
{ cout<<"v["<<i<<"]=";
cin>>v[i];}
l[n]=1;
for (k=n-1;k>=1;k--)
{ max=0;
for (i=k+1;i<=n;i++)
if (v[i]>=v[k] && l[i]>max)
max=l[i];
l[k]=1+max;}
max=l[1];
t=1;
for (k=1;k<=n;k++)
if (l[k]>max)
{ max=l[k];
t=k;}
cout<<"lungimea maxima:"<<max
<<endl<<v[t]<<endl;
for (i=t+1;i<=n;i++)
if (v[i]>v[t] && l[i]==max-1)
{ cout<<v[i]<<endl;
max--;}}
Exerciţiu. Cum verificaţi pentru această problemă principiul optimalităţii?
Complexitatea acestui algoritm este O(n2).
Pentru fiecare element al șirului se calculează un maxim. Aceasta presupune parcurgerea
șirului până la capăt. Pentru elementul aflat pe poziţia n-1 se face o comparare, pentru
elementul aflat pe poziţia n-2 se fac 2 comparări, ..., pentru elementul aflat pe poziţia 1 se fac
n-1 comparări.
Prin urmare, numărul de comparări este:
21)n(n1n...21S−=−+++= ,
deci algoritmul are complexitatea O(n2).
6.4. O problemă cu sume
Enunţ. Se citește n>1, număr natural, Suma, număr natural și n numere naturale nenule. Se
cere să se decidă dacă numărul Suma poate fi obţinut ca sumă de numere naturale dintre cele
n citite. În caz afirmativ, să se afișeze un set de numere care, adunate, dau acest rezultat.
Rezolvare. Putem considera toate submulţimile mulţimii {1,2,...,n} și pentru fiecare
submulţime calculăm suma obţinută. Dar... câte submulţimi avem? Avem 2n submulţimi.
Înseamnă că avem un algoritm în O(2n)... Inacceptabil!
Vom prefera un alt algoritm, bazat pe metoda programării dinamice.
Notăm numerele citite cu n1, n2, ..., nn. Fie S=n1+n2+...+nn. Evident, orice sumă care se
poate forma cu numerele citite, poate fi un număr între 1 și S. Vectorul Sume, un vector cu S
componente, va reţine 1 pentru fiecare sumă care poate fi formată și 0 în caz contrar.
La pasul i vom calcula toate sumele care se pot calcula cu numerele n1, n2, ..., ni.
La pasul 1 avem Sume[n1]=1.
La pasul 2 avem Sume[n2]=1 și Sume[n1+n2]=1.
La pasul 3 avem Sume[n3]=1 și Sume[n2+n3]=1, Sume[n1+n2+n3]=1.
...
Dar cum reţinem toţi termenii care alcătuiesc o sumă? Mai simplu decât pare la prima
vedere… Un vector, numit Alege, cu S componente, va reţine pentru fiecare sumă calculată
ultimul termen care intră în alcătuirea ei. Atunci când afișăm soluţia pentru Suma, tipărim
Alege[Suma], apoi Alege[Suma-Alege[Suma]]…
Vom prezenta ca exemplu cazul n=3. Numerele citite sunt 2, 3, 5.
Sumele calculate pot lua valori între 1 și 2+3+5=10. Un vector Suma, cu 10 componente va
reţine 1 pentru fiecare sumă care se poate calcula și 0 dacă, până la acel pas suma nu s-a
putut calcula.
Cu numărul 2 se poate forma o singură sumă: 2.
Sume Alege
0100000000 0200000000
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Cu numerele 2 și 3 se mai pot forma sumele: 3, și 5=2+3.
Suma Alege
0110100000 0230300000
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
#include <iostream.h>
int Castig[50][50],
Alege[50][50],Gr[100],C[100],
i,j,n,G,Obiect;
int main()
{ cout<<"G=";cin>>G;
cout<<"n=";cin>>n;
for(i=1;i<=n;i++)
{ cout<<"Gr["<<i<<"]=";
cin>>Gr[i];
cout<<"C["<<i<<"]=";
cin>>C[i];}
for(i=1;i<=n;i++)
for(j=1;j<=G;j++)
if (Gr[i]<=j)
if(C[i]+Castig[i-1][j-Gr[i]]
>Castig[i-1][j])
{ Castig[i][j]=C[i]+
Castig[i-1][j-Gr[i]];
Alege[i][j]=i;}
else
{Castig[i][j]=Castig[i-1][j];
Alege[i][j]=Alege[i-1][j];}
else
{Castig[i][j]=Castig[i-1][j];
Alege[i][j]=Alege[i-1][j];}
i=n; j=G;
cout<<"Castig total "
<<Castig[i][j]<<endl;
while (Alege[i][j])
{ Obiect=Alege[i][j];
cout<<" Produsul "
<<Alege[i][j]
<<" Greutate "
<<Gr[Alege[i][j]]
<< " Castig "
<<C[Alege[i][j]]<<endl;
while (Obiect==Alege[i][j])
{ j-=Alege[i][j];
i--;}}}
Enunţ (Varianta 2). La fel ca la prima variantă, numai că se presupune că se dispune de un
număr nelimitat de obiecte de un anumit tip. Pentru fiecare tip de obiect se cunoaște
greutatea unui exemplar și câștigul obţinut prin transportul său la destinaţie.
Rezolvare. Pare mai complicat, dar, în realitate, este algoritmul de la problema anterioară,
simplificat. Matricele Castig și Alege devin vectori cu G+1 componente. Se parcurg vectorii
de mai sus, o dată pentru tipul de obiect 1, apoi pentru tipul de obiect 2, ... și, la sfârșit,
pentru tipul de obiect n. La fiecare parcurgere se urmărește să se încarce optim greutăţile
1,2,...,G.
Spre deosebire de algoritmul anterior, unde, la pasul i, se actualizează încărcarea greutăţii j,
pornind de la greutatea j-G[i], încărcată optim cu obiecte de tipuri 1, 2, ..., i-1, aici se
actualizează greutatea j-G[i], încărcată optim cu produsele 1, 2, ..., i-1, i. Aceasta face să se
selecteze mai multe produse de același tip. Evident, există posibilitatea să obţinem un câștig
general mai mare decât la problema precedentă.
Pentru exemplul anterior, puteţi observa mai jos conţinuturile vectorilor Castig și Alege,
după rulare. Soluţia aleasă va fi: Castig 24, se alege de 3 ori obiectul 3.
Programul este prezentat mai jos:
#include <iostream.h>
int Castig[100],Alege[100],
Gr[100],C[100],i,j,n,G;
int main()
{ cout<<"G="; cin>>G;
cout<<"n="; cin>>n;
for(i=1;i<=n;i++)
{ cout<<"Gr["<<i<<"]=";
cin>>Gr[i];
cout<<"C["<<i<<"]=";
cin>>C[i];}
for(i=1;i<=n;i++)
for(j=1;j<=G;j++)
if (Gr[i]<=j)
if(C[i]+Castig[j-Gr[i]] >
Castig[j])
{ Castig[j]=C[i]+
Castig[j-Gr[i]];
Alege[j]=i;}
j=G;
cout<<"Castig total "
<<Castig[G]<<endl;
while (Alege[j])
{ cout<<" Produsul "
<<Alege[j]
<<" Greutate "
<<Gr[Alege[j]]
<< " Castig "
<<C[Alege[j]]<<endl;
j-=Gr[Alege[j]];}}
Indiferent de variantă, complexitatea este O(nG).
O astfel de complexitate se numește complexitate pseudopolinomială. În unele cazuri se
obţin soluţii într-un timp foarte scurt, dar... ce ne facem dacă G este foarte mare, de exemplu
G=2n.
Mai jos, puteţi analiza modelul matematic al problemei rucsacului, varianta discretă, cazul 1.
Puteţi interpreta relaţiile?
Se cer {}0,1,...XX,Xn21∈, astfel încât:
∈+++= ∈≤++
+*n21nn332211*n21nn332211N...cc,c,X...cXcXcXcfmaxNG,...gg,gGX...gXgXgXg
Chiar dacă matematicienilor le place, uneori, să prezinte unele probleme pe un exemplu
copilăresc, ca în cazul de faţă, unde o persoană are un rucsac și încearcă să transporte niște
obiecte, problema are o importanţă uriașă în economie.
Analizaţi exemplele următoare:
1) O firmă de transport dispune de un vapor și într-un port găsește mai multe produse pe care
le poate transporta în ţara de origine. În urma transportului se pot obţine anumite câștiguri
care se cunosc de la început, pentru fiecare produs în parte. Iată că în locul rucsacului avem
un vapor, deja problema prezintă interes... economic!
6.6. Distanţa Levenshtein
Enunţ. Se consideră două cuvinte A și B cu m, respectiv, n caractere. Se cere să se
transforme cuvântul A în cuvântul B prin utilizarea a 3 operaţii:
A – adăugarea unei litere;
M – modificarea unei litere;
S – ștergerea unei litere.
Transformarea se va face prin utilizarea unui număr minim de operaţii. Se va afișa numărul
minim de operaţii și șirul transformărilor.
Exemplu: A=’IOANA’ (m=5), B=’DANIA’ (n=5).
Se va afișa 3 (numărul transformărilor).
Numărul minim de transformări se numește distanţa Levenshtein (noţiunea a fost introdusă,
împreună cu algoritmul de calcul, în anul 1965 de către omul de știinţă rus Vladimir
Levenshtein).
DANIADANAOANAIOANAAMS→→→
Rezolvare. Să observăm că numărul de operaţii necesar conversiei este mai mic sau egal
cu maximul dintre m și n. De exemplu, dacă m<n, putem modifica primele m caractere și
șterge ultimele n-m caractere.
Fie șirul optim care transformă pe A în B. Atunci, șirul transformărilor de la A la Tk este
optim. Dacă, prin absurd, nu ar fi optim, înseamnă că există un alt șir cu număr mai mic de
transformări de la A la Tk. Dacă înlocuim acest șir în șirul transformărilor de la A la B, se
obţin mai puţine transformări, deci se contrazice optimalitatea soluţiei iniţiale. În concluzie,
șirul transfomărilor de la A la Tk este optim.
În șirul transformărilor, de la un termen la altul, se trece prin efectuarea unei singure operaţii
dintre: adăugarea, modificarea sau ștergerea unui caracter. Aceasta înseamnă că doi termeni
consecutivi ai șirului diferă printr-un singur caracter. Mai mult, în șirul transformărilor, nu
contează ordinea în care efectuăm calculele.
De exemplu, un șir optim de transformări de la IOANA la DANIA este și:
pe lângă șirul modificărilor de mai jos:
DANIADANAOANAIOANAAMS→→→
În ambele șiruri s-au modificat, adăugat, șters aceleași caractere, aflate pe aceleași poziţii în
șirul iniţial, doar ordinea diferă. Astfel, în primul șir am adăugat caracterul I pe poziţia 4, am
șters caracterul I de pe prima poziţie, iar caracterul O de pe poziţia 2 a fost modificat în D. În
al doilea șir, am șters caracterul I de pe prima poziţie, am modificat caracterul O de pe a doua
poziţie în D și am adăugat caracterul I pe poziţia 4.
Dacă ordinea transformărilor nu contează, atunci vom prefera să calculăm numărul minim al
transformărilor, pornind de la A, și numărând adăugările, modificările, și ștergerile
caracterelor de la stânga către dreapta (în șirul iniţial).
Pentru rezolvare, vom presupune că fiecare cuvânt (A, B) începe cu un caracter vid, pe care-l
notăm cu V. În aceste condiţii, avem de efectuat transformarea:
VA1 A2... Am → VB1 B2... Bn
În acest fel, A va avea m+1 caractere, iar B va avea n+1 caractere.
...B...TTTAk21→→→→DANIAOANIAIOANIAIOANAMSA→→→
Pentru calculul distanţei vom utiliza matricea Cost cu m+1 linii și n+1 coloane. Liniile sunt
între 0 și m+1, iar coloanele între 0 și n+1. Elementul Cost[i,j] va reţine numărul mimim al
transformărilor primelor i caractere ale cuvântului A în primele j caractere ale cuvântului B.
Mai precis, Cost[i,j] înseamnă costul obţinerii cuvântului intermediar:
B1 B2 ... Bj Ai+1 Ai+2 ... Am
Avem:
1) Cost[0,j]=j, j=0, 1, 2, ..., n. Semnificaţie: costul transformării caracterului vid, care
precede pe A, în primele j caractere ale cuvântului B, este j (se fac j adăugări).
2) Cost[i,0]=i, i=0, 1, 2, ..., m Semnificaţie: costul transformării primelor i caractere ale lui A
în caracterul vid care îl precede pe B, este i (se fac i ștergeri).
3) 0<i≤m, 0<j≤n +
{}
−−−−+=−−=altfel,j)1,cost(i1),jcost(i,1),j1,cost(imin1BA1],j1,Cost[ij]Cost[i,ji
Semnificaţie: la fiecare pas, se compară caracterul aflat în A pe poziţia i (A[i]), cu cel aflat în
B pe poziţia j (B[j]). Dacă se cunosc costurile optime (numărul minim de operaţii): C[i-1,j-
1], C[i,j-1], C[i-1,j], atunci:
A) Dacă caracterul aflat pe poziţia i în A este egal cu caracterul aflat pe poziţia j în B
(Ai=Bj), se sare acel caracter. În acest caz,
Cost[i,j]=Cost[i-1,j-1].
B1B2...Bj-1AiAi+1...Am → B1B2...Bj-1BjAi+1...Am
B) Ai≠Bj. Atunci se efectuează una din operaţiile următoare, mai precis, cea care are costul
cel mai mic:
B1) Adăugarea unui caracter (Bj). Atunci costul total este: 1+Cost[i,j-1].
B1B2...Bj-1Ai+1...Am → B1B2...Bj-1BjAi+1...Am
B2) Ștergerea unui caracter, cel aflat pe poziţia Ai. Atunci costul total este 1+Cost[i-1,j].
B1B2...Bj-1BjAiAi+1...Am → B1B2...Bj-1BjAi+1...Am
B3) Modificarea unui caracter, Ai va fi egal Bj. Atunci costul total este 1+Cost[i-1,j-1].
B1B2...Bj-1AiAi+1...Am → B1B2...Bj-1BjAi+1...Am
Cazul ”IOANA→DANIA”. Costul transformării caracterului vid în caracterul vid este 0,
costul transformării caracterului vid în ”D” este 1, costul transformării caracterului vid în
”DA” este 2, ..., costul transformării caracterului vid în ”DANIA” este 5. Apoi, costul
transformării caracterului vid în caracterul vid este 0, costul transformării caracterului ”I” în
caracterul vid este 1, costul transformării caracterelor ”IO” în caracterul vid este 2, ..., costul
transformării caracterelor ”IOANA” în caracterul vid este 5.
VDANIA
V012345
I1
O2
A3
N4
A5
În continuare, completăm matricea pe linii:
C[1,1]. A[1]=I≠D=B[1].
1+min{cost[i-1,j-1],cost[i-1,j],cost[i,j-1]}=1+min{cost[0,0],
cost[0,1],cost[1,0]=1+min(0,1,1)=1.
Semnificaţia: modificarea minimă pentru a transforma ”I” în ”D” are costul 1. Se face o
modificare pentru că (i-1,i-1) trece în (i,j).
VDANIA
V012345
I11
O2
A3
N4
A5
...
În final, matricea este:
VDANIA
V012345
I112334
O222344
A332344
N443234
A554333
Numărul minim de transformări este: cost[m,n]=cost[5,5]=3.
După calculul elementelor matricei, se depistează operaţiile efectuate și acestea se afișează în
ordine inversă.
Depistarea unei operaţii
Pentru i=5 și j=5,
min{cost[4,4],cost[4,5],cost[5,4]}= min{3,4,3}.
Alegem 3 (prima valoare minimă din șir). Pentru că avem cost[5,5]=min,
înseamnă că la ultima operaţie s-a efectuat un salt (a fost găsită egalitate).
Acum i=4 și j=4. Apoi:
min{cost[3,3],cost[3,4],cost[4,3]}=min{3,4,2]=2.
cost[4,4]≠min
Pentru că am efectuat o operaţie de tipul (i,j-1)→(i,j) înseamnă că s-a
adăugat pe poziţia 4 a șirului A caracterul de pe poziţia 4 a șirului B (I). Aceasta
este ultima modificare făcută de algoritm.
Avem i=4, j=3. Depistăm apoi, penultima modificare, ș.a.m.d., până când i=0 și
j=0. Pentru a afișa modificările în ordine inversă vom utiliza o stivă (Sol). De
asemenea, se poate utiliza recursivitatea.
#include <iostream>
#include <cstring>
char A[100],B[100],
Sol[100][300],op;
int m,n,i,j,min,k,
cost[100][100];
void Next(int& i, int& j,
char& op)
{ int l=0,c=0;
min=1000;
if (i>0 && j>0 &&
min>=cost[i-1][j-1])
{ min=cost[i-1][j-1];
l=i-1; c=j-1;
op='m';}
if (i>0 && cost[i-1][j]<min)
{ min=cost[i-1][j];
l=i-1; c=j;
op='s';}
if (j>0 && cost[i][j-1]<min)
{ min=cost[i][j-1];
l=i; c=j-1; op='a';}
if (cost[i][j]==min) op='v';
i=l; j=c;}
int main()
{ int t;
cout<<"A="; cin>>A+1;
cout<<"B="; cin>>B+1;
m=strlen(A+1);
n=strlen(B+1);
cout<<m<<" "<<n<<endl;
for (i=0;i<=m;i++)
cost[i][0]=i;
for(j=0;j<=n;j++)
cost[0][j]=j;
for (i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(A[i]==B[j])
cost[i][j]=cost[i-1][j-1];
else
{ min=cost[i-1][j-1];
if (min>cost[i-1][j])
min=cost[i-1][j];
if (min>cost[i][j-1])
min=cost[i][j-1];
cost[i][j]=1+min;}
cout<<"Distanta "
<<cost[m][n]<<endl;
i=m;
j=n;
while(i+j)
{ Next(i,j,op);
if (op!='v')
{ int x=0;
k++;
Sol[k][x++]=op;
Sol[k][x++]=' ';
for (t=1;t<=j;t++)
Sol[k][x++]=B[t];
for (t=i+1;t<=m;t++)
Sol[k][x++]=A[t];}}
for(k=cost[m][n];k>=1;k--)
cout<<Sol[k]<<endl;
cout<<B+1;}
După cum se poate observa, algoritmul are complexitatea O(n2).
6.7. Înmulţirea optimă a unui șir de matrice
Presupunem că avem de înmulţit două matrice: An,p cu Bp,m. În mod evident, rezultatul va
fi o matrice Cn,m. Se pune problema de a afla câte înmulţiri au fost făcute pentru a obţine
matricea C. Prin înmulţirea liniei 1 cu coloana 1 se fac p înmulţiri, întrucât au p elemente.
Dar linia 1 se înmulţește cu toate cele m coloane, deci se fac m*p înmulţiri. În mod analog se
procedează cu toate cele n linii ale matricei A, deci se fac n*m*p înmulţiri. Reţinem acest
rezultat.
Să considerăm produsul de matrice A1×A2×...×An (A1(d1,d2), A2(d2,d3),..., An(dn,dn+1)).
Se cunoaște că legea de compoziţie produs de matrice nu este comutativă, în schimb este
asociativă. De exemplu, dacă avem de înmulţit trei matrice A, B, C produsul se poate face în
două moduri: (AxB)xC sau Ax(BxC).
Este interesant de observat că nu este indiferent modul de înmulţire a celor n matrice. Să
considerăm că avem de înmulţit patru matrice A1(10,1), A2(1,10), A3(10,1), A4(1,10).
Pentru înmulţirea lui A1 cu A2 se fac 100 de înmulţiri și se obţine o matrice cu 10 linii și 10
coloane. Prin înmulţirea acesteia cu A3 se fac 100 de înmulţiri și se obţine o matrice cu 10
linii și o coloană. Dacă această matrice se înmulţește cu A4, se fac 100 de înmulţiri. În
concluzie, dacă acest produs se efectuează în ordine naturală, au loc 300 de înmulţiri.
Să efectuăm același produs în ordinea care rezultă din expresia
A1×((A2×A3)×A4).
Efectuând produsul A2 cu A3 se efectuează 10 înmulţiri și se obţine o matrice cu o linie și o
coloană. Această matrice se înmulţește cu A4, se fac 10 înmulţiri și se obţine o matrice cu 1
linie și 10 coloane. Dacă o înmulţim pe aceasta cu prima, efectuăm 100 de înmulţiri,
obţinând rezultatul final cu numai 120 de înmulţiri.
În concluzie, apare o problemă foarte interesantă și anume de a afla modul în care trebuie să
se înmulţească cele n matrice, astfel încât numărul de înmulţiri să fie minim.
Să vedem, mai întâi, în câte moduri se poate calcula un produs de n astfel de matrice. Pentru
n=4, putem avea:
((A1×A2)×(A3×A4)); (((A1×A2)×A)3×A4); ((A1×(A2×A3))×A4);
(A1×(A2×(A3×A4))); (A1×((A2×A3)×A4)).
Astfel, pentru n=4 avem 5 posibilităţi de calcul al acestui produs. Să observăm că pentru
produse de n matrice, sunt necesare n-1 perechi de paranteze.
Exerciţiu. Puteţi demonstra prin inducţie acest rezultat?
Ţinând cont de aceasta, se poate formula problema următoare: în câte feluri se pot combina n
perechi de paranteze (desigur, pentru problema dată avem n-1 perechi)? Cei pasionaţi de
informatică pot studia numărarea arborilor binari, autoinstruire (vezi Capitolul 9, problema
propusă 23). Acum ne limităm să spunem că acest număr este:
nnCn211+
și că, în general, un astfel de număr este foarte mare.
Exerciţiu. Calculaţi acest număr pentru n=10, 11, ..., 20.
Prin urmare, un algoritm în care calculăm în toate modurile posibile acest produs este
ineficient.
Din fericire, pentru această problemă există o rezolvare polinomială, prin utilizarea
programării dinamice. Să presupunem că produsul Ai×Ai+1×...Aj s-a calculat optim. În final,
s-au înmulţit două matrice (Ai×...×Ak)×(Ak+1×...×Aj). Atunci, produsele Ai×...Ak și
Ak+1×...×Aj au fost calculate optim. De ce? Demonstraţi prin reducere la absurd.
Pentru rezolvare, vom aplica principiul al 3-lea al programării dinamice.
În vederea rezolvării problemei, reţinem o matrice A cu n linii și n coloane. Elementul A(i,j),
i<j, reprezintă numărul minim de înmulţiri pentru efectuarea produsului Ai×Ai+1×...×Aj. De
asemenea, numărul liniilor și al coloanelor celor n matrice sunt reţinute într-un vector DIM
cu n+1 componente. Pentru exemplul nostru DIM reţine următoarele valori: 10, 1, 10, 1, 10.
Pentru rezolvare se ţine cont de următoarele relaţii existente între componentele matricei A:
()()()()()()
{}.1jDIM1kDIMiDIMj1,kAki,Aminji,A3)2);DIM(i1)DIM(iDIM(i)1)iA(i,2)0;i)A(i,1)jki+×+
×+++=+×+×=+=<≤
Justificarea acestor relaţii este următoarea:
1) o matrice nu se înmulţește cu ea însăși, deci se efectuează 0 înmulţiri;
2) liniile și coloanele matricei Ai se găsesc în vectorul DIM pe poziţiile i și i+1, iar ale
matricei Ai+1, pe poziţiile i+1 și i+2;
3)
înmulţind matricele Ai×Ai+1×Ak, se obţine o matrice cu un număr de linii egal cu acela al
matricei Ai (DIM(i)) și cu un număr de coloane egal cu acela al matricei Ak (DIM(k+1));
înmulţind matricele Ak+1×...×Aj, se obţine o matrice cu un număr de linii egal cu acela al
matricei Ak+1 (DIM(k+1)) și cu un număr de coloane egal cu acela al matricei Aj
(DIM(j+1));
prin înmulţirea celor două matrice se obţine matricea rezultat al înmulţirii Ai×...×Aj, iar
pentru această înmulţire de matrice se efectuează DIM(i) ×DIM(k+1)×DIM(j+1) înmulţiri.
Observaţii
Relaţia sintetizează faptul că pentru a obţine numărul de înmulţiri optim pentru produsul
Ai×...×Aj se înmulţesc două matrice, una obţinută ca produs optim între Ai×...×Ak și cealaltă
obţinută ca produs optim între Ak+1×...×Aj, în ipoteza în care cunoaștem numărul de
înmulţiri necesar efectuării acestor două produse, oricare ar fi k cuprins între limitele date.
Această observaţie este o consecinţă directă a programării dinamice și anume că produsul
efectuat optim între matricele prezentate se reduce în ultimă instanţă la a efectua un produs
între două matrice cu condiţia ca acestea să fie calculate optim (produsul lor să aibă un
număr minim de înmulţiri).
Să observăm faptul că orice secvenţă pentru calculul costului optim este de forma
Ai×Ai+1×...×Aj. Astfel, întotdeauna j≥i. Pentru a reţine costul optim, A(i,j) vom utiliza o
matrice. Cum j≥i înseamnă că din această matrice se va utiliza numai partea situată deasupra
diagonalei principale.
Din relaţia 1, rezultă că mai întâi trebuie completate cu 0, elementele aflate pe diagonala
principală. Dacă matricea este declarată ca variabilă globală, elementele ei sunt oricum
iniţializate cu 0.
Din relaţia 2, rezultă că, în continuare, trebuie completate elementele de coordonate
(i,i+1). Toate acestea sunt situate în partea aflată deasupra diagonalei principale, pe o
paralelă la diagonala principală ("cea mai apropiată").
Din relaţia 3, rezultă că pentru a afla costul optim pentru produsul Ai×Ai+1×...×Aj, reţinut
de A(i,j), se fac j-i comparări, prin care produsul se descompune în alte două produse, al
căror cost optim este deja cunoscut și se alege descompunerea care asigură costul minim.
Elementele necesare din matricea costurilor optime se observă în tabelul de mai jos:
k Produsele Elemente necesare
i (Ai)×Ai+1×...×Aj A(i,i) , A(i+1,j)
i+1 (Ai×Ai+1)×Ai+2×...×Aj A(i,i+1), A(i+2,j)
... ... ...
j-1 (Ai×Ai+1×...× Aj-1)×Aj A(i,j-1), A(j,j)
Din tabel se observă că pentru calculul lui A(i,j) sunt necesare:
a) A(i,i), A(i,i+1), ..., A(i,j-1) - adică toate elementele din matricea A(i,j), aflate pe linia i,
până la coloana j.
b) A(i+1,j), A(i+2,j), ..., A(j,j) - adică toate elementele din matricea A(i,j), aflate pe coloana
j, până la linia i. De exemplu, dacă n=5, alăturat puteţi observa elementele implicate în
calculul costului optim a(2,5). Întrebarea este: pentru ce au fost prezentate toate aceste
amănunte? Răspuns: pentru a calcula costul optim, reţinut de A(i,j), este necesar ca
elementele matricei A să fie completate pe diagonala principală, apoi pe cea
mai apropiată paralelă de aceasta, apoi, din nou, pe cea mai apropiată diagonală paralelă cu
ultima completată, până se ajunge să se completeze A(1,n) care va reţine costul optim pentru
problema cerută. În acest fel, pentru orice element care se calculează, elementele necesare au
fost deja determinate. Se pune problema să aflăm cum putem efectua acest calcul utilizând
relaţiile prezentate. Pentru exemplificare vom utiliza exemplul dat la începutul acestui
paragraf. Datorită relaţiei 1, diagonala principală a matricei A (cu 4 linii și 4 coloane) va fi
alcătuită numai din elemente având valoarea 0.
Rămâne să determinăm modul de generare a elementelor de pe paralelele
la diagonala principală, mai precis pe cele aflate deasupra diagonalei
principale. Astfel:
- pentru prima "paralelă": A(1,2), A(2,3), ..., A(n-1,n);
- pentru a doua "paralelă": A(1,3), A(2,4), ..., A(n-2,n);
- pentru a treia "paralelă": A(1,3) A(2,5), …, A(n-3,n);
...
- pentru ultima "paralelă": A(1,n).
Observăm că:
- pentru prima paralelă, liniile sunt între 1 și n-1;
- pentru a doua paralelă, liniile sunt între 1 și n-2;
- pentru a treia paralelă, liniile sunt între 1 și n-3;
...
- pentru ultima paralelă liniile sunt între 1 și 1.
Dacă notăm linia cu i și coloana cu j, atunci secvenţa:
pentru l de la 1 la n-1
pentru i de la 1 la n-l
j←l+i
generează pentru l=1 linii de la 1 la n-1, pentru l=2, linii de la 1 la n-2, ..., pentru l=n-1, linia
1. Să observăm faptul că pentru fiecare l și i, coloana este j. În acest fel, pentru o anumită
valoare a lui l, se obţine o paralelă la diagonala principală. De exemplu, dacă l=1, i=1, j=2, se
obţine A(1,2), dacă l=1, i=2, j=3, se obţine A(2,3), ..., iar dacă l=1, i=n-1, j=n, se obţine A(n-
1,n), adică prima paralelă la diagonala principală. Revenim la exemplul dat la începutul
acestui paragraf. Iniţial se pot calcula numai elementele A(i,i+1), adică A(1,2), A(2,3),
A(3,4) - elemente situate pe o paralelă la diagonala principală a matricei A. În concluzie,
avem A(1,2)=100, A(2,3)=10, A(3,4)= 100. Matricea A va arăta ca alăturat:
În continuare calculăm: ()()()()()(){}{}()()()()()(){}{}()()()()()(){}
{};1201011002010,101010010010,110200min5DIM1kDIM1DIM1,4kAk1,Amin1,4A20;101
101010,1011000min5DIM1kDIM2DIM1,4kAk2,Amin2,4A20;1101001001,110100min4DI
M1kDIM1DIM1,3kAk1,Amin1,3A4k14k23k1=××++××++××++==×+×+++==××++××+
+==×+×+++==××++××++==×+×+++=<≤<≤<≤
În concluzie, pentru exemplul nostru, se fac minimum 120 de înmulţiri, rezultat luat din
matricea A și anume A(1,4):
.0100020100120201000=xxxxxxA.010001001000=xxxxxxxxxA
Mai avem de lămurit o problemă. Chiar dacă cunoaștem costul optim (numărul minim de
înmulţiri), cum determinăm în ce mod se înmulţesc matricele pentru a obţine acest cost? Să
observăm că elementele din matrice, situate sub diagonala principală, au fost neutilizate. De
asemenea, pentru calculul optim al unui produs Ai×Ai+1×Ai+2×...×Aj se determină un
anumit k. Așa cum am arătat, k exprimă ordinea de înmulţire a matricelor. De exemplu, dacă
k=i+1, avem produsul (Ai×Ai+1)×Ai+2×...×Aj, înţelegând prin aceasta că produsul se obţine
ca produs între matricele Ai×Ai+1 și Ai+2×...×Aj, produse pe care știm să le obţinem în mod
optim. Dar, dacă în urma acestui calcul am determinat k, astfel încât produsul obţinut să fie
optim, această valoare poate fi reţinută de A(j,i). Pentru exemplul nostru, matricea A este
prezentată mai jos:
Grafic, valorile se pot prezenta într-un arbore. Întrucât arborii vor fi descriși într-un capitol
separat, vă rog să reveniţi după parcurgerea acelui capitol la această problemă.
Priviţi arborele următor:
Pentru produsul matricelor de la 1 la 4, se obţine k=1 (A(4,1)=1). Aceasta înseamnă că
produsul se va efectua astfel: A1×(A2×A3×A4). Pentru produsul A2×A3×A4 avem k=3.
Aceasta înseamnă că produsul va fi calculat astfel: (A2×A3)×A4. Prin urmare, produsul celor
4 matrice se va calcula în felul următor:
(A1×((A2×A3)×A4)).
Dacă listăm nodurile neterminale ale acestui arbore, arborele fiind parcurs în postordine,
obţinem modul în care se așează parantezele pentru calculul produsului de matrice. Pentru
exemplul nostru, subprogramul parc afișează (2,3), (2,4), (1,4). Aceasta ne spune cum să
aranjăm parantezele.
.0331100021201001120201000=A
(1,4)
(1,1)
(2,4)
(2,3)
(4,4)
(2,2)
(3,3)
Figura. 6.1. Reprezentarea valorilor sub forma unui arbore
#include <iostream.h>
long i,n,dim[10],a[10][10];
void parc (int l, int c)
{ int k=a[c][l];
if (k!=l) parc(l,k);
if (k+1!=c) parc(k+1,c);
cout<<l<<" "<<c<<endl;}
void costopt ()
{ long k,i,j,l,m;
for (l=1;l<=n-1;l++)
for (i=1;i<=n-l;i++)
{ j=i+l;
a[i][j]=100000;
for (k=i;k<=j-1;k++)
{ m=a[i][k]+a[k+1][j]+
dim[i]*dim[k+1]*
dim[j+1];
if (a[i][j]>m)
{ a[i][j]=m;
a[j][i]=k;}}}
cout<<"cost optim "
<<a[1][n]<<endl;}
int main()
{ cout<<"n="; cin>>n;
for (i=1;i<=n+1;i++)
{ cout<<"d=";
cin>>dim[i];}
costopt();
parc(1,n);}
Complexitatea algoritmului este O(n3). Observaţi că există trei cicluri for imbricate!
6.8. Probleme cu ordinea lexicografică a permutărilor
Problema 1. Se citește n, număr natural, și o permutare a numerelor 1,2,...,n. Se cere să se
afișeze numărul de ordine al permutării, dacă se consideră permutările în ordinea
lexicografică. Alăturat, observaţi permutările mulţimii {1,2,3}, listate în ordinea
lexicografică.
Prima idee este să generăm prin Backtracking, în ordine lexicografică, toate permutările,
până la întâlnirea permutării date și în paralel să le numărăm. Când am întâlnit-o, afișăm
numărul de ordine. Dar, avem n! permutări. Cum n!=1×2×...n>2×2×2...2=2n-1, observăm că
algoritmul este exponenţial. Evident, renunţăm la o astfel de soluţie.
Rezolvare. Să observăm primul element afișat al fiecărei permutări. Astfel, există două
permutări care afișează 1 ca prim element, două permutări care afișează 2, ca prim element și
2 permutări care afișează 3 ca prim element. Dacă analizăm și șirul permutărilor observăm
că, în general: elementul 1 este afișat de (n-1)! ori, elementul 2 este afișat de (n-1)! ori, ...,
elementul n este afișat de (n-1)! ori.
De fapt, !)!1(...)!1()!1(nnnnorinde=−++−+−.
Această simplă observaţie ne permite să scriem o relaţie de recurenţă, unde NR(P(n))
înseamnă numărul de ordine al permutării iniţiale, iar NR(P(n-1)) înseamnă numărul de
ordine al permutării alcătuite din ultimele n-1 elemente ale permutării iniţiale. Dacă
permutarea este a1 a2... an, atunci:
=>+=1111nn1)),-NR(P(n1)-(a1)!-(nNR(P(n))
Să observăm faptul că permutarea formată cu ultimele n-1 elemente ale permutării iniţiale
este formată din elementele de la 1 la n, din care lipsește exact un element. Din ea, se poate
obţine permutarea cu același număr de ordine (ordinea lexicografică) a mulţimii {1,2,...,n-1},
dacă din orice element mai mare decât cifra eliminată se scade 1 (această operaţie nu
afectează ordinea lexicografică!).
Exemplu: pentru n=5, P=4 5 2 3 1.
P=4!3+NR({5,2,3,1})=72+NR({4,2,3,1})=72+3!*3+NR({2,3,1})=
90+2!1+NR({3,1})=92+NR({2,1})=92+1!1+P(1)=93+1=94.
#include <iostream.h>
int P[10],n,i,k,Nr,Prod;
void Numar()
{ int nsalv=n;
while (n>1)
{ Prod/=n;
Nr+=(P[k]-1)*Prod;
for (i=k+1;i<=nsalv;i++)
if (P[i]>P[k]) P[i]--;
k++;n--;}
Nr++;}
int main()
{ cout<<"n=";cin>>n;
for(i=1;i<=n;i++) cin>>P[i];
Prod=1;
for(i=2;i<=n;i++) Prod*=i;
k=1;
Numar();
cout<<Nr;}
Algoritmul are complexitatea O(n2). Justificaţi!
Problema 2. Se citește n>0, număr natural, și un număr natural 1≤Nr≤n! Care este
permutarea care, în ordine lexicografică, are numărul de ordine Nr?
Exemplu: pentru n=5 și Nr=94, se va afișa 4 5 2 3 1.
Rezolvare. Știm că, în șirul tuturor permutărilor, fiecare element al permutării apare pe
prima poziţie de exact (n-1)! ori. În cazul nostru, (n-1)!=4!=24. Cum primele (în ordine
lexicografică) (n-1)! permutări au elementul 1 pe prima poziţie, următoarele (n-1)! permutări
au elementul 2 pe prima poziţie, înseamnă că:
Primul_element=1+[(Nr-1)/(n-1)!],
unde prin [x] am notat parte întreagă din x.
Observaţie foarte importantă. Dacă primul element al permutării poate fi depistat ca mai sus,
cu următoarele trebuie efectuate operaţii în plus, pentru că se selectează elementele unei
permutări ale cărei elemente nu sunt numere consecutive. De exemplu, dacă pentru n=5 se
selectează ca prim element numărul 3, atunci următorul element trebuie selectat din
mulţimea {1,2,4,5}. În acest caz, algoritmul va furniza indicele elementului în vector și nu
elementul propriu-zis. Astfel, dacă elementele ar ocupa în vectorul P poziţii consecutive,
acesta ar trebui să fie P(1,2,4,5) și dacă algoritmul returnează 3, ar trebui selectat 4.
Datorită celor arătate, vom prefera să lucrăm cu 2 vectori, ca alăturat. Vectorul P reţine
numerele 1, 2, ..., n, iar O[i] reţine 1 dacă elementul corespunzător din P a fost selectat, și 0
în caz contrar. Astfel, dacă algoritmul returnează valoarea k, va trebui afișat al k-lea element
neselectat, după care O[k] va reţine 1. Exemplul care urmează vă va lămuri.
Avem n=5 și Nr=94.
(94-1)/24+1=3+1=4. Numărul rămas este 94-3*24=94-72=22. Pentru că elementul selectat
este 4 (al 4-lea în ordine), marcăm în vectorul O acest fapt. În acest mod, problema s-a redus
la o alta, mai simplă: care este permutarea cu 4 elemente, 1, 2, 3, 5 care, în ordine
lexicografică, are numărul de ordine 22?
Avem: (n-1)!=3!=6. La fel: (22-1)/6+1=3+1=4. Al 4-lea element neselectat este 5. Îl selectăm
pentru a-l afișa și-l marcăm în O. Până în acest moment am afișat 4 și 5. Numărul rămas este
22-3*6=22-18=4.
Problema s-a redus la o alta, mai simplă: care este permutarea cu 3 elemente, 1, 2, 3 care, în
ordine lexicografică, are numărul de ordine 4?
(n-1)!=2!=2.
(4-1)/2+1=2.
Numărul rămas este 4-1*2=2.
Selectăm al doilea element neselectat, adică 2 și afișăm elementul. Astfel, am afișat 4, 5, 2.
Apoi:
(n-1)!=1!=1.
(2-1)/1+1=2.
Numărul rămas este 2-1*1=1. Afișăm 3, pentru că este al doilea element neselectat, după
care marcăm în O elementul 3. Am afișat astfel 4, 5, 2 și 3.
Afișăm ultimul element neafișat, adică 1. Am obţinut 4, 5, 2, 3 și 1.
1234500010PO1234500011PO1234501011PO1234501111PO1234500000PO
#include <iostream.h>
int n,Nr,i,k,fact,ic,
nsalv,P[10],O[10];
int main()
{ cout<<"n="; cin>>n;
cout<<"Nr="; cin>>Nr;
fact=1;
for(i=1;i<=n;i++)
{ P[i]=i;
fact*=i;}
nsalv=n;
while (Nr!=1)
{ fact/=n;
n--;
k=(Nr-1)/fact+1;
Nr-=fact*(k-1);
ic=0;i=1;
while(ic<k)
{ if (O[i]==0) ic++;
i++;}
O[i-1]=1;
cout<<P[i-1];}
for(i=1;i<=nsalv;i++)
if(O[i]==0) cout<<P[i];}
Algoritmul are complexitatea O(n2). Justificaţi!
6.9. Numărul partiţiilor unei mulţimi cu n elemente
Enunţ. Se citește n, număr natural. Se cere ca programul să afișeze numărul partiţiilor unei
mulţimi cu n elemente.
Rezolvare. Prima idee care ne vine în minte este să generăm toate partiţiile unei mulţimi
(vedeţi generarea lor prin Backtracking) și să le numărăm. Dar numărul partiţiilor este așa de
mare astfel încât o asemenea idee se dovedește dezastruasă. Pornind de la partiţiile unei
mulţimi cu n elemente, observaţi, pentru n=3, cum se pot obţine toate partiţiile unei mulţimi
cu n+1 elemente.
{1,2,3}, {4}
{1,2,3}
{1,2,3,4}
{1,4}, {2,3}
{1} {2,3} {1}, {2,3,4}
{1}, {2,3}, {4}
{2,4}, {1,3}
{2} {1,3} {2}, {1,3,4}
{2}, {1,3}, {4}
{3,4}, {1,2}
{3} {1,2} {3}, {1,2,4}
{3}, {1,2}, {4}
{1,4}, {2}, {3}
{1} {2} {3} {1}, {2,4}, {3}
{1}, {2}, {3,4}
{1}, {2}, {3}, {4}
Ideea de bază este ca, din fiecare partiţie a mulţimii de n elemente, să se genereze toate
partiţiile care provin din ea, ale mulţimii de n+1 elemente. Aceasta se obţine dacă se adaugă
pe rând, la fiecare mulţime a partiţiei, elementul n+1 și, la sfârșit, acesta va forma singur o
mulţime a partiţiei. Vedeţi mai sus!
Vom nota prin S(n,k) numărul partiţiilor unei mulţimi cu n elemente, partiţii în care numărul
mulţimilor este k. De exemplu, pentru n=3, avem: S(3,1)=1, S(3,2)=3 și S(3,3)=1. În aceste
condiţii, numărul partiţiilor unei mulţimi cu 3 elemente este:
S(3,1)+S(3,2)+S(3,3)=1+3+1=5. De aici rezultă că, pentru a calcula numărul partiţiilor unei
mulţimi cu n+1 elemente, trebuie să calculăm suma:
S(n+1,1)+S(n+1,2)+...+S(n+1,n+1).
Dacă am găsi o modalitate de calcul pentru S(n,k), atunci problema ar fi rezolvată.
a) Să observăm că, pentru orice n, S(n,1)=1, adică avem o singură partiţie în care toate
mulţimile au un singur element: {1}, {2}, {3}, …, {n}. Tot așa, S(n,n)=1, pentru că avem o
singură partiţie în care mulţimile au n elemente: {1,2,...,n}.
b) Urmărim să găsim o relaţie de recurenţă pentru S(n+1,k), adică să găsim numărul
partiţiilor unei mulţimi cu n+1 elemente, partiţii în care toate mulţimile au k elemente, în
condiţiile în care cunoaștem S(n,1), S(n,2) ...,S(n,n).
b1) Dacă cunoaștem numărul partiţiilor unei mulţimi cu n elemente, în care fiecare partiţie
are k submulţimi, S(n,k), atunci putem forma partiţii alcătuite din exact k mulţimi ale
mulţimii cu n+1 elemente. Pentru fiecare partiţie numărată de S(n,k), adăugăm elementul
n+1 în prima mulţime a partiţiei, apoi în a doua mulţime, ..., la sfârșit în a k-a mulţime a
partiţiei. În acest fel, din fiecare partiţie se obţin alte k partiţii. În concluzie, vom obţine în
acest mod k*S(n,k) partiţii. În exemplul dat, observaţi cum din cele 3 (S(3,2)) partiţii cu 2
submulţimi ale mulţimii cu 3 elemente, am obţinut 2*S(3,2)=6 partiţii cu 3 submulţimi ale
unei mulţimi cu 4 elemente.
{1,4}, {2,3}
{1} {2,3} {1}, {2,3,4}
{2,4}, {1,3}
{2} {1,3} {2}, {1,3,4}
{3,4}, {1,2}
{3} {1,2} {3}, {1,2,4}
b2) Dacă cunoaștem numărul partiţiilor unei mulţimi cu n elemente, partiţii care sunt
alcătuite din k-1 mulţimi, atunci din fiecare astfel de mulţime se poate obţine o altă partiţie
cu k mulţimi ale mulţimii cu n+1 elemente, adăugând la fiecare partiţie mulţimea alcătuită
din elementul n+1. În concluzie, în acest mod vom obţine alte S(n,k-1) partiţii cu k
submulţimi ale unei mulţimi cu n+1 elemente. În exemplul dat, avem:
{1,2,3} {1,2,3} {4}
Cum alte posibilităţi de obţinere a partiţiilor unei mulţimi cu k clase ale unei mulţimi cu n+1
elemente nu există și cum, astfel obţinute, partiţiile nu se repetă, relaţia este:
S(n+1,k)=S(n-1,k)+k*S(n,k).
Pentru exemplul dat, S(4,2)=S(3,3)+3*S(3,2)=1+2*3=7.
Pentru a scrie programul, completăm, mai întâi prima coloană a matricei cu 1 (pentru că
avem S(n,1)=1). Prima linie va avea numai un 1 în prima coloană, pentru că, evident,
S(1,k)=0, pentru k>1. În continuare, completăm pe linii elementele matricei S. În final,
facem suma pe linia n.
#include <iostream.h>
long S[20][20],n,k,i,j,s;
int main()
{ cout<<"n="; cin>>n;
for (i=1;i<=n;i++) S[i][1]=1;
S[i][i]=1;
for(i=2;i<=n;i++)
for (j=2;j<=i;j++)
S[i][j]=S[i-1][j-1]+j*S[i-1][j];
for (i=1;i<=n;i++)
s+=S[n][i];
cout<<s;}
Complexitatea algoritmului este O(n2).
📘 5. Teoria grafurilor
10. Grafuri
10.1. Grafuri neorientate
10.1.1. Noţiuni teoretice
Definiţie. Se numeşte graf neorientat o pereche ordonată de mulţimi ( X , U ), X fiind o mulţime finită
şi nevidă de elemente, numite vârfuri, iar U o mulţime de perechi neordonate din X, numite muchii.
Notăm G = ( X , U ) un graf neorientat
X se numeşte mulţimea vârfurilor
U se numeşte mulţimea muchiilor
Fie u U care trece prin x, y. Atunci u = [ x , y ] sau u = ( x , y )
Definiţie. Pentru o muchie u = [ x , y ] :
– vârfurile x şi y sunt adiacente şi se numesc extremităţile muchiei u;
– muchia u şi vârful x sunt incidente în graf;
– muchia u şi vârful y sunt incidente în graf;
Observaţie. [ x , y ] = [ y , x ] deoarece nu există o orientare a muchiei
Exemplu. Fie G = ( X , U ) astfel încât :
X = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 }
U = { [ 1 , 5 ] , [ 3 , 7 ] , [ 4 , 6 ] , [ 9 , 8 ] , [ 10 , 2 ] , [ 1 , 2 ] , [ 9 , 4 ] , [ 1 , 10] , [ 6 , 8 ] }
1 10 3 7
4 6 11
5 2
9 8
Definiţie. Gradul unui varf x, notat d ( x ), reprezintă numărul muchiilor care trec prin vârful x
( incidente cu vârful x ).
Definiţie. Un varf care are gradul 0, se numeşte vârf izolat.
Un vârf care are gradul 1, se numeşte vârf terminal.
Exemplu. d ( 1 ) = 3; d ( 2 ) = 2; d ( 4 ) = 2; d ( 6 ) = 2; d ( 8 ) = 2; d ( 9 ) = 2; d (10 ) = 2;
d ( 11 ) = 0 11 = vârf izolat
d ( 3 ) = 1; d ( 5 ) = 1; d ( 7 ) = 1 3 , 5 , 7 = vârfuri terminale
Definiţie. Fie graful G = ( X , U ). Un graf parţial al lui G, este un graf G 1 = ( X , V ) astfel încât V
U, 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.
Exemplu. G1 = ( X , V ) V = { [ 1 , 5 ] , [ 2 , 10 ] , [ 6 , 4 ] }
1 2
5 10 4 6
8 3 7 11 9
1 2
3 7
10
2
5
4 3
3
1
5
2 6
4 7
Definiţie. Se numeşte graf bipartit complet, un graf bipartit cu proprietatea că pentru orice vârf
x din A şi orice vârf y din B, există muchia [ x , y ].
1 2
3
5
4
Definiţie. Se numeşte lanţ în graful G, o succesiune de vârfuri L = ( z1 , z2 , … , zk ), unde z1 , z2 ,
… , zk X, astfel încât oricare două vârfuri consecutive sunt adiacente, adică [ z 1 , z2 ] , [ z2 , z3 ] , … ,
[ zk–1 , zk ] U.
Vârfurile z1 şi zk se numesc extremităţile lanţului.
Numărul de muchii care intră în componenţa sa reprezintă lungimea lanţului. Dacă vârfurile z1 , z2 , …
, zk sunt distincte două câte două, lanţul se numeşte elementar. În caz contrar, lanţul se numeşte
neelementar.
Exemplu:
a Mn x n
Observaţie. Pentru orice graf neorientat, matricea de adiacenţă a este simetrică faţă de diagonala
principală.
2 3
1 4
2. Reprezentare prin liste de adiacenţă
Nodul Lista de
adiacenţă
1 2
2 1,3,4
3 2,4
4 2,3
Definiţie. Un graf G este conex, dacă oricare ar fi două vârfuri ale sale, există un lanţ care le leagă.
Observaţie. Dacă graful nu este conex, un graf poate fi descompus în componente conexe.
Definiţie. Se numeşte componentă conexă a grafului G = ( X , U ), un subgraf G 1 = ( X1 , U1 ) a
lui G, conex, cu proprietatea că nu există nici un lanţ care să lege un vârf din X1 cu un vârf din X – X1.
Exemplu.
Definiţie. Se numeşte ciclu hamiltonian într–un graf, un ciclu elementar care conţine toate
vârfurile grafului.
Se numeşte graf hamiltonian, un graf care conţine un ciclu hamiltonian. Un graf complet
este hamiltonian.
Se numeşte lanţ hamiltonian într–un graf, un lanţ elementar care conţine toate vârfurile grafului.
Teoremă. Dacă într–un graf G = ( X , U ) cu n >= 3 vârfuri, gradul fiecărui vârf x verifică
condiţia d ( x ) >= n/2, atunci graful este hamiltonian.
Definiţie. Se numeşte ciclu eulerian într–un graf, un ciclu care conţine toate muchiile
grafului.
Se numeşte graf eulerian, un graf care conţine un ciclu eulerian.
Teoremă. Un graf fără vârfuri izolate este eulerian, dacă şi numai dacă este conex, şi gradele
tuturor vârfurilor sunt numere pare.
Exemplu. Graf hamiltonian Graf eulerian
4 1
7
1 2 8
6
5
2 3 3 4 5
10.1.2. Itemi cu alegere multiplă
2. Într-un graf neorientat cu 15 muchii, fiecare nod al grafului are gradul diferit de
0. Doar trei dintre noduri au gradul un număr par, restul nodurilor având gradele numere impare. Care
este numărul maxim de noduri pe care poate să le aibă graful?
a) 27 b) 24 c) 32 d) 16
5. Se consideră graful neorientat reprezentat prin matricea de adiacenţă alăturată. Câte dintre vârfurile
grafului au gradul impar?
01110
10001
10010
10101
01010
a) 3 b) 2 c) 5 d) 1
7. Fie graful neorientat cu 9 noduri, numerotate de la 1 la 9 şi muchiile [1,2], [2,3], [3,7], [4,8], [4,5], [4,6],
[5,9], [6,9], [7,8], [6,7], [1,7]. Numărul minim de muchii carepoate fi adăugat astfel încât graful să devină
eulerian este:
a) 4 b) 5 c) 2 d) 3
8. Se consideră graful neorientat reprezentat prin matricea de adiacenţă alăturată. Care este lista de
adiacenţă corespunzătoare grafului?
01110
10001
10010
10101
01010
a) 1: 2, 3 b) 1: 2, 3, 5 c) 1: 3, 4 d) 1: 2, 3, 4
2: 1, 4 2: 1, 5 2: 1, 3, 5 2: 1, 5
3: 2,5 3: 1,4 3: 2,4,5 3: 1,4
4: 1,3,5 4: 1,3,5 4: 1,3,5 4: 1,3,5
5: 2,4 5: 1,2,3 5: 2,4 5: 2,4
9. Care este numărul minim de muchii ce trebuie eliminat din graful alăturat astfel încât graful parţial
obţinut să nu fie conex?
2
1
3
4
a) 1 b) 2 c) 3 d) 0
10. Fie graful neorientat cu 6 noduri, numerotate de la 1 la 6 şi muchiile [1,2], [1,3], [1,4], [2,3], [2,4],
[3,4], [3,5], [4,5], [4,6], [5,6]. Matricea de adiacenţă corespunzătoare grafului este:
a) 1 0 0 1 1 1 b) 0 1 1 1 0 0 c) 0 1 1 1 1 0 d) 0 1 0 1 0 0
101100 101100 101111 101010
110110 110110 110111 110110
111011 111011 111011 111010
000101 001101 001101 111000
000111 000110 000000 000110
Rezolvare
#include <iostream>
using namespace std;
int b, n, i, j, a[20][20], v[20], k;
int main()
{cin>>n;
for(i=1;i<=n;i++)
for (j=1;j<=n;j++)
cin>>a[i][j];
cin>>k;
for(i=1;i<=k;i++)
cin>>v[i];
b=1;
for(i=1;i<k;i++)
if(a[v[i]][v[i+1]]!=1)
b=0;
if (b)
cout<<"DA";
else
cout<<"NU";
return 0;}
3. Se dă un graf cu n noduri prin matricea de adiacenţă. Să se scrie un program care afişează câte
dintre nodurile grafului au grad par şi câte grad impar.
4. Prin parcurgerea unui graf înţelegem vizitarea nodurilor grafului o singură dată fiecare, după o
anumită regulă.
Parcurgerea în lăţime (BF- breadth first)
Începem parcurgerea grafului în lăţime dintr-un nod i, pe care îl considerăm vizitat.
Vizităm apoi rând pe rând toate nodurile adiacente cu nodul i, încă nevizitate.
Pentru fiecare nod vizitat, vom vizita în continuare toate nodurile adiacente cu el, încă
nevizitate şi aşa mai departe, până când nu mai găsim noduri nevizitate adiacente cu
nodurile vizitate deja.
Parcurgerea nodurilor în lăţime nu dă o soluţie unică, soluţia depinde de ordinea parcurgerii nodurilor
adiacente.
La implementare pentru memorarea nodurilor vizitate vom utiliza o structură de tip coadă, pe care o
vom memora într-un vector. Se va mai folosi un vector viz care reţine informaţii referitoare la nodurile
care au fost vizitate astfel:
1, daca nodul i a fost vizitat
viz [ i ] =
0 , daca nodul i nu a fost vizitat
5. Se dă un graf neorientat cu n noduri memorat prin lista de adiacenţă. Să se scrie un program care
construieşte în memorie matricea de adiacenţă şi verifică dacă graful este sau nu eulerian.
6. Se dă un graf neorientat cu n noduri memorat prin lista de adiacenţă. Să se scrie un program care
construieşte în memorie matricea de adiacenţă şi verifică dacă o succesiune de noduri dată de la
tastatură este sau nu ciclu în graful dat.
9. Să se verifice dacă un graf memorat prin matricea de adiacenţă are „faţă umană”, adică are exact 3
componente conexe: una cu 2 vârfuri, una cu 3 vârfuri şi una cu 4 vârfuri.
10. Se dă un graf care are toate vârfurile de grad impar. Să se scrie un algoritm care determină toate
ciclurile elementare ale grafului.
11. Se dă un graf neorientat cu n noduri memorat prin matricea de adiacenţă şi două noduri x şi y. Să
se determine toate lanţurile hamiltoniene având ca extremităţi nodurile date, daca există, altfel să se
afişeze mesajul „Nu există!”.
13. Se dă un graf neorientat cu n noduri memorat prin lista de adiacenţă. Să se scrie un program care
construieşte în memorie matricea de adiacenţă şi afişează subgraful obţinut prin eliminarea nodului de
grad maxim.
14. Să se scrie un program care pentru un graf memorat prin matricea de adiacenţă, cu n noduri,
determină numărul de muchii al grafului şi determină subgraful cu număr minim de vârfuri şi cu
proprietatea că orice vârf al său are gradul cel puţin egal cu 2. Dacă nu există un astfel de subgraf să se
afişeze mesajul „Nu există!”.
15. Se dă un graf neorientat cu n noduri memorat prin lista de adiacenţă. Să se scrie un program care
determină cel mai lung lanţ elementar din graf şi îl afişează.
10.2. Grafuri orientate
u2 u2
1 2 1 2
u1
u3 u3
u4 u4
3 u5 3
4 4
5 5
u7 u6 u7 u6
6 6
G=(X,U) Graf partial
Definiţie. Fie G = ( X , U ). Un subgraf al lui G, este un graf G 1 = ( Y , T ) astfel încât Y X, iar
T conţine toate arcele din U care au ambele extremităţi în Y ( se obţine din G eliminând o parte din
noduri şi păstrând acele arce care au ambele extremităţi în mulţimea nodurilor rămase ).
Exemplu. Y={3,4,5,6} T={[4,3],[3,5],[5,6],[6,4]}
u2
1 2 u4 u5
3
u1 4
u3 5
u4 u7 u6
3 u5
4
5 6
u7 u6
6
G=(X,U) Subgraf
AM n x n a[i,j]=
BM n x m b[i,j]=
DM n x m d[i,j]=
Exemplu.
a= b= d=
Definiţia Un graf orientat este complet dacă oricare două vârfuri, i şi j (i≠j), sunt adiacente.
Definiţia Un graf orientat este turneu, dacă oricare ar fi două vârfuri i şi j, i≠j, între ele există un singur arc:
arcul (i,j) sau arcul (j,i).
Definiţie. Un graf G este conex, dacă oricare ar fi două noduri ale sale, există un lanţ care le leagă.
Observaţie. Dacă graful nu este conex, atunci poate fi descompus în componente conexe.
Definiţie. Se numeşte componentă conexă a grafului G = ( X , U ), un subgraf G 1 =( X 1 , U 1 ) a lui
G, conex, cu proprietatea că nu există nici un lanţ care să lege un nod din X 1 cu un nod din X – X 1 .
Exemplu. Graf neconex :
Definiţie. Un graf orientat G = ( X , U ) este tare conex, dacă pentru oricare două noduri x şi y
X, există un drum de la x la y precum şi un drum de la y la x.
Observaţie. Dacă graful nu este tare conex, atunci poate fi descompus în componente tare conexe.
Definiţie. Se numeşte componentă tare conexă a grafului orientat G = ( X , U ), un subgraf G 1 =
( X 1 , U 1 ) a lui G, tare conex, cu proprietatea că pentru orice nod x
X – X 1 subgraful indus de X 1 { x } nu mai este tare conex.
- se selectează vârfurile grafului unul cate unul in n-1 paşi in ordinea crescătoare a costului drumului
de la vârful de start x la ele, intr-o multime care conţine initial doar vârful de start se foloseşte
vectorul prec definit astfel:
prec[i]=k atunci k este vârful precedent lui I pe drumul minim de la x la i
- se mai folosesc doi vectori d[i] reprezintă costul minim al drumului de la x la I si s[i]=1 daca vârful I
a fost vizitat si 0 un caz contrar
Paşii care se executa in algoritmul lui Dijkstra:
1. se selectează vârful de start
2. are loc repetarea următoarei secvenţe de cel mult n-2 ori:
2.1. se caută vârful k neselectat, cu d[k] minim si se selectează
2.2. se actualizează vectorul d pentru acele vârfuri I neselectate dar pentru care fostul d[i]
este mai mic decât d[k]+costul arcului (k,i); astfel d[i]=d[k]+c[k,i] iar prec[i]=k.
Aşadar drumul de la x la I are ca varf intermediar nodul k care se afla inainte de i
3. la sfarsit folosind vectorul prec se afişează drumurile de la x la fiecare varf I al grafului
precum si costurile acestor drumuri
– determină lungimea drumurilor minime între oricare două noduri ale unui graf
– graful este reprezentat prin matricea de costuri, c
– dacă de la nodul i la nodul j nu există arc, c[i,j]=1000.
Plecăm de la următoarea idee: dacă drumul minim între două noduri oarecare i şi j trece printr-un nod k,
atunci drumurile de la i la k şi de la k la j sunt la rândul lor minime. Pentru fiecare pereche de noduri (i,
j ), cu i, j {1,2,…,n}, procedăm astfel:
Dăm lui k pe rând valorile 1,2,…,n, pentru ca nodul k despre care vorbeam mai sus poate
fi, cel puţin teoretic, orice nod al grafului. Pentru fiecare k:
dacă suma dintre costul drumului de la i la j şi costul drumului de la k la j este mai
mică decât costul drumului de la i la j {a[i, k]+a[k, j]<a[i, j]}, atunci drumul iniţial
de la i la j este înlocuit cu drumul indirect ikj. această înlocuire fireşte că se va
opera ca atare în matricea costurilor: {a[i, j]:=a[i, k]+a[k, j]}.
1. Câte noduri are graful orientat cu 6 noduri şi următoarele arce: (1,5), (1,6), (2,1),
(2,3), (3,1), (3,4), (4,3), (4,5), (5,4), (6,5) au gradul interior egal cu gradul exterior?
a) 2 b) 3 c) 6 d) 5
2. Se consideră un graf orientat cu 8 noduri numerotate de la 1 la 8 şi cu mulţimea arcelor formată
doar din arcele:
- de la fiecare nod numerotat cu număr prim i la nodurile numerotate cu număr par
- de la nodul 1 la nodul 6
- de la fiecare nod numerotat cu i impar la fiecare nod i+1.
Pentru graful dat care este cel mai lung drum format doar din noduri distincte care uneşte nodul 2 cu nodul
8?
a) 2 b) 3 c) 4 d) 5
3. Se consideră graful orientat reprezentat prin listele de adiacenţă alăturate. Câte nod lista
noduri au gradul extern mai mic decât gradul intern? 1: 2,6,5
2: 3,4
3: 1
4: 5, 6
a) 2 b) 3 c) 6 d) 5 5: 6
6. Care este numărul de circuite distincte ale grafului orientat dat prin lista de adiacenţă alăturată?
a) 0 b) 1 c) 2 d) 3
7. Se consideră graful orientat cu 6 noduri şi următoarele arce (1,2), (1,5), (1,6), (2,3), (3,6), (4,1),
(6,4). Care este nodul accesibil din toate celelalte vârfuri prin intermediul unor drumuri elementare?
a) 6 b) 1 c) 5 d) 3
9. Gradul intern pentru nodul cu eticheta i dintr-un graf orientat la care se cunoaşte matricea de
adiacenţă este egal cu numărul de cifre egal cu 1 aflate pe:
a) linia i
b) diagonala principală
c) diagonala secundară
d) coloana i
10. Un graf orientat are 5 noduri numerotate de la 1 la 5 şi 4 arce: (1,2), (2,1), (2,3), (3,4). Prin
eliminarea nodului 2 şi a arcelor incidente cu acesta se obţine:
a) un subgraf cu 4 noduri şi un arc
b) un graf parţial
c) un subgraf cu 4 noduri şi nici un arc
d) un subgraf cu 3 noduri şi 3 arce distincte
Răspunsuri itemi cu alegere multiplă
10. Grafuri
void main()
{
citire(); nrc=1;
for(i=1;i<=n;i++)
if (s[i]==0) {s[i]=nrc;
df1(i);
df2(i); for(j=1;j<=n;j++)
if(s[j]!=p[j]) {s[j]=0;p[j]=0;} nrc++;}
for(i=1;i<nrc;i++)
{cout<< "Componenta "<<i<<endl; for(j=1;j<=n;j++)
if(s[j]==i) cout<<j<<" "; cout<<endl;
}}
2. Algoritmul lui Dijkstra Fie un graf orientat cu costuri asociate arcelor. Se dă un varf r de plecare, să
se determine pentru orice pereche de vârfuri (r,x) costul drumului minim care le uneşte.
Exemplu:
3. Algoritmul lui Roy – Floyd Fiind dat un graf orientat cu costuri asociate arcelor, se cere să se
determine pentru oricare două vârfuri lungimea minimă a drumului care le leagă.
Rezolvare
#include<iostream.h>
int a[20][20],n;
void citire()
{int i,j;
cin>>n;
for(i=1;i<=n;i++)
for (j=1;j<=n;j++)
cin>>a[i][j];}
void drum(int i,int j)
{int k=1, b=0;
while ((k<=n) && !b)
{if (i!=k && j!=k && a[i][j]==a[i][k]+a[k][j])
{ drum(i,k);
drum(k,j);
b=1;}
k++;}
if(!b)
cout<<j<<" ";}
void sdrum(int ni, int nf)
{if(a[ni][nf]<32000)
{cout<<"Drumul de la"<<ni<<"la"<<nf<<"are lungimea: "<<a[ni][nf]<<endl;
cout<<ni<<" ";
drum(ni,nf);}
else cout<<"Nu exista drum de la "<<ni<<" la "<<nf;}
void lung()
{int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (a[i][j]>a[i][k]+a[k][j]) a[i][j]=a[i][k]+a[k][j];}
void main()
{int ni,nf;
citire();
lung();
cin>>ni>>nf;
sdrum(ni,nf);}
4. Fiind dat un graf orientat prin matricea de adiacenţă se cere să se determine, dacă există, un ciclu
hamiltonian.
Rezolvare #include<iostream.h> int n,
s[20], a[20][20];
void citire()
{ int i,j; cin>>n;
for(i=1;i<=n;i++) for(j=1;j<=n;j++)
cin>>a[i][j];
}
int succesor(int k)
{
if (s[k]++<n) return 1; else return 0;
}
int valid (int k)
{
if(a[s[k-1]][s[k]]==0) return 0; else for(int
i=1;i<k;i++)
if (s[i]==s[k]) return 0; if(k==n) if (a[s[k]][1]==0)
return 0; return 1;
}
void tipar()
{
for (int i=1;i<=n;i++) cout<<s[i];
cout<<s[1]<<endl;
}
void back(int k)
{
if(k==n+1) tipar(); else
{ s[k]=1;
while(succesor(k))
if (valid(k)) back(k+1);
}
}
void main()
{citire();
s[1]=1;
s[2]=1;
back(2);
}
5. Algoritmul lui Roy – Warshall pentru determinarea matricei drumurilor unui graf orientat memorat
prin intermediul matricei de adiacenţă.
Rezolvare
#include<iostream.h>
int n,d[20][20],i,j,k;
void main()
{cin>>n;
for(i=1;i<=n;i++)
for (j=1;j<=n;j++)
cin>>d[i][j];
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if ((d[i][j]==0) && (i!=k) && (j!=k))
d[i][j]=d[i][k]*d[k][j];
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++) cout<<d[i][j]<<"
";
cout<<endl;}}
1. Să se scrie un algoritm care verifică dacă un graf orientat memorat prin listele de adiacenţă are noduri
cu gradul intern nul.
2. Se dă un graf orientat cu n noduri memorat prin matricea de adiacenţă şi un nod x. Să se afişeze
nodurile legate de x prin drumuri de lungime impară, daca există, altfel să se afişeze mesajul „Nu
există!”.
3. Se dă un graf orientat memorat prin listele de adiacenţă. Să se scrie un program care verifică dacă o
succesiune de noduri citită de la tastatura este sau nu lanţ in graful dat şi afişează lungimea lanţului.
5. Se dă un graf orientat cu n noduri memorat prin listele de adiacenţă. Să se scrie un algoritm care
elimină arcul (x,y).
6. Se dă un graf orientat cu n noduri memorat prin lista de adiacenţă. Să se scrie un program care elimină
din graf toate arcele corespunzătoare vârfurilor cu grad minim.
7. Se dă un graf orientat cu n noduri memorat prin lista de adiacenţă. Să se scrie un program care
construieşte în memorie matricea de adiacenţă şi verifică dacă acesta conţine lanţuri de lungime k,
unde k este un număr natural citit de la tastatură mai mic decât n.
8. Se dă un graf orientat cu n noduri memorat prin lista de adiacenţă. Să se scrie un program care
construieşte în memorie matricea de adiacenţă şi verifică dacă o succesiune de noduri dată de la
tastatură este sau nu ciclu în graful dat.
10. Se dă un graf orientat in care are toate vârfurile au gradul intern par. Să se scrie un algoritm care
determină toate ciclurile elementare ale grafului.
11. Se dă un graf orientat cu n noduri memorat prin matricea de adiacenţă şi două noduri x şi y. Să se
determine toate vârfurile care au aceleaşi grade interne ca vârful x şi aceleaşi grade externe ca vârful
y.
12. Se dă un graf orientat cu n noduri memorat prin matricea de adiacenţă. Să se determine toate
ciclurile care trec prin noduri cu gradul extern număr prim, daca există, altfel să se afişeze mesajul
„Nu există!”.
13. Se dă un graf orientat cu n noduri memorat prin lista de adiacenţă. Să se scrie un program care
construieşte în memorie matricea de adiacenţă şi afişează subgraful obţinut prin eliminarea vârfurilor
care au gradul intern egal cu gradul extern.
14. Să se scrie un program care pentru un graf orientat memorat prin matricea de adiacenţă, cu n
noduri, determină numărul de arce ale grafului şi determină subgraful cu număr minim de vârfuri şi cu
proprietatea că orice vârf al său are gradul intern cel puţin egal cu 2 şi gradul extern cel mult 3. Dacă
nu există un astfel de subgraf să se afişeze mesajul „Nu există!”.
15. Se dă un graf orientat cu n noduri memorat prin lista de adiacenţă. Să se scrie un program care
determină cel mai lung lanţ elementar din graf şi îl afişează.
10.3. Arbori
Definiţie. Fie G un graf. Un graf parţial H al său care în plus este şi arbore se numeşte
arbore parţial.
Corolar. Un graf G=(X, U) conţine un arbore parţial dacă şi numai dacă G este conex.
Reprezentarea arborilor
Fie un arbore cu n noduri.
1. Reprezentare prin matrice de adiacenţă.
aM
nxn 1, daca i este tatal lui j
a[i,j]=
0 , in caz contrar
0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 1 0 0
a 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0
3. Vector de taţi – memorează pentru fiecare nod părintele acestuia. Pentru rădăcină elementul
corespunzător din vector este egal cu 0.
T=(0,1,1,1,3,3,3,4,7,7)
Arborii pot fi parcurşi prin metode specifice grafurilor: în adâncime, lăţime.
Arbori binari
Definiţie. Un arbore în care fiecare nod are maxim doi descendenţi se numeşte
arbore binar.
Dacă aceşti descendenţi există ei se numesc descendent stâng, respectiv descendent drept.
Definiţie: Se numeşte arbore binar complet un arbore binar în fiecare nod, care nu este frunză, are exact doi
descendenţi.
Propoziţie: Un arbore binar complet care are p noduri terminale, toate situate pe acelaşi nivel, are în total 2p-
1 noduri.
Arborii binari pot fi parcurşi prin metode specifice grafurilor: în adâncime,
lăţime.
Metode specifice arborilor binari :
Exemplu.
Soluţiile de parcurgere ale arborelui din figura următoare :
1. Care este înălţimea şi care sunt frunzele arborelui descris prin vectorul de „taţi”: (0, 1, 1, 2, 2, 5, 3,
3)?
a) înălţimea 3 şi frunze: 4, 5, 6 b) înălţimea 4 şi frunze: 4, 6, 7, 8
c) înălţimea 4 şi frunze: 4, 5, 6 d) înălţimea 3 şi frunze: 4, 6, 7, 8
2. Câte frunze are arborele descris prin următorul vector de „taţi”: (0, 1, 2, 2, 4, 1, 6, 6,
8, 8)?
a) 4 b) 6 c) 5 d) 3
4. Pentru arborele având următorul vector de „taţi” (2, 3, 0, 1, 1, 2, 4, 5) care este rădăcina şi care
sunt descendenţii direcţi ai nodului 2?
a) răd: 3 şi descendenţii direcţi: 1, 6 b) răd: 3 şi descendenţii direcţi: 2, 6
c) răd: 1 şi descendenţii direcţi: 4, 6 d) răd: 2 şi descendenţii direcţi: 1, 6
6. Care sunt nodurile care au exact 2 descendenţi pentru un arbore cu 9 noduri, numerotate de la 1 la 9,
dat de vectorul de „taţi”: (5, 1, 1, 5, 0, 4, 4, 7, 7)?
a) 1,2,3 b) 1,4,5 c) 1,4,5,7 d) 2,4,5,7
7. Câte noduri trebuie eliminate dintr-un graf complet cu 15 noduri, pentru ca acesta să devină arbore?
a) 120 b) 106 c) 116 d) 14
9. Se consideră arborele cu 7 noduri şi muchiile (1,5), (1,2), (2,3), (3,4), (3,6), (1,7). Care dintre
nodurile arborelui ar putea fi alese ca rădăcină pentru ca arborele să aibă număr maxim de niveluri?
a) 1,4,5,6 b) 4,5,6,7 c) 1,6,7 d) 1,2
10. Se consideră vectorul de „taţi” al unui arbore oarecare t=(0, 1, 1, 2, 2, 3, 3, 7), în care nodurile
sunt numerotate de la 1 la 8. Alegeţi afirmaţia incorectă:
a) nodurile 4,5 sunt fraţi b) nodul 3 are gradul 2
c) nodul 3 este tatăl lui 1 d) nodurile 4,5,6,8 sunt frunze
11. Se consideră arborele cu 9 noduri şi muchiile (1,5), (1,2), (2,3), (3,4), (3,6), (1,7), (7,8), (5,9). Dacă
alegem ca rădăcină nodul 2 , atunci vectorul corespunzător de „taţi” al arborelui este:
a) (2, 0, 2, 3, 1, 1, 5, 7, 8)
b) (2, 0, 2, 1, 3, 1, 3, 7, 8)
c) (2, 0, 2, 3, 1, 3, 1, 7, 5)
d) (1, 0, 2, 3, 1, 3, 5, 7, 7)
12. Se consideră vectorul de „taţi” al unui arbore oarecare t=(0, 1, 1, 2, 2, 3, 3, 7), în care nodurile sunt
numerotate de la 1 la 8. Alegeţi afirmaţia corectă:
a) nodurile 2,4,6 sunt fraţi b) nodul 5 are gradul 3
c) nodul 3 este tatăl lui 1 d) nodurile 4,5,6,8 sunt frunze
13. Precizaţi câte muchii trebuie înlăturate din graful a cărui 01100000
matrice de adiacenţă este dată alăturat, astfel încât să devină 00011000
arbore? 00000110
00000000
a) 1 b) 2 c)0 d) 3 00000000
00000001
00000001
14. Fie G un graf conex cu 50 de noduri si 1500 muchii. Numărul de muchii care trebuie
eliminate din G astfel încât acesta să devină arbore este:
a) 1451 b) 49 c) 1450 d) 100
10. Grafuri
10.2. Arbori
1.b 2.c 3.d 4.a 5.a 6.c 7.d 8.d 9.b 10.c 11.c 12.d 13.a 14.a 15.c
1. Se citeşte un graf prin intermediul matricei de adiacenţă. Să se scrie un program care verifică dacă
este arbore.
Exemplu:
n=5 şi matricea de adiacenţă 0 1 0 1 1
00000
00000
00000
0 0 1 0 0 se va afişa ARBORE
Rezolvare
Aceasta este o funcție recursivă de parcurgere în adâncime (DFS – Depth-First Search), care:
-pornește de la nodul nod
-vizitează toate nodurile accesibile
-verifică dacă există cicluri
-și dacă graful este conex
#include <iostream>
using namespace std;
int s[20],a[20][20], b,n,i, suma; // a - matrice adiacență, s - vector de vizitare, n - nr. noduri
void dfs(int nod)// s[] = vector de vizitare, b = 1 → marchează existența unui ciclu
{int k;
s[nod]=1; // marcăm nodul curent ca vizitat
for(k=1;k<=n;k++)
if (a[nod][k]==1)// a[nod][k] == 1 pentru a verifica dacă există o muchie de la nod la k
{a[k][nod]=0;// eliminăm muchia inversă (dacă este neorientat)
if(s[k]==0)
dfs(k); // nodul k nu a fost vizitat => îl vizităm recursiv
else
b=1;}} // nodul k a fost deja vizitat => CICLU detectat!
int main()
{cin>>n;
for(i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
dfs(1); // pornim parcurgerea de la nodul 1
suma=0;
for(i=1;i<=n;i++)
suma=suma+s[i];
if (suma!=n)
cout<<"Nu este conex"<<endl;
else
if(b) cout<<"Are cicluri"<<endl;
else cout<<"Arbore"<<endl;
return 0;}
int s[20],a[20][20],n;// s[] este vectorul de vizitare (s[i] = 1 ⇒ nodul i a fost vizitat)
using namespace std;
2 3 4 Niv 2
5 6 7 8 Niv 3
9 10 Niv 4
Rezolvare:
#include<iostream>
using namespace std; //rad - radacina
221
int n, c[20],s[20],ic=1,sc=1,a[20][20], i, niv[20], rad; //n – număr de noduri, a[i][j] – matricea de
adiacență
void bfs(int nod) // s[i] – vector de vizitare, niv[i] – nivelul nodului i, c[] – coada pentru BFS(in lățime)
{c[ic]=nod; //Inițializăm coada cu rădăcina nod, pe care o marcăm ca vizitată, ic, sc – capul și coada cozii
s[nod]=1;
niv[nod]=1;
while(ic<=sc) //Cât timp avem noduri în coadă:
{i=1;
while(i<=n)
{if(a[c[ic]][i]==1 && s[i]==0) //Verificăm pt nodul c[ic] toți vecinii i, dacă i este vecin și nu a fost vizitat
{sc++; //Îl adăugăm în coadă
c[sc]=i;
s[i]=1;
niv[c[sc]]=niv[c[ic]]+1;} //Îi setăm nivelul ca nivelul tatălui + 1
i++;}
ic++;}}
int main()
{cin>>n;
for (i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j]; cout<<"Radacina este ";
cin>>rad;
bfs(rad);
for(i=1;i<=n;i++)
cout <<"Nodul "<<i<<" nivelul "<<niv[i]<<endl;
return 0;}
222
iniţializare {1}, {2}, {3}, {4}, {5}, {6}, {7}
1 {1, 2} {1, 2}, {3}, {4}, {5}, {6}, {7}
2 {2, 3} {1, 2, 3}, {4}, {5}, {6}, {7}
3 {4, 5} {1, 2, 3}, {4, 5}, {6}, {7}
4 {6, 7} {1, 2, 3}, {4, 5}, {6, 7}
5 {1, 4} {1, 2, 3, 4, 5}, {6, 7}
6 {2, 5} respinsa (formează ciclu)
7 {4, 7} {1, 2, 3, 4, 5, 6, 7}
Mulţimea A este iniţial vidă şi se completează pe parcurs cu muchii acceptate (care nu formează un
ciclu cu muchiile deja existente în A). În final, mulţimea A va conţine muchiile {1, 2}, {2, 3}, {4, 5},
{6, 7}, {1, 4}, {4, 7}. La fiecare pas, graful parţial <V, A> formează o pădure de componente
conexe, obţinută din pădurea precedentă unind două componente. Fiecare componentă conexă este la
rândul ei un arbore parţial de cost minim pentru vârfurile pe care le conectează. La sfârşit, vom avea o
singură componentă conexă, care este arborele parţial de cost minim căutat (Figura b).
Rezolvare:
#include<iostream>
using namespace std;
struct muchie
{int x, y, z; //s[i] = 1- marchează că muchia i a fost aleasă în arbore
}v[20]; // vector de muchii - v[1], v[2], ..., v[m]-fiecare element e o muchie
int n, m, d[20], s[20]; //d[i] – componenta din care face parte nodul i; n – nr noduri; m – nr muchii
void ordonare(int m) //v[i].y - nodul de sosire al muchiei i
{int i, a=0, q, w, e; //v[i].z - costul muchiei i
while(a==0) //v[i].x - nodul de pornire al muchiei i
{a=1;
for (i=1;i<m;i++)
if (v[i].z>v[i+1].z)
{q=v[i+1].x;
w=v[i+1].y;
e=v[i+1].z;
v[i+1].x=v[i].x;
v[i+1].y=v[i].y;
v[i+1].z=v[i].z;
v[i].x=q;
v[i].y=w;
v[i].z=e;
a=0;}}}
int main()
{int i;
cin>>n>>m;
for (i=1;i<=m;i++)
cin>>v[i].x>>v[i].y>>v[i].z;
ordonare(m);
for (i=1;i<=n;i++)
d[i]=i;
for (i=1;i<=m;i++)
223
if (d[v[i].x]!=d[v[i].y]) // le unesc în aceeași componentă
{int aux = d[v[i].y];
for (int j=1; j<=n; j++)
if(d[j] == aux)
d[j] = d[v[i].x];
s[i] = 1; }// marchez muchia ca fiind aleasă
cout << "Muchiile arborelui de cost minim:\n";
for (i=1;i<=m;i++)
if(s[i]==1)
cout<<v[i].x<<" "<<v[i].y<<endl;
return 0;}
1. Se dă un graf conex. Se cere împărţirea acestuia în m arbori parţiali de cost minim fiecare cu p
vârfuri. Să se afişeze aceşti arbori.
2. Să se creeze un arbore binar care are drept chei numere întregi citite de la tastatură. Să se afişeze
produsul cheilor impare din arbore.
3. Să se creeze un arbore binar care are drept chei numere întregi citite de la tastatură. Să se afişeze
produsul cheilor pozitive şi numărul cheilor negative din arbore.
4. Să se creeze un arbore binar care are drept chei numere întregi citite de la tastatură. Să se afişeze
nodurile din arbore care au exact doi succesori.
5. Să se scrie un program care afişează cheile nodurilor unui arbore aflate pe un anumit nivel k citit
de la tastatură.
6. Să se scrie un program care afişează parcurgerea în preordine, inordine şi postordine a unui arbore
binar.
7. Să se scrie un program care afişează elementul de pe poziţia k, unde k este citit de la tastatură, din
parcurgerea în preordine, inordine şi postordine a unui arbore binar.
10. Să se creeze un arbore binar care are drept chei numere întregi citite de la tastatură. Să se afişeze
nodurile din arbore care au unul din succesori cu cheia număr par.
11. Se dă un arbore ale cărui chei sunt numere întregi, nu neapărat distincte. Să se afişeze cheile
distincte ale arborelui şi numărul acestora.
224
12. Se dă un arbore binar ale cărui chei sunt numere întregi. Să se afişeze suma cheilor pare aflate pe
poziţii impare la parcurgerea în inordine a arborelui.
13. Se dă un arbore binar ale cărui chei sunt numere întregi. Să se afişeze cheile divizibile cu primul
şi ultimul element din parcurgerea în postordine a arborelui.
14. Se dă un arbore binar ale cărui chei sunt numere întregi. Să se afişeze numărul de noduri a căror
cheie este egală cu o valoare k citită de la tastatură şi nivelul pe care acestea se află.
15. Se dă un arbore binar ale cărui chei sunt numere întregi. Să se afişeze numărul de noduri
terminale a căror cheie este egală cu o valoare k citită de la tastatură şi nivelul pe care acestea se află
este număr impar.
📘 6. BAZE DE DATE
6.1 Concepte de bază
Bază de date (BD)
O bază de date este o colecție organizată de date corelate logic, stocate electronic, care permite:
Exemple de SGBD:
MySQL
Oracle Database
Microsoft Access
Microsoft SQL Server
Exemplu:
Firmă → Departament → Angajat
Model rețea
Model relațional
226
Datele sunt organizate în tabele
Relațiile se realizează prin chei (primare și externe)
Cel mai utilizat model
Atribute
o compuse: adresă
o derivate: vârstă
o multivaloare: telefon
Identificator unic
Normalizarea datelor
227
Tabel
Coloane = câmpuri
Rânduri = înregistrări
Cheie primară
Cheie străină
Constrângeri
Integritate referențială
Exemple SQL
SELECT simplu:
INSERT:
INSERT INTO Elevi (nume, prenume, clasa) VALUES ('Ionescu', 'Ana', 'IX B');
UPDATE:
228
UPDATE Elevi SET clasa='XII' WHERE ID=2;
DELETE:
💻 7. ARHITECTURA GENERALĂ A
SISTEMELOR DE CALCUL
Prezentare generală
Sistem de calcul = hardware + software
Scop: prelucrarea informațiilor
Tipuri de sisteme
Componente
1. Hardware: unitate centrală, memorie, periferice
2. Software: sistem de operare, aplicații
Memorie internă
RAM (volatilă)
ROM (permanentă)
Cache (foarte rapidă)
Memorie externă
229
HDD, SSD, stick USB, CD/DVD
Dispozitive periferice
Ergonomie și siguranță
Poziție corectă
Iluminare adecvată
Pauze regulate
Distanța față de monitor: 50–70 cm
Tipuri
Monotasking/multitasking
Mono-user/multi-user
În timp real
Mobile
Caracteristici
230
Programe pentru fișiere comprimate
Securitatea datelor
📄 9. APLICAȚII DE BIROTICĂ
Procesoare de text
Microsoft Word
Funcții: redactare, formatare, inserare tabele și imagini
Microsoft Excel
Funcții: formule, grafice, sortare, filtrare
Editoare de prezentări
Microsoft PowerPoint
Funcții: diapozitive, animații, multimedia
Tipuri
Funcții
Partajare resurse
Comunicare
Colaborare
231
Protocoale
Internet
Adresare
Limbaj HTML
<html>
<head><title>Pagina mea</title></head>
<body>
<h1>Salut</h1>
<p>Primul paragraf</p>
</body>
</html>
232