|
|
| Line 1: |
Line 1: |
| = Subprograme =
| |
| == Studiu de caz - modularizarea unui program ==
| |
| === De ce avem nevoie de subprograme ===
| |
| # pentru a evita scrierea de cod repetitiv; definirea unui subprogram ne permite executarea acestuia de mai multe ori, fara a scrie acelasi cod de in mod repetat;
| |
| # decompunerea problemei in subprobleme - facem asta deoarece subproblemele sunt parti de cod mai simplu de scris, de testat, de verificat si de inteles (in en: decomposition- medoda de a imparti problema in subprobleme).
| |
| # Modularizarea usureaza munca in echipa
| |
| Esista 2 modalitati de descompunere:
| |
| * top-down - when you try to define the most general functions first and then you divide them into simpler and more specialized ones)
| |
| * bottom up - when you start your work by creating a set of narrowly defined and highly specialized functions, and then assembling them into more complex structures
| |
|
| |
|
| == Tipuri de subprograme ==
| |
| Clasificare dupa autor
| |
| * '''Functii predefinite''' sau functii de biblioteca - sunt functii scrise de altcineva disponibile in bibliotecile mediului de programare
| |
| ** ex1: in biblioteca cmath gasim functia '''abs''' care calculeaza val absoluta a numar, functia sqrt care calculeaza radicalul unui numar, etc
| |
| ** ex2: in biblioteca cstring casim functii care prelucreaza siruri de caractere precum functia '''strlen''' care calculeaza lungimea unui sir, etc.
| |
| * '''Functii definite de utilizator''' - functii pe care le putem defini si utiliza in programul nostru
| |
|
| |
| Subprogramele pot fi de două tipuri:
| |
|
| |
| * '''funcții''' – subprograme care determină un anumit rezultat, o anumită valoare, pornind de la anumite date de intrare. Spunem că valoarea este returnată de către funcție, iar aceasta va fi apelată ca operand într-o expresie, valoarea operandului în expresie fiind de fapt valoarea rezultatului funcției.
| |
| <syntaxhighlight>
| |
| #include <iostream>
| |
|
| |
| using namespace std;
| |
| int catecifre( int n ){
| |
| int cnt = 0;
| |
| while ( n ){
| |
| cnt ++;
| |
| n/=10;
| |
| }
| |
| return cnt;
| |
| }
| |
|
| |
| int main(){
| |
| int e = 2034;
| |
| cout << catecifre ( e );
| |
| return 0;
| |
| }</syntaxhighlight>
| |
| * '''proceduri''' – subprograme care se folosesc într-o instrucțiune de sine stătătoare, nu într-o expresie. Ele îndeplinesc o sarcină, au un efect și nu returnează un rezultat. De exemplu, citirea unor variabile, afișarea unor valori, transformarea unor date, etc.
| |
| Ex: Afisare primelor n numere naturale impare
| |
| <syntaxhighlight>
| |
| #include <iostream>
| |
|
| |
| using namespace std;
| |
|
| |
| void afisare( int n ){
| |
| int i = 1;
| |
| while ( i <= n ){
| |
| cout << 2 * i - 1 << " ";
| |
| i ++;
| |
| }
| |
| }
| |
|
| |
| int main(){
| |
| int main(){
| |
| int n = 5;
| |
| afisare( n );
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| == Transmiterea parametrilor ==
| |
| * prin valoare
| |
| * prin referinta (diferenta dintre c/c++)
| |
|
| |
| == Aplicatii subprograme ==
| |
| In acest laboator ne propunem sa recapitulam algoritimi studiati in anul anterior si totodata sa ii implementam sub forma de subprograme. Vom recapitula:
| |
| * algoritmilor elementari
| |
| ** Prelucrarea cifrelor unui numar (numar palindrom)
| |
| ** Algoritmi de divizibilitate ( cmmdc, cmmmc, primalitate, descompunere in factori primi
| |
| ==== Numere palindrom ====
| |
| Algoritmul clasic verifică dacă numărul este egal cu răsturnatul său:
| |
| Avem şi o metodă mai apropiată de cea originală, în care răsturnăm numărul numai pînă la jumate:
| |
| <syntaxhighlight>#include<stdio.h>
| |
|
| |
| int main(){
| |
| long long n, r;
| |
| scanf("%lld", &n );
| |
|
| |
| if ( n > 0 && n % 10 == 0 )
| |
| printf("NU\n");
| |
| else {
| |
| r = 0;
| |
| while( n > r ){
| |
| r = r * 10 + n % 10;
| |
| n = n / 10;
| |
| }
| |
| // cand numarul are un numar par de cifre testam daca p == r
| |
| // cand numarul are un numar impar de cifre testam daca p == r / 10
| |
| if( n == r || n ==(r /10))
| |
| printf("DA\n");
| |
| else
| |
| printf("NU\n");
| |
| }
| |
| return 0;
| |
| }</syntaxhighlight>
| |
| Metoda: Rasturnam numarul pana la jumatate; Cum obtinem cele 2 jumatati?
| |
| Vom muta in r cifre din n pana cand r devine mai mare ca n. Atentie la numerele cu zerouri la coada. Ex: 5500
| |
|
| |
| <syntaxhighlight>
| |
| #include <stdlib.h>
| |
| #include <stdlib.h>
| |
| int pali( long long n ){
| |
| int r;
| |
| if ( n > 0 && n % 10 == 0 )
| |
| return 0;
| |
| r = 0;
| |
| while ( n> r ) {
| |
| r = r * 10 + n % 10;
| |
| n = n / 10;
| |
| }
| |
| if ( n == r || n == ( r / 10 ) )
| |
| return 1;
| |
| return 0;
| |
| }
| |
| int main(){
| |
| long long n;
| |
| scanf( "%lld", &n );
| |
| if( pali(n) )
| |
| printf( "este palindrom" );
| |
| else
| |
| printf( "nu este palindrom" );
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
| ===Calculul cmmdc-ului===
| |
| <syntaxhighlight>
| |
| #include <stdio.h>
| |
| unsigned int cmmdc( unsigned int a, unsigned int b ){
| |
| unsigned int r;
| |
| while ( b > 0 ){
| |
| r = a % b;
| |
| a = b;
| |
| b = r;
| |
| }
| |
| return a;
| |
| }
| |
| int main() {
| |
| unsigned int a, b;
| |
| scanf( "%d%d", &a, &b );
| |
| printf( "%u", cmmdc( a, b ) );
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| Rezolvati in clasa:
| |
| * problema [http://varena.ro/problema/plaja2 plaja2]
| |
| * Scrieti un program similar care sa calculeze cmmmc-ul a doua numere
| |
|
| |
| ===Calculul cmmmc-ului===
| |
| *[http://varena.ro/problema/plaja1 Plaja1] Problema se reduce la a calcula cmmmc a n numere.
| |
| <syntaxhighlight>
| |
| #include<fstream>
| |
| using namespace std;
| |
| //prototipurile functilor pe care le vom defini.
| |
| int cmmdc(int ,int );
| |
| int cmmmc(int ,int );
| |
| //definirea functiilor anuntate prin prototipuri
| |
| int cmmdc(int a,int b){
| |
| int r;
| |
| while(b>0){
| |
| r=a%b;
| |
| a=b;
| |
| b=r;
| |
| }
| |
| return a;
| |
| }
| |
| int cmmmc(int a,int b){
| |
| return (a*b)/cmmdc(a,b);
| |
| }
| |
| int main(){
| |
| ifstream f("plaja1.in");
| |
| ofstream g("plaja1.out");
| |
| int n,i,x,y;
| |
| f>>n;
| |
| f>>x; //citim o prima valoare din sir
| |
| for(i=2;i<=n;i++){
| |
| f>>y; //citim o noua valoare din sir
| |
| x=cmmmc(x,y); //x va fi rescris cu valoarea cmmmc-ului dinte x si y.
| |
| }
| |
| g<<x;
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| De retinut ca x si y sunt parametrii transmisi prin valoare, ca urmare functia cmmmc nu va putea modifica valoarea acestora.
| |
|
| |
| ==== Afisarea tuturor divizorilor unui numar ====
| |
| Se citeste un numar natural n. Sa se afiseze toti divizorii acestuia in ordine crescatoare:
| |
| Ex: pentru n = 12 se vor afisa: 1 2 3 4 6 12
| |
|
| |
| <syntaxhighlight>
| |
| #include <iostream>
| |
| #include <cmath>
| |
| using namespace std;
| |
| int main(){
| |
| int n, d;
| |
|
| |
| cin >> n;
| |
| // afisam mai intai divizorii de pana in radical
| |
| // vom parcurge deci sqrt(n) numere
| |
| d = 1;
| |
| while( d * d < n ){
| |
| if( n % d == 0 )
| |
| cout << d << '\n';
| |
| d = d + 1;
| |
| }
| |
| // afisam divizorii de dupa radical
| |
| // parcurgem divizorii de pana in radical in ordine inversa
| |
| // si afisam perechea fiecaruia de dupa radical
| |
| // vom parcurge deci tot sqrt(n) numere
| |
| d = sqrt (n);
| |
| while( d >= 1 ){
| |
| if( n % d == 0 )
| |
| cout << n / d << '\n';
| |
| d = d - 1;
| |
| }
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| Scrieti in clasa un program similar care utilizeaza un subprogram pentru afisarea divizorilor
| |
|
| |
| Folosind functii:
| |
| <syntaxhighlight>#include <iostream>
| |
| #include <cmath>
| |
| using namespace std;
| |
| void afisare_divizori ( int n ){
| |
| // afisam mai intai divizorii de pana in radical
| |
| // vom parcurge deci sqrt(n) numere
| |
| int d = 1;
| |
| while( d * d < n ){
| |
| if( n % d == 0 )
| |
| cout << d <<' ';
| |
| d = d + 1;
| |
| }
| |
| // afisam divizorii de dupa radical
| |
| // parcurgem divizorii de pana in radical in ordine inversa
| |
| // si afisam perechea fiecaruia de dupa radical
| |
| // vom parcurge deci tot sqrt(n) numere
| |
| d = sqrt ( n );
| |
| while( d >= 1 ){
| |
| if( n % d == 0 )
| |
| cout << n / d << ' ';
| |
| d = d - 1;
| |
| }
| |
| }
| |
| int main(){
| |
| int n;
| |
|
| |
| cin >> n;
| |
| afisare_divizori (n);
| |
|
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
| ==== Afisarea sumei divizorilor unui numar ====
| |
| <syntaxhighlight>#include <stdio.h>
| |
| int suma_div(int n){
| |
| int d, s;
| |
| s = n+1;
| |
| d=2;
| |
| while ( d * d < n ) {
| |
| if ( n % d == 0 )
| |
| s = s + d + n / d;
| |
| d = d + 1;
| |
| }
| |
| if( d * d == n)
| |
| s = s + d;
| |
| return s;
| |
| }
| |
| int main() {
| |
| int n;
| |
| scanf( "%d", &n );
| |
| printf( "Suma Divizorilor lui %d este: %d", n, suma_div(n) );
| |
| return 0;
| |
| }</syntaxhighlight>
| |
|
| |
| ==== Descompunerea in factori primi ====
| |
| <syntaxhighlight>#include<stdio.h>
| |
|
| |
| int main(){
| |
| int n, div, exp;
| |
|
| |
| scanf("%d",&n);
| |
| div = 2; //Incepem cautarea factorilor primi de la primul numar prim
| |
| while( div * div <= n ){//Cautam factorii primi pana la radicalul lui n
| |
| exp = 0;
| |
| while( n % div == 0 ) {
| |
| n /= div;
| |
| exp ++;
| |
| }
| |
| if( exp > 0 )
| |
| printf("%d^%d\n", div, exp );
| |
| div ++;
| |
| }
| |
| // daca n mai contine un factor, el este un numar prim la puterea unu
| |
| if( n > 1 )
| |
| printf("%d^1\n", n );
| |
|
| |
| return 0;
| |
| }</syntaxhighlight>
| |
| <syntaxhighlight></syntaxhighlight>
| |
|
| |
| ==== Primalitate ====
| |
| <syntaxhighlight>#include <stdio.h>
| |
| int main() {
| |
| int n, d;
| |
| scanf( "%d", &n );
| |
| d = 2;
| |
| while ( d*d <= n && n % d > 0 )
| |
| d = d + 1;
| |
| if ( d*d > n )
| |
| printf( "%d este prim\n", n );
| |
| else
| |
| printf( "%d nu este prim\n", n );
| |
| return 0;
| |
| }</syntaxhighlight>
| |
| Cu functii:
| |
| <syntaxhighlight>#include <stdio.h>
| |
| int prim ( int n ) {
| |
| int d;
| |
| d = 2;
| |
| while ( d * d <= n && n % d > 0 )
| |
| d = d + 1;
| |
| if ( d * d > n )
| |
| return 1;
| |
| else
| |
| return 0;
| |
| }
| |
| int main() {
| |
| int n;
| |
| scanf( "%d", &n );
| |
| if(prim(n))
| |
| printf( "%d este prim\n", n );
| |
| else
| |
| printf( "%d nu este prim\n", n );
| |
| return 0;
| |
| }</syntaxhighlight>
| |
|
| |
| Aplicatie: Afisarea tuturor numerelor prime dintr-un sir de n valori
| |
| <syntaxhighlight>
| |
| #include <stdio.h>
| |
| int prim (int n){
| |
| int d;
| |
| d = 2;
| |
| while ( d * d <= n && n % d > 0 )
| |
| d = d + 1;
| |
| if ( d * d > n )
| |
| return 1;
| |
| else
| |
| return 0;
| |
| }
| |
| int main() {
| |
| int n, i, nr, contor;
| |
| scanf( "%d", &n );
| |
| contor=0;
| |
| for( i = 0; i < n; i++ ){
| |
| scanf( "%d", &nr );
| |
| if(prim(nr) == 1)
| |
| contor++;
| |
| }
| |
| if(contor != 0)
| |
| printf( "in sir sunt %d numere prime\n", contor );
| |
| else
| |
| printf( "in sir nu sunt numere prime\n" );
| |
| return 0;
| |
| }</syntaxhighlight>
| |
|
| |
| ==== Ciurul lui Eratostene ====
| |
| O metoda mai rapida de a rezolva problema de mai sus ar fi sa contruim un tablou unidimensional in care sa memoram pentru fiecare numar, daca este prim sau nu.
| |
| <syntaxhighlight>#include <stdio.h>
| |
| char ciur[2000000];
| |
| void creare_ciur ( int n ){
| |
| int d, i;
| |
| for ( d = 2; d * d <= n; d ++ )
| |
| if ( ciur[d] == 0 ) // daca d este prim
| |
| for ( i = d * d; i <= n; i = i + d ) // vom marca numerele din d in d
| |
| ciur[i] = 1;
| |
| }
| |
| int main() {
| |
| int n, i;
| |
| scanf( "%d", &n );
| |
| creare_ciur(n);
| |
| for( i = 2; i <= n; i++ )
| |
| if( ciur[i] == 0 )
| |
| printf( " %d ", ciur[i] );
| |
| return 0;
| |
| }</syntaxhighlight>
| |
| ==== Sortarea a unui sir de n numere ====
| |
| <syntaxhighlight>
| |
|
| |
| #include <iostream>
| |
|
| |
| using namespace std;
| |
| void citire( int v[], int &n ){
| |
| int i;
| |
| cin >> n;
| |
| i = 0;
| |
| while ( i< n ){
| |
| cin >> v[i];
| |
| i++;
| |
| }
| |
| }
| |
| void afisare( int v[], int n ){
| |
| int i;
| |
| i = 0;
| |
| while ( i < n ){
| |
| cout << v[i] << " ";
| |
| i++;
| |
| }
| |
| }
| |
|
| |
| void myswap ( int &a, int &b ){
| |
| int aux = a;
| |
| a = b;
| |
| b = aux;
| |
| }
| |
| void sortare( int v[], int n ){
| |
| int i, j;
| |
| for ( i = 0; i < n - 1; i ++ )
| |
| for ( j = i + 1; j < n; j ++ )
| |
| if ( v[i] > v[j] )
| |
| myswap( v[i], v[j] );
| |
| }
| |
| int main(){
| |
| int a[100], n;
| |
| citire( a, n );
| |
| sortare ( a, n );
| |
| afisare( a, n );
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| ==== Interclasare vectori ====
| |
| <syntaxhighlight>#include <stdio.h>
| |
| #include <stdlib.h>
| |
| void citire(FILE *f, int v[], int *n){
| |
| int i;
| |
| fscanf( f, "%d", &n );
| |
| for ( i = 0; i < (*n); i++ )
| |
| fscanf( f, "%d", &v[i] );
| |
| }
| |
| void scrie( FILE *f, int v[], int n ) {
| |
| int i;
| |
| for ( i = 0; i < n; i++ )
| |
| fprintf( f, "%d ", v[i] );
| |
| fprintf( f, "\n" );
| |
| }
| |
| void interclasare(int v1[], int n1, int v2[], int n2, int v3[], int *n3 ){
| |
| int i1, i2, i3;
| |
| i1 = i2 = i3 = 0;
| |
| while ( i1 < n1 && i2 < n2 )
| |
| if ( v1[i1] < v2[i2] )
| |
| v3[i3++] = v1[i1++];
| |
| else
| |
| v3[i3++] = v2[i2++];
| |
|
| |
| while ( i1 < n1 )
| |
| v3[i3++] = v1[i1++];
| |
|
| |
| while ( i2 < n2 )
| |
| v3[i3++] = v2[i2++];
| |
|
| |
| *n3 = n1 + n2;
| |
| }
| |
|
| |
| int main(){
| |
| int a[100], b[100], c[100], na, nb, nc;
| |
| FILE *fin =fopen( "interclasare.in","r" );
| |
| citire(fin, a, &na);
| |
| citire(fin, b, &nb);
| |
| FILE *fout = fopen ("interclasare.out", "w");
| |
| fclose( fin );
| |
| interclasare( a, na, b, nb, c, &nc );
| |
| fout = fopen( "interclasare.out", "w" );
| |
| scrie( fout, c, nc);
| |
| fclose( fout );
| |
| return 0;
| |
| }</syntaxhighlight>
| |
|
| |
| <syntaxhighlight></syntaxhighlight>
| |
