Bella: Blanked the page

2024-01-14T14:39:49Z

Blanked the page

Bella: /* Afisarea sumei divizorilor unui numar */

2020-10-08T15:24:52Z

Afisarea sumei divizorilor unui numar

New page

= 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>

10 2018 Lectia3 - Revision history

Bella: Blanked the page

Bella: /* Afisarea sumei divizorilor unui numar */