Question

Două numere a și b sunt numite generatoare ale unui număr natural n dacă a∙b+[a/b]=n, unde s-a notat
cu [c] partea întreagă a numărului real c.
Subprogramul generatoare are un singur parametru, n, prin care primește un număr natural
(n[2,109]). Subprogramul afișează pe ecran toate perechile distincte de numere naturale cu proprietatea
că sunt generatoare ale lui n și că primul număr din pereche este par. Numerele din fiecare pereche sunt
separate prin simbolul minus (-), iar perechile sunt separate prin câte un spațiu. Dacă nu există astfel de
perechi, se afișează pe ecran mesajul nu exista. Scrieți definiția completă a subprogramului.
Exemplu: dacă n=2020 se afișează pe ecran
2-1010 4-505 10-202 20-101 96-21 200-10 606-3 808-2 1010-1

Answer 1

Răspuns:

void generatoare( int n ) {

   int a, b;

   for ( a = 2; a <= n; a += 2 ) {

       b = 1;

       while ( a * b + a / b < n )

           b ++;

       if ( a * b + a / b == n )

           cout << a << '-' << b << ' ';

   }

}

Explicație:

Complexitate:

Daca luam expresia a * b + a / b si luam doar prima parte, a * b care este mai mica decat expresia noastra, atunci:

pentru un singur a, forul pentru b se va executa de n/a ori, deci complexitatea devine o suma de genul n/2 + n/4 + n/6 + n/8 +... n/n

Dând factor comun pe n/2 suma o sa fie:

n/2( 1 + 1/2 + 1/3 + 1/4 + ... 1/n ), care suma asta este o suma faimoasa si tinde la ln( n ), complexitatea ajungand la n * ln(n) nu n^2

Explicatie program:

primul for, cel pentru 'a' ia fiecare numar posibil pe care il poate lua a

al doilea for, cunoscand 'a', testeaza daca exista un b a.i. expresia sa fie adevarata

Ultimul if testeaza si afiseaza perechea daca expresia este adevarata