INFORMATICA/C/C++

ALGORITMI

Cand construim un algoritm trebuie sa tinem cont de urmatoarele reguli:
Sa se definesca exact datele asupra caroro lucreaza algoritmul(date de intrare, date de iesire si intermediare);
Sa definim exact operatiile care se vor executacu datele asupra carora lucreaza algoritmul;
Sa definim exact notiunea de structura si control a algoritmului;
Sa definim exact succesiunea de structure care formeaza algoritmul

Principiile programrii structurate
1)Structura liniara: este structura in care pasii se executa in ordinea in care au fost scrisi: pas1,pas2, ….,pasi,pasi+1,….pasn-1,pasn .
Un pas al structuriise executa numai daca au fost executatitoti pasii care-l preced.
Exemplu:se introduce de la tastatura trei numere a,b si c. Sa se calculeze media aritmetica dintre a si b si media aritmetica dintre b si c.

Pas1: inceput
Pas2: comunica valorile pentru a, b, c
Pas3: calculeaza m1<-(a+b)/2
Pas4: calculeaza m2<-(b+c)/2
Pas5: comunica valorile lui m1 si m2
Pas6: terminat

Pseudocod:

intreg a, b,c;
real m1,m2;
inceput
Citeste a, b, c;
m1<-(a+b)/2;
m1<-(a+b)/2;
scrie m1,m2;
sfarsit



2)Structura alternativa
Se face selectarea intre doua sau mai multe actiuni, in functie de anumite conditii. Exista doua tipuri:
a)alternativa simpla
b)alternative generalizata

SIMPLA:se face selectarea intre doua actiuni, in functie de indeplinirea sau neindeplinirea unei conditii.De exemplu:
daca anul este bisect, atunci imparte totalul la 366;altfel imparte la 366.Conditia este tipul anului.
Exemplu: se introduce de la tastatura un numar n. Sa se calculeze inversul acestui numar, inv, definit astfel:

inv={█(1/n,pt n≠0@0,pt n=0)┤

Pseudocod:

intreg n;
real inv;
inceput
citeste n;
daca n<>0
atunci
inv<-1/n;
altfel
inv<-0;
sfarsit_daca;
scrie inv;
sfarsit.

GENERALIZATA:se face selectarea intre mai multe actiuni, in functie de o variabila de memorie numita selector, care poate lua mai multe valori, dintr-o multime ordonata de elemente de acelasi tip cu selectorul.De exemplu:
daca este clasa IX-A sunt 27 de elevi,daca este clasa IX-B sunt 28 de elevi.In acest caz selectorul este numele clasei iar multimea de valori este formata din numele de clasa.
Exemplu:se introduc de la tastatura numerele intregi n, a, b si c.Sa se calculeze valoare lui e definit altfel:

e{█((a+b)c,pt n=1@(b+c),pt n=2@(c+a),pt n=3)┤
Pseudocod:

intreg n,a,b,c;
real c;
inceput
citeste n,a,b,c;
daca n=1
atunci e<-(a+b)/c;
altfel
daca n=2
atunci e<-(b+c)/a;
altfel
daca n=3
atunci e<-(c+b)/a;
sfarsit_daca;
sfarsit_daca;
sfarsit_daca;
scrie e;
sfarsit;

3)Structura repetitiva
Se executa treptat o actiune sau o secventa de actiuni, atat tip cand conditia precizata este adevarata.De exemplu:
- cat timp semaforul este verde, mai trece o masina
- cat timp mai sunt numere la adunam la sursa
- incepand de la numarul 1, scrieti in ordine numerele pana la 100




Exemplu: se introduc de la tastatura mai multe numere pana cand ultimul numar este 0 si trebuie sa se calculeze suma numerelor.

Pseudocod:

executa s<-0
citeste valoare lui a
testeaza a<>0
executa s<-s+a; citeste a;
testeaza a<>0;
…………..
testeaza a<>0 pana cand a=0;
scrie valoarea lui s

a)repetitive cu numar cunoscut de pasi
Sunt necesare doua variabile de memorie: una numita contor(de exemplu,i ), care se foloseste pentru a numarade carte ori s-a executat repetat corpul ciclului, si una numita numar de repetari(de exemplu, n), care determina de cate ori trebuie sa se executa repetat corpul ciclului.
Exemplu: sa se calculeze suma a n numere introduce de la tastatura

Pseudocod:
intreg i,n;
real s,a;
inceput
citeste;
s<-0;
pentru i<-1,n executa
citeste a;
s<-s+a;
sfarsit_pentru;
scrie s;
sfarsit.

b)repetitive cu numar necunoscut de pasi
- conditionata anterior: testeaza conditia de terminare a ciclului inainte de executarea corpului ciclului
cat_timp conditie executa
actiune;
sfarsit_cat-timp;

-conditionata posterior:testeaza conditaia de terminare a ciclului dupa executarea corpului ciclului

Exemplu:se introduce de la tastatura mai multe numere pana cand ultimul numar este 0 si trebuie sa calculeze suma numerelor.
Variant1(anterior)
real s,a;
inceput
s<-0;
citeste a;
cat_timp a<>0 executa
s<-s+a;
citeste a;
sfarsit_cat_timp;
scrie s;
sfarsit.

Varianta2(posterior)
real s,a;
inceput
s<-a;
citeste a;
repeata
s<-s+a;
citeste a;
pana_cand a=0;
scrie s;
sfarsit.





ALGORITM INTERSCHIMBARE
Exemplu:se citeste un numar natural format din trei cifre.Sa se afiseze numarul minim care se poate forma din cifrele sale(exemplu:nr 321 se poate forma 123).

intreg n,a,b,c,x;
inceput
citeste n;
a<-n div 100;
b<-(n div 10) mod 10;
c<-n mod 10;
daca a>b
atunci x<-a;
a<-b;
b<-x;
sfarsit_daca
daca b>c
atunci x<-b;
b<-c;
c<-x;
sfarsit_daca
daca a>b
atunci x<-a;
a<-b;
b<-x;
sfarsit daca
n<-a*100+b*10+c;
scrie n;
sfarsit.









ALGORITM DETERMINAREA MAXIMULUI(MINIM)

Exemplu 1: Se introduce de la tastatura un sir de n numere de la tastatura. Sa se afiseze maximuldintre acestea.

intreg a, max,n,I;
inceput
citeste n,a;
max<-a;
pentru i<-2,n executa
citeste a;
daca a>max;
atunci max<-a;
sfarsit_daca;
sfarsit_pentru;
scrie max;
sfarsit.

Exemplu 2: Se introduce un sir de numere de la tastatura pana la intalnirea valorii 0. Sa se afiseze maximul.

intreg a,max;
inceput
citeste a;
max<-a;
cat_timp a<>0 executa
daca a>max;
atunci a<-max;
sfarsit_daca;
citeste a;
sfarsit_cat_timp;
scrie max;
sfarsit.




ALGORITM PENTRU PRELUCRAREA CIFRELOR UNUI NUMAR
1)EXTRAGEREA CIFRELOR
Exemplu1: Se citeste un numar natural n.Sa se afiseze suma si produsul cifrelor sale.
intreg n,s,p;
inceput
citeste n;
s<-0;
p<-1;
cat_timp n<>0, executa
s<-s+n mod 10;
p<-p*(n mod 10);
n<-n div 10;
sfarsit_cat_timp;
scrie s,p;
sfarsit.
Exemplu2: Se introduce de la tastatura un sir de numere natural, pana la citirea valorii 0. Sa se afiseaza toate perechiile de numere introduce consecutive care au proprietatea ca al doilea numar este egal cu suma cifrelor primului numar.

intreg a,b,s,x;
inceput
citeste a,b;
cat_timp b<>0 executa
s<-0;
x<-a;
cat_timp x<>0 executa
s<-s+x mod 10
x<-x div 10;
sfarsit_cat_timp;
daca a=b
atunci scrie a, b;
sfarsit_daca;
a<-b;
citeste b;
sfarsit_cat_timp;
sfarsit.
2)COMPUNEREA UNUI NUMAR DIN CIFRELE SALE

Exemplu1: Se introduce pe rand, de la tastatura, mai multe numere care reprezinta cifrele unui numar, pana se introduce un numar care nu poate fi cifra. Sa se afiseze numarul obtinut din aceste cifre.

intreg c, nr;
inceput
nr<-0;
citeste c;
cat_timp c>=0 and c<=9 executa
nr<-nr*10+c;
citeste c;
sfarsit_cat_timp;
scrie nr;
sfarsit.
Exemplu2:Se introduce pe rand de la tastatura cele n cifre ale unui numar, incepand cu cifra cea mai semnificativa. Sa se afiseze numarul obtinut din aceste cifre.

intreg n,p,nr,i,c;
inceput
citeste n;
p<-1;
pentru i<-1, n-1 executa
p<-p*10;
sfarsit_pentru;
nr<-0;
pentru i<-1,n executa
citeste c;
nr<-nr+c*p;
p<-p div 10;
sfarsit_pentru;
scrie nr;
sfarsit.

Exemplu3: Se citesc mai multe numere, care reprezinta cifrele unui numar binary, pana cand numarul citit nu este cifra binara. Sa se afisesze numarul binary.

intreg c, nr;
inceput
nr<-0;
citeste c;
cat_timp c=0 or c=1 executa
nr<-nr*10+c;
citeste c;
sfrasit_cat_timp;
scrie nr;
sfarsit.

3)DETERMINAREA INVERSULUI

intreg n,inv;
inceput
citeste n;
inv<-0;
cat_timp n<>0 executa
inv<-inv*10+ n mod 10;
n<-n div 10;
sfarsit_cat_timp;
scrie inv;
sfarsit

Exemplu: Se citeste un numar, sa se verifice daca este palindrom

intreg n,nr,inv;
inceput
citeste n;
nr<-n;
inv<-0;
cat_timp n<>0 executa
inv<-inv*10+ n mod 10;
n<-n div 10;
sfarsit_cat_timp;
daca nr=inv;
atunci
scrie”este palindrom”
altfel
scrie”nu este palindrom”
sfarsit_daca;
sfarsit.
4)CALCULAREA C.M.M.D.C
4.1 algoritmul lui Euclid

intreg a,b,r;
inceput
citeste a,b;
cat_timp b<>0 executa
r<-a mod b;
a<-b;
b<-r;
sfarsit_cat_timp;
scrie”cmmdc”, a;
sfarsit

4.2 scaderi repetate

intreg a,b;
inceput a,b;
citeste a,b;
cat_timp a<>b executa
daca a>b
atunci
a<-a-b;
altfel
b<-b-a;
sfarsit_daca;
sfarsit_cat_timp;
scrie”cmmdc”, a;
sfarsit.
Exemplu:Sa se calculeze cel mai mic mulplipu comun sic el mai mare divisor comun a doua numere a si b care se introduce de la tastatura.

intreg a,b,c,r,x,y,m;
inceput
citeste a,b;
x<-a;
y<-b;
daca b=0
atunci c<-a;
altfel
cat_timp b<>0 executa
rn; atunci scrie”nr este prim”; altfel scrie”nr nu este prim”; sfarsit_daca; sfarsit. 6)PRELUCRAREA DIVIZORILOR UNUI NUMAR 6.1 DIVIZORI PROPRII intreg n,i; inceput citeste n; scrie 1,n; pentru i<-n, n div 2 executa daca n mod i=0 atunci scri i; sfarsit_daca; sfarsit_pentru; sfarsit. 6.2)DIVIZORI PRIMI intreg n, i; inceput citeste n; cat_timp n<>1 executa daca n mod i=0; atunci scrie i; cat_timp n mod i=0 n<-n div i; sfarsit-cat_timp; sfarsit_daca; i<-i+1; sfarsit_cat_timp; sfarsit 7)GENERAREA SIRURILOR RECURENTE(FIBONNACI) intreg a1,a2,a3, n,i; inceput citeste n; a1<-1; a2<-1; scrie a1,a2; pentru i<-3,n executa a3<-a1+a2; scrie a3; a1<-a2; a2<-a3; sfarsit_pentru; sfarsit. Varianta Int fib(int n) { If(n==0) { Return 0;} Else if(n==1) {return 1;} Else Return fib(n-1)+fib(n-2) } ALGORITMI DE SORTARE - vector sursa(nesortat); a - vector destinatie(sortat); b - vector numerator(contor); k 1)metoda numararii int i,n,j,a[50],b[50],k[50]={0}; cout<<”n=”; cin>>; for(i=0;i<=n;i++) { cout<<”a[“<<i<<”]=”; cin>>a;
}
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(a>a[j])
k++;
else
k[j]++;
for(i=0;i<n;i++)
b[k]=a;
for(i=0;i<n;i++)
cout<<b<<” “;

2)metoda selectiei directe

int i,j,n,aux,a[50];
cout<<”n=”;
cin>>n;
for(i=0;i<n;i++)
{
cout<<”a[“<<i<<”]=”;
cin>>a;
}
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(a[j]<a)
{
aux=a;
a=a[j];
a[j]=aux;
}
for(i=0;i<n;i++)
cout<<a<<” “;

3)metoda bulelor

int i,terminat,n,aux,a[50];
cout<<”n=”;
cin>>n;
for(i=0;i<n;i++)
{
cout<<”a[“<<i<<”]=”;
cin>>a;
}
while(!terminat)
{
terminat=1;
for(i=0;i<n-1;i++)
if(a>a[i+1])
{
aux=a;
a=a[i+1];
a[i+1]=aux;
terminat=0;
}
}
for(i=0;i<n;i++)
cout<<a<<” “;

4)metoda inserarii directe

int i,j,n,aux,a[50];
cout<<”n=”;
cin>>n;
for(i=0;i<n;i++)
{
cout<<”a[“<<i<<”]=”;
cin>>a;
}
for(i=1;i<n;i++)
{
aux=a[1];
j=i-1;
while(j>0 && aux<a[j]0
{
a[j+1]=a[j];
j--;
}
if(aux>=a[j])
a[j+1]=aux;
else
{
a[1]=a[0];
a[0]=aux;
}
}
for(i=0;i<n;i++)
cout<<a<<” “;




5)metoda inserarii rapide

int i,n,j,aux,st,dr,mij,a[50];
cout<<”n=”; cin>>n;
for(i=0;i<n;i++)
{
cout<<”a[“<<i<<”]=”;
cin>>aMax nested elements reachedMax nested elements reached