68
Algoritmi
1. Se citește un număr natural n. Să se calculeze : 𝑛!={1,𝑑𝑎𝑐ă 𝑛=0
1∗2∗3∗…∗𝑛,𝑑𝑎𝑐ă 𝑛≥1 } 2. Să se calculeze valoarea expresiei:
a. E=1*2 + 2*3 + 3*4 + ... + n*(n+1) b. E=1+2+3+...+n
c. E=1*2 - 2*3 + 3*4+...+(-1)n *n*(n+1) d. E=11+12+13+⋯+1𝑛e. E=11!+12!+13!+⋯+1𝑛!
3. Să se afișeze numerele mai mici sau egale cu n astfel: (1, n), (2,n-1), (3,n-2)...
*realizati percurgerea programului*transformati for in do si while
Probleme cu cifrele unui număr
Frecvent se pune problema prelucrării cifrelor unui număr și pentru realizareaacestuia se pune problema separării și analiza individuală a fiecărei cifre dintr-un număr dat.
int main(){ cout<<”N=”;
cin>>N;
while (N!=0){ .......N%10; //prelucreaza ultima cifra a lui N
N=N/10; //stergem ultima cifra}
Cout<<”afiseaza cerinta ”<<rezultat;}
• Se citeste un numar format din mai multe cifre.1. Sa se afiseze cifrele separate prin spatii .2. Sa se afiseze suma cifrelor numarului
Se citesc mai multe numere pana se tasteaza cifra 0. Sa se afiseze cifrele pare al numerelorcitite si suma lor
Sa se afiseze divizorii unui numar citit n
Se citesc n valori , sa se afiseze valoarea maxima
Se citesc mai multe valori pana se tasteaza 0.Sa se afiseze cifra valorilor pare, produsul cifrelor impare
Varianta 1citeste A,B;cat timp (B!=0) executa{R=A%B;A=B;B=R;}//se iese cand B este nul=>
scrie A;
Varianta 2.citeste A,Bcat timp (A!=B) executadaca (A>B)
atunci A=A-B;altfel B=B-A;scrie A;
Varianta 3.citeste A,B;cat timp (A*B!=0) executa //daca nici unul nu e nul….daca (A>B) atunci A=A%B;
altfel B=B%A;scrie A+B; //afisez valoarea nenula
Varianta 4.
citeste A, B;cmmdc=0;pentru D=1 , A executadaca (A%D==0 si B%D==0 )
atunci cmmdc=D;scrie cmmdc
CMMDC(a,b)
Problema. Fie doua numere naturale A si B. Sa se determine cel mai mare divizor comun a lui A si B.Sa citim iar: Practic trebuie sa determinam un numar natural care sa fie divizor atat pentru A cat si pentru B. Daca sunt mai multe numere in aceasta situatie, atunci il alegem pe cel mai mare.
.
Calculul CMMMCPentru calculul matematic a cmmdc pentru doua numere A si B, se realizeaza descompunereain factori primi si apoi se considera termenii comuni, la puterea cea mai mica.Pentru calculul matematic a cmmmc pentru doua numere A si B, se realizeaza descompunereain factori primi si apoi se considera termenii comuni si necomuni, la puterea cea mai mare.
A*B=CMMDC(A,B)*CMMMC(A,B).
Cmmdc=3 Cmmmc=18
a= 8
b=10𝑎
𝑏
#include <iostream>using namespace std;int main(){ int a,b,r;
cout << "a=" ; cin>>a;cout << "b=" ; cin>>b;
while(b!=0){ r=a%b;
a=b;b=r;
}cout<<"cmmdc="<<a;return 0;}
cmmmc * cmmdc =a*b;
#include <iostream>using namespace std;int main(){ int a,b,r;
cout << "a=" ; cin>>a;cout << "b=" ; cin>>b;
while (a!=b)if(a>b) a=a-b;else b=b-a;
cout <<"cmmdc= "<<a;
CEL MAI MARE DIVIZOR COMUN
ALGORITMUL LUI NICOMAHUS(metoda scaderilor repetate)
CEL MAI MIC MULTIPLU COMUN
ALGORITMUL LUI EUCLID(metoda impartirilor succesive)
Testarea unui numar prim
Afisarea numerelor prime pereche
pentru a nu pierde numarul n dupa divizari, il retinem in x
Initializam numarul reconstruit din cifre
Testarea unui numar palindrom
Ordinul de multiplicitate a divizorilor unui numar
Transformarea unui numar zecimal in numar binar
#include <iostream>#include<cmath>
using namespace std;
int main(){int n,a;
cout << "n=" << endl;cin>>n;a=sqrt(n);if(a==(sqrt(n)))cout<<"n patrat perfect";else cout<<"nu este pp";return 0;
}
#include <iostream>#include <fstream>using namespace std;int main(){ ifstream f("date.in");
ofstream g("date.out");int t[100],i,n, s;char cl[20];g<<"din ce clasa "; f>>cl;s=0;g<< "cati elevi sunt in clasa "; f>>n;for(i=1;i<=n;i++) //citirea vectorului{ g<<"\n elevul " <<i;
f>>t[i];}
for(i=1;i<=n;i++) // prelucrare vectors=s+t[i];
for(i=1;i<=n;i++) //afisare vectorg<<t[i]<<" ";
g<<"\n media elevilor din clasa "<<cl<< " este "<<s/n;f.close();g.close();return 0;}
Generarea unui vector cu rand
Numararea elementelor pare si impare
a[j]=aux;}//urmeaza afisarea sirului sortat cout<<"Sirul sortat crescator este:"<<=n;i++)cout<<a[i]<<" ";}
Adaugare element la capat
Adaugare element pe pozitia k
Se stiu doi vectori sortați a si b,
Prin interclasarea lor se înțelege construirea unui al treilea vector sortat c care să
conțină toate elementele acestora din a si b.
Se parcurg contorii i si j , se cauta valoarea minima si o duce in c
1
Contorul i parcurge de la 0n vectorul a
Contorul j parcurge de la 0 m vectorul b
Contorul p parcurgevectorul c
•Afisam vectorul c pentru p=0n+m
Declaram a[50], b[50], c[100], n, m, i, j, p;
Citeste a[i];Citeste b[j];int i = 0, j = 0;
while (i < n && j < m)if (a[i] < b[j])
{ c[p] = a[i]; p=p+1; i=i+1;}else
{ c[p++] = b[j++]; p=p+1; j=j+1;}
while (i < n)c[p++] = a[i++];
while (j < m)c[p++] = b[j++];
for(p=0; p<=n+m; p++)cout<<c[p]<<“ ”;
•Inserăm în c elementele rămase din a.
•Inserăm în c elementele rămase din b.
•Parcurgem simultan cei doi vectori,
cât timp i < n și j < m.
Dacă a[i] < b[j], atunci c[p] devine a[i], și îi incrementăm pe i++ și p++.
2
Fișiere text
Subprograme
• sunt părţi ale unui program (modularizate),
• se identifica prin nume,
• In functie de rezultatul returnat , functia va avea un tip de data (void, int, float)
• se pot activa la cerere prin intermediul acestor nume.
int Maxim (int p, int q){
if (p>q) return p;elsereturn q;}
int main(){ int max;max=Maxim(10,20);max=Maxim(max,30);}
Definiţia unui subprogram reprezintă de fapt descrierea unui proces de calcul cu ajutorul
variabilelor virtuale (parametri formali)
Apelul unui subprogram nu este altceva decât execuţia procesului de calcul pentru cazuri
concrete (cu ajutorul parametrilor reali, (efectivi, actuali) ).
tip_returnat nume_funcţie (lista parametrilor formali)
{
instrucţiune; // corpul funcţiei
return x;
}
Definiţia unei funcţii are forma generală:
Unde:
•tip_returnat: reprezintă tipul rezultatului calculat şi returnat de funcţie şi poate fi: int,
char, char*, long, float, void, etc.
•nume_funcţie: Contine doar literele mari si mici ale alfabetului englez, cifrele
sistemului zecimal, caracterul ’_’, cu conditia ca primul caracter sa nu fie cifra.
•lista parametrilor formali: reprezintă o listă de declaraţii de variabile separate prin
virgulă. Această listă poate să fie şi vidă. Pentru fiecare parametru format trebuie :
• tipul parametrului
• numele lui
• modul de transfer (valoare sau referinta)
nume_funcţie (lista parametrilor efectivi);
Apelul unei funcţii care nu returnează o valoare are urmatoarea
forma generala:
#include <iostream>
using namespace std;
void f1 ( )
{ cout << "abc";
}
int main ()
{ f1();
return 0;
}
/* Functia f1 este o functie cu rezultat
void, care nu are parametri formali.
In urma executiei programului se va
afisa: abc */
unde notiunea de parametru efectiv = parametru actual = parametru real = parametru de apel, iar lista parametrilor efectivi poate sa fie vidă, o expresie sau mai multe despărţite prin virgulă
#include <iostream>
using namespace std;
void f2(int k)
{ for (int i=1; i<=k ; i++)
cout << "abc"<< " ";
}
int main ()
{
f2 (3);
return 0;
}
/* Functia f2 este o functie cu rezultat
void, care are un singur parametru
formal K.
Functia f2 este apelata pentru valoarea
3, valoare care va fi preluata de
parametrul formal k si se va afisa:
abc abc abc */
• poate fi apelată ca operand al unei expresii,
• sau poate fi afisata valoarea returnata cout<<nume_functie
Apelul unei funcţii care returnează o valoare
La apelul unei funcţii, valorile parametrilor efectivi se atribuie
parametrilor formali corespunzători.
În momentul în care se întâlneşte un apel de funcţie,
controlul execuţiei programul este transferat primei
instrucţiuni din funcţie, urmând a se executa secvenţial
instrucţiunile funcţiei.
#include <iostream>using namespace std;int schimb(int x, int y){int z;z=x; x=y; y=z;}int main(){int a,b;cout<<"a= "; cin>>a;cout<<"b= "; cin>>b;schimb(a,b);cout<<a<<" "<<b;}
#include <iostream>using namespace std;
int schimb(int &x, int &y){int z;z=x; x=y; y=z;}
int main(){int a,b;cout<<"a= "; cin>>a;cout<<"b= "; cin>>b;schimb(a,b);cout<<a<<" "<<b;}
#include <iostream>using namespace std;
void schimba(int &x,int &y){int z;z=x; x=y; y=z;}int main(){int a,b,c;cout<<"a= "; cin>>a;cout<<"b= "; cin>>b;cout<<"c= "; cin>>c;if (a>b) schimba(a,b);if (b>c) schimba(b,c);if (a>b) schimba(a,b);if (b==(a+c)/2)cout<<a<<","<<b<<","<<c<<"sunt in progresie aritmetica";
elsecout<<a<<","<<b<<","<<c<<"nu sunt in progresie aritmetica";}
Se citesc 3 valori , sa se arate ca sunt in progresie aritmetica
#include <iostream>using namespace std;void creare(int v[50], int n){int i;for ( i=1;i<=n;i++){ cout<<"\n Elementul ["<<i<<"]=";
cin>>v[i];}}void afisare(int v[50], int n){ int i;for ( i=1;i<=n;i++)cout<<v[i] <<" ";}int main(){int a[50], b[50],c[50];cout <<"\n creaza vectorului a:";creare(a,5);cout <<"\n creaza vectorului b:";creare(b,4);cout <<"\n creaza vectorului c:"; creare(c,6);cout <<"\n afiseaza valorile vectorului a:"; afisare(a,5);cout <<"\n afiseaza valorile vectorului b:"; afisare(b,4);cout <<"\n afiseaza valorile vectorului c: ";afisare(c,6);
return 0;}
Se citesc 3 vectori , sa afiseze cei 3 vectori
#include <iostream>#include<cmath>using namespace std;
void creare (int v[50], int n){ int i;
for ( i=1;i<=n;i++){ cout<<"\n Elementul ["<<i<<"]=";
cin>>v[i];}
}void afisare(int v[50], int n){ int i;
for ( i=1;i<=n;i++)cout<<v[i] <<" ";
}int prim (int x){ int nr_div=0,i;
for (int i=2; i<=sqrt(x); i++)if (x%i==0)
return 0 ;return 1;}
int main(){int a[50],i;cout <<"\n creaza vectorul a:”;
creare(a,5);afisare(a,5);cout<<endl;for ( i=1;i<=5;i++)
if(prim(a[i]))cout<<a[i]<<" ";
return 0;}
Se citeste un vector cu 5 elemente, sa se afiseze numerele
prime
#include <iostream>using namespace std;void creare (int v[50], int n){ int i;
for ( i=1;i<=n;i++){ cout<<"\n Elementul ["<<i<<"]=";
cin>>v[i];}
}void afisare(int v[50], int n){ int i;
for ( i=1;i<=n;i++)cout<<v[i] <<" ";
}
int oglindit(int n){int ogl,cn;cn=n;while (n!=0){ ogl=ogl*10+n%10;n=n/10; }if(cn==ogl)return 1;
elsereturn 0;
}
int main(){int a[10],i,n;cout<<"n= "; cin>>n;creare (a,n);afisare(a,n);for ( i=1;i<=n;i++)
if(oglindit(a[i])!=0)cout<<"Numarul "<<a[i]<<" este palindrom"<<endl;return 0;}
# include <iostream>
# include <cmath>
using namespace std;
int prim (int x)
{ int nr_div=0;
for (int i=2; i<=sqrt(x); i++)
if (x%i==0) nr_div++;
if (nr_div==0) return(1);
else return(0);
}
int main ()
{ int N;
cout << "N="; cin >> N;
if (prim(N))
cout << "PRIM";
else
cout << "NU E PRIM";
return 0;
}
Functia prim este o functie cu
rezultat de tip int, care are un
singur parametru formal x, cel ce
reprezinta numarul de verificat.
Functia va returna valoarea 1
daca numarul x nu are divizori
proprii, deci este numar prim, sau
0 atunci cand numarul x are cel
putin un divizor propriu.
Functia este apelata din cadrul
unei expresii in instructiunea if.
Dupa executia functiei numele ei
va fi inlocuit de valoarea returnata.
int prim (int x)
{ int nr_div=0;
for (int i=2; i<=sqrt(x); i++)
if (x%i==0)
return 0 ;
return 1;
}
if(prim(N)!=0))
Se citesc 3 valori , sa se arate ca sunt in progresie aritmetica
PARAMETRI ACTUALI SI FORMALI
Parametri formali apar în antetul subprogramului şi
sunt utilizaţi de subprogram pentru descrierea
abstractă a unui proces de calcul .
Parametri actuali apar în instrucţiunea de apelare a
uni subprogram şi sunt folosiţi la execuţia unui proces
de calcul pentru valori concrete.
void schimba_valoare (int x, int y)
{ int aux=x; x = y; y = aux; }
int main ()
{ int M=1, N=5;
schimba_valoare(M,N);
cout << "M="<<M<< " " << "N="<<N<<endl;
return 0;
}
Parametrii formali nu sunt variabile. O
variabilă este caracterizată de nume,
tip, şi adresă. Legarea unui parametru
formal la o adresă se realizează în
timpul execuţiei instrucţiunii de apelare
a subprogramului.
//transmitere prin referinta//transmitere prin valoare
void schimba_referinta (int &a, int &b)
{ int aux=a; a=b; b=aux; }
int main ()
{ int M=1, N=5;
schimba_referinta(M,N);
cout << "M="<<M<< " " << "N="<<N<<endl;
#include<iostream.h> int test(int a=10, int b=20) {return a+b;} int main() {cout<<test(30,40)<<endl; //afişează 70 cout<<test(30)<<endl; //afişează 50 cout<<test(); //afişează 30
La apelul subprogramului, parametrilor formali li se atribuie valoarea parametrilor actuali.
Parametrii formali corespunzători parametrilor valoare pot fi iniţializaţi în antetul subprogramului.
Dacă lipseşte un parametru actual, parametrul formal va fi iniţializat cu valoarea din listă
Identificaţi următoarele componente
ale programului (indicaţi liniile unde
sunt folosite):
a) Variabile globale
b) Variabile locale
c) Parametri actuali şi modul de
transfer
d) Parametri formali şi modul de
transfer
e) Antetul funcţiei C
f) Apelul funcţiei C
g) Scrieţi prototipul funcţiei C
Ce afişează apelul func ţiei schimba(a,b) de la lin ia 15 pentru a=15 şi b=27 ?
Ce afişează apelul funcţiei test(a,b) de la linia 9 pentru a=27 şi b=45 ?
#include <iostream>
using namespace std;int test(int &a,int &b){while(a!=b)
if(a>b) a=a-b;else b=b-a;return a;
}int main(){int a=6, b=15;
cout << test(a,b) << " ";cout << a << " "<<b;return 0;
}
Identificaţi următoarele componente ale programului (indicaţi liniile unde sunt folosite): a) Variabile globale b) Variabile locale c) Parametri actuali şi modul de transfer d) Parametri formali şi modul de transfer e) Antetul funcţiei testf) Apelul funcţiei test
g) Scrieţi prototipul funcţiei test
https://drive.google.com/file/d/1z2Clb-6LGobQwhz-iyqanJmtbtv6U1w0/view
pentru suma cifrelor unui număr natural n esteurmătoarea:
int suma (int n)
{
return n%10+suma(n/10);
}
Funcţia este greşită pentru că nu tratează cazurileelementare. Ca urmare, recursia nu se opreşteniciodată.Pentru a calcula suma cifrelor, se elimină succesivtoate cifrele sale, până când n devine 0. Din acestmoment, se evaluează la infinit suma(0),deoarece 0/10 este permanent 0.
Recursivitate
int suma (int n){
if(n<=0) return 0;
return n%10+suma(n/10);}
Funcţia corectă ar fi fost:
Definiție
O funcție se numește recursivă dacă ea se autoapelează.Clasificare
Recursivitatea este de două tipuri: directă și indirectă.În cazul în care auto-apelul se realizează în cadrul aceleiași funcții, recursivitatea este directă (A->A).Atunci când auto-apelul se realizează prin intermediul altei funcții, recursivitatea este indirectă (A->B->...->A).
O funcţie greşită
Funcţie recursivă directă:int fact(int n)
{
if(n==1)
return 1;
return n*fact(n-1); //apel recursiv
}
int f(int a)
{
if(a%12==0)
return 0;
return f(a-1);
}
int f(int b)
{
if(b/2>2)
return b+f(b/2);
return b/2;
}
int f1(int d)
{
while (d%2==0)
return
++c+f2(d/2);
return 1;
}
int f2(int e)
{
if (e%2==0)
return f1(e);
return 0;
}
int f(int g)
{
if(x/3)>0;
return x/3;
return x*3;
}
int f(int c)
{
while(c>1)
return c+f(c-1);
return 1;
}
int f(int a)
{
if (a%3==0)
return 0;
return 1+f(a-1)
}
void f(int x, int &y)
{
if(x==y) cout<<x<<y;
else
{x++; y--; f(x,y); cout<<x<<y}
}
int f(int b, int c)
{
if(b>c)
if(b%c==0)
return f(b+b/c,c);
else
return 1+f(b+b%c,c);
return b;
}
int f(int x, int d)
{
while(x>0)
{
if(x==d)
return 1;
if(x%d==0)
return 1+ f(x/d, d+1)
return f(x-1, d);
}
return 0;
}
Matrici• Numim tablou o colecţie ( grup, mulţime ordonată ) de date • de acelaşi tip ,• situate într-o zona de memorie continuă ( elementele tabloului se află la adrese
succesive).
X[1][1] X[1][2] X[1][3] ……….. X[1] [m]
X[2][1] X[2][2] X[2][3] ………. X[2] [m]
X[3][1] X[3][2] X[3][3] ………… X[3] [m]
……….. …………. ………….. ………… ……………
X[n][1] X[n][2] X[n][3] ……… X[n][m]
matrici#include<iostream>using namespace std;int main (){int x[10][10], n, m, i, j;cout<<"Dati numarul de linii: "; cin>>n;cout<<"Dati numarul de coloane: "; cin>>m;cout<<"Introduceti elementele matricei: "<<endl;for (i=1; i<=n; i++) //parcurge liniilefor (j=1; j<=m; j++) //parcurge coloanele{cout<<"x["<<i<<"]["<<j<<"]="; //afiseaza ce locatie de memorie
cin>>x[i][j]; //memoreaza valoarea in locatie
}cout<<"Afisam matricea: "<<endl;for (i=1; i<=n; i++){for (j=1; j<=m; j++)
cout<<x[i][j]<<" "; // sa afiseze elementele din randul i
cout<<endl; // pentru a trece la randul i+1
}return 0;
}
Se citeste o matrice patratica. Sa se afiseze elementele de pe diagonala secundara, elementele de pe diagonala principala, elementele de sub/desupra diagonalei secundare/principala.
Este un caz particular de matrice pentru care numărul de linii este egal cu numărul de coloane.
Diagonala principală este formată din elementele care îndeplinesc relația i=j
Citeste matricea;Afiseaza elementele matricei;cout<<"Afisam elementele diagonalei principale: "<<endl;for (i=1; i<=n; i++)
{for (j=1; j<=m; j++)
if(i==j) cout<<x[i][j]<<" ";
cout<<endl;}
x11 x12 x13 X1….m
x21 x22 x23 X2…m
x31 x32 x33 X3…..m
xn1 xn2 xn3 xnm
Diagonala secundară conţine elementele caracterizate de relaţia i+j=n+1.
Citeste matricea;Afiseaza elementele matricei;cout<<"Afisam elementele diagonalei secundara: "<<endl;for (i=1; i<=n; i++)
{ for (j=1; j<=m; j++)
if(i+j==n+1) cout<<x[i][j]<<" ";
cout<<endl;}
x11 x12 x13 X1….m
x21 x22 x23 X2…m
x31 x32 x33 X3…..m
xn1 xn2 xn3 xnm
cout<<"Afisam elementele de deasupra diagonalei principale:"<<endl;for (i=0; i<n; i++){for (j=0; j<m; j++)
if(i<j)cout<<x[i][j]<<" ";
cout<<endl;}
Citeste matricea;Afiseaza elementele matricei;
x11 x12 x13 X1….m
x21 x22 x23 X2…m
x31 x32 x33 X3…..m
xn1 xn2 xn3 xnm
cout<<"Afisam elementele de sub diagonala principală : "<<endl;for (i=1; i<=n; i++){for (j=1; j<=m; j++)
if(i>j)cout<<x[i][j]<<" ";
cout<<endl;}
Citeste matricea;Afiseaza elementele matricei;
x11 x12 x13 X1….m
x21 x22 x23 X2…m
x31 x32 x33 X3…..m
xn1 xn2 xn3 xnm
