MyCodeSchool

Pasul 1 din 5

C++

Pasul 1 din 5 · Ce construiești

  • C++
  • BAC
  • 13 minute

while la bac: divizori, cmmdc și numere prime

Scrii un program care citește două numere și afișează cel mai mare divizor comun, cel mai mic multiplu comun și dacă sunt prime între ele.

cmmdc.cpp, în consolă
84 120
12 840
NU

Partea a doua a lecției despre while. Dacă n-ai lucrat încă pe cifrele unui număr, începe cu partea întâi, legată la final.

Pasul 2 din 5

Rulează-l linie cu linie

Algoritmul lui Euclid pe 48 și 18. Ideea: cmmdc(a, b) e același cu cmmdc(b, a % b), iar numerele scad repede.

euclid.cpp
#include <iostream>using namespace std;int main() {    int a, b;    cin >> a >> b;    while (b != 0) {        int r = a % b;        a = b;        b = r;    }    cout << a;    return 0;}

Variabile

Ce apare pe ecran


      

  1. Linia 5. Două variabile întregi, încă fără valoare.
  2. Linia 6. Se citesc 48 și 18, de pe același rând.
  3. Linia 7. 18 e diferit de 0, deci se intră în buclă.
  4. Linia 8. Restul lui 48 la 18 e 12. r e declarat în buclă și trăiește doar într-o tură.
  5. Linia 9. a ia locul lui b: 18.
  6. Linia 10. b ia restul: 12. Perechea (48, 18) a devenit (18, 12).
  7. Linia 7. 12 ≠ 0, încă o tură.
  8. Linia 8. 18 % 12 = 6.
  9. Linia 9. a devine 12.
  10. Linia 10. b devine 6. Perechea e (12, 6).
  11. Linia 7. 6 ≠ 0, încă o tură.
  12. Linia 8. 12 % 6 = 0: 6 îl împarte exact pe 12.
  13. Linia 9. a devine 6.
  14. Linia 10. b devine 0.
  15. Linia 7. b e 0, bucla se oprește. Rezultatul a rămas în a.
  16. Linia 12. Se afișează 6.
  17. Linia 13. main se încheie.
  18. Gata. Trei ture pentru 48 și 18. Prin scăderi repetate ar fi fost patru, iar diferența crește cu mărimea numerelor.

Prezice ieșirea

Rulezi programul cu 17 și 5. Ce afișează?

Răspuns: „1”.

Perechile sunt (17, 5), (5, 2), (2, 1), (1, 0). 17 e prim, iar 5 nu îl divide, deci singurul divizor comun e 1: numerele sunt prime între ele.

Pasul 3 din 5

Algoritmii cu divizori

Fragmentele stau în main. Toți folosesc același test: n % d == 0 înseamnă „d îl divide pe n”.

Toți divizorii

divizori.cpp
int n = 12, d = 1;while (d <= n) {    if (n % d == 0)        cout << d << ' ';    d++;}

Ce apare pe ecran

1 2 3 4 6 12 

d ia pe rând valorile de la 1 la n, iar if le păstrează doar pe cele care împart exact. Cu un contor în loc de cout, afli câți divizori are numărul.

E prim? Verifici până la radical

prim.cpp
int n = 91, d = 2;bool prim = n >= 2;while (d * d <= n && prim) {    if (n % d == 0)        prim = false;    d++;}cout << prim << ' ' << d - 1;

Ce apare pe ecran

0 7

Dacă n are un divizor mai mare decât radicalul, are și unul mai mic, perechea lui. Ajunge deci să încerci d cât timp d * d <= n. Pentru 91 = 7 · 13, bucla se oprește la 7.

Condiția && prim oprește căutarea la primul divizor găsit. prim pornește de la n >= 2, pentru că 0 și 1 nu sunt prime.

cmmdc prin scăderi

scaderi.cpp
int a = 48, b = 18;while (a != b) {    if (a > b)        a -= b;    else        b -= a;}cout << a;

Ce apare pe ecran

6

Varianta din manual: scazi mereu numărul mic din cel mare până devin egale. E ușor de urmărit pe hârtie, dar lentă când numerele sunt foarte diferite, de exemplu 1000000 și 1. Nu merge dacă unul dintre numere e 0.

cmmmc și long long

cmmmc.cpp
long long a = 120000, b = 70000;long long x = a, y = b;while (y != 0) {    long long r = x % y;    x = y;    y = r;}cout << x << ' ' << a * b / x;

Ce apare pe ecran

10000 840000

cmmmc(a, b) = a · b / cmmdc(a, b). Aici a · b = 8 400 000 000, peste limita unui int, de aproximativ 2,1 miliarde. long long merge până pe la 9 · 1018. Algoritmul lucrează pe copii, ca să-i rămână a și b pentru formulă.

Capcană: 1 iese prim

Dacă pornești cu prim = true, pentru n = 1 bucla nu rulează deloc: 2 · 2 > 1. Nimeni nu schimbă prim:

unu.cpp
#include <iostream>using namespace std;int main() {    int n = 1, d = 2;    bool prim = true;    while (d * d <= n && prim) {        if (n % d == 0)            prim = false;        d++;    }    cout << prim;    return 0;}

Ce apare pe ecran

1

Repară cu bool prim = n >= 2;. La bac, testele includ aproape sigur 0 și 1.

Capcană: afișezi variabila greșită

Bucla se oprește exact când b devine 0. Deci, după ea, b e mereu 0:

gresit.cpp
#include <iostream>using namespace std;int main() {    int a = 48, b = 18;    while (b != 0) {        int r = a % b;        a = b;        b = r;    }    cout << b;    return 0;}

Ce apare pe ecran

0

Repară cu cout << a;. Întreabă-te ce valoare are fiecare variabilă în clipa în care condiția devine falsă.

Pasul 4 din 5

Verifică-te

Cinci grile în stilul subiectului I. După fiecare răspuns vezi de ce e așa.

1 din 5 · Prezice ieșirea

Ce afișează programul?

scaderi.cpp
#include <iostream>using namespace std;int main() {    int a = 12, b = 8;    while (a != b) {        if (a > b)            a -= b;        else            b -= a;    }    cout << a;    return 0;}

Răspuns: „4”.

(12, 8) devine (4, 8), apoi (4, 4). Numerele sunt egale, bucla se oprește, iar cmmdc e 4.

2 din 5 · Prezice ieșirea

Ce afișează programul?

numara.cpp
#include <iostream>using namespace std;int main() {    int n = 36, d = 1, nr = 0;    while (d <= n) {        if (n % d == 0)            nr++;        d++;    }    cout << nr;    return 0;}

Răspuns: „9”.

Divizorii lui 36 sunt 1, 2, 3, 4, 6, 9, 12, 18, 36. Un pătrat perfect are mereu un număr impar de divizori: 6 e perechea lui însuși.

3 din 5 · Alege varianta

Ce condiție pui în while ca testul de număr prim să facă cât mai puține ture și să rămână corect?

Răspuns: d * d <= n.

Cu <, la n = 49 nu se mai încearcă 7, iar 49 ar ieși prim. n / 2 e corect doar dacă scrii <=, și oricum face mult mai multe ture.

4 din 5 · Prezice ieșirea

Ce afișează programul?

perfect.cpp
#include <iostream>using namespace std;int main() {    int n = 28, s = 0, d = 1;    while (d < n) {        if (n % d == 0)            s += d;        d++;    }    cout << s;    return 0;}

Răspuns: „28”.

Se adună divizorii mai mici decât 28: 1 + 2 + 4 + 7 + 14 = 28. Un număr egal cu suma divizorilor lui proprii se numește perfect.

5 din 5 · Prezice ieșirea

Ce afișează programul?

ture.cpp
#include <iostream>using namespace std;int main() {    int a = 10, b = 4, ture = 0;    while (b != 0) {        int r = a % b;        a = b;        b = r;        ture++;    }    cout << ture << ' ' << a;    return 0;}

Răspuns: „2 2”.

(10, 4) devine (4, 2), apoi (2, 0). Două ture, iar cmmdc e 2.

Pasul 5 din 5

Ce ai învățat

Programul complet

cmmdc cu Euclid, pe copii, apoi cmmmc. Împărțirea se face înainte de înmulțire, a / x * b, ca rezultatul intermediar să rămână mic. La final, DA dacă numerele sunt prime între ele.

cmmdc.cpp
#include <iostream>using namespace std;int main() {    long long a, b;    cin >> a >> b;    long long x = a, y = b;    while (y != 0) {        long long r = x % y;        x = y;        y = r;    }    cout << x << ' ' << a / x * b;    cout << '\n';    if (x == 1)        cout << "DA";    else        cout << "NU";    return 0;}

Cu 21 și 50

1 1050
DA

Cu 84 și 120

12 840
NU

Continuă cu