10 2018 Lectia3

Subprograme

Studiu de caz - modularizarea unui program

De ce avem nevoie de subprograme

1. 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;
2. 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).
3. 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.

#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;
}

• 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

#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;
}

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:

#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;
}

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

#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;
}

Calculul cmmdc-ului

#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;
}

Rezolvati in clasa:

• problema plaja2
• Scrieti un program similar care sa calculeze cmmmc-ul a doua numere

Calculul cmmmc-ului

• Plaja1 Problema se reduce la a calcula cmmmc a n numere.

#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;
}

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

#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;
}

Scrieti in clasa un program similar care utilizeaza un subprogram pentru afisarea divizorilor

Folosind functii:

#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;
}

Afisarea sumei divizorilor unui numar

#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;
}

Descompunerea in factori primi

#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;
}

Primalitate

#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;
}

Cu functii:

#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;
}

Aplicatie: Afisarea tuturor numerelor prime dintr-un sir de n valori

#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;
}

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.

#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;
}

Sortarea a unui sir de n numere

#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;
}

Interclasare vectori

#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;
}