Ce vei învăța astăzi?
Vom învăța algoritmul lui Euclid pentru CMMDC și cum îl folosim pentru a simplifica fracții. Vom compara eficiența cu metoda naivă (for).
Dicționar: Matematică ↔ C++ (CMMDC)
| Concept matematic | Cum se citește | În C++ | Observație |
|---|---|---|---|
| a mod b (restul) | „a modulo b" | a % b | operatorul rest |
| CMMDC(a,b) | „cel mai mare div. comun" | cmmdc(a, b) | funcție definită de noi |
| CMMMC(a,b) | „cel mai mic multiplu comun" | a / cmmdc(a,b) * b | împărțim ÎNTÂI! |
| a | b (a divide b) | „a divide pe b" | b % a == 0 | restul = 0 → divide |
| a/CMMDC | „simplificarea fracției" | a / d (d = cmmdc) | salvează a,b originale! |
| min(a,b) | „minimul" | min(a,b) | <algorithm> |
Ce este CMMDC?
CMMDC (Cel Mai Mare Divisor Comun) a două numere naturale a și b este cel mai mare număr care le divide pe ambele exact.
Exemplu: CMMDC(12, 8) = 4 (4 divide atât 12 cât și 8)
Analogie: Plăci de pardoseală
Imaginează-ți o cameră de 12m × 8m. Vrei să o acoperi cu plăci pătrate cât mai mari posibil, fără tăiere. Latura plăcii = CMMDC(12, 8) = 4 metri. Vei avea 3×2 = 6 plăci.
Exercițiu mental: Găsește divizorii comuni
| Număr | Divizori |
|---|---|
| 12 | 1, 2, 3, 4, 6, 12 |
| 8 | 1, 2, 4, 8 |
| Comuni | 1, 2, 4 → CMMDC = 4 |
Aplicație principală: Simplificarea fracțiilor! Fracția 12/8 se simplifică împărțind ambele numere la CMMDC(12,8) = 4, obținând 3/2. CMMDC apare frecvent și în probleme de PbInfo.
Metoda 1: Algoritmul naiv (cu for)
Prima idee: parcurgem toate numerele de la min(a,b) spre 1 și returnăm primul care divide ambele.
int cmmdc_naiv(int a, int b) {
int minim = min(a, b);
for (int d = minim; d >= 1; d--) {
if (a % d == 0 && b % d == 0)
return d;
}
return 1;
}
// Pentru a=1000000 și b=999999, parcurge ~999999 pași!
Problemă: Dacă a și b sunt numere prime între ele (ex: 999999 și 1000000), metoda naivă parcurge TOATE numerele de la min(a,b) la 1 înainte să găsească 1. Extrem de lent!
Metoda 2: Algoritmul lui Euclid
Principiu matematic: CMMDC(a, b) = CMMDC(b, a % b). Repetăm până b devine 0. Rezultatul este a.
De ce funcționează?
Dacă d divide atât pe a cât și pe b, atunci d divide și pe (a - b), și pe (a % b). Deci toți divizorii comuni se păstrează când înlocuim (a, b) cu (b, a%b). La final, când b=0, toți acei divizori se regăsesc în a.
Exemplu pas cu pas: CMMDC(48, 18)
| Pas | a | b | C++: a%b | Acțiune |
|---|---|---|---|---|
| 1 | 48 | 18 | 48%18 = 12 | a←18, b←12 |
| 2 | 18 | 12 | 18%12 = 6 | a←12, b←6 |
| 3 | 12 | 6 | 12%6 = 0 | a←6, b←0 |
| 4 | 6 | 0 | STOP | CMMDC = 6 |
Doar 3 pași față de 18 pași la metoda naivă!
Alt exemplu: CMMDC(270, 192)
| Pas | a | b | C++: a%b |
|---|---|---|---|
| 1 | 270 | 192 | 270%192 = 78 |
| 2 | 192 | 78 | 192%78 = 36 |
| 3 | 78 | 36 | 78%36 = 6 |
| 4 | 36 | 6 | 36%6 = 0 |
| 5 | 6 | 0 | STOP → CMMDC = 6 |
Doar 4 pași! Metoda naivă ar fi făcut 192 de pași.
Implementare C++: Euclid iterativ
Pseudocodul algoritmului Euclid:
#include <iostream>
using namespace std;
int main() {
int a, b;
cout << "Introdu doua numere: ";
cin >> a >> b;
int x = a, y = b; // copiem valorile originale
// Algoritmul lui Euclid
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
// acum a = CMMDC
cout << "CMMDC(" << x << ", " << y << ") = " << a << endl;
cout << "Fractia simplificata: " << x/a << "/" << y/a << endl;
return 0;
}
Greșeală frecventă: Uiți să salvezi valorile originale! După while, variabilele a și b s-au schimbat. Dacă vrei să afișezi fracția simplificată, ai nevoie de valorile inițiale (x și y).
Implementare C++: Euclid recursiv
Varianta recursivă este foarte elegantă — o singură linie de cod!
#include <iostream>
using namespace std;
int cmmdc(int a, int b) {
if (b == 0) return a;
return cmmdc(b, a % b);
}
// Varianta scurtă (ternary operator):
// int cmmdc(int a, int b) { return b == 0 ? a : cmmdc(b, a%b); }
int main() {
int a, b;
cin >> a >> b;
int d = cmmdc(a, b);
cout << "CMMDC = " << d << endl;
cout << "Simplificat: " << a/d << "/" << b/d << endl;
return 0;
}
Iterativ vs. Recursiv: Ambele dau același rezultat. Varianta iterativă este ușor mai eficientă (fără overhead de apeluri de funcție). Varianta recursivă este mai elegantă și mai ușor de citit.
CMMMC - Cel Mai Mic Multiplu Comun
Formula: CMMMC(a, b) = a × b / CMMDC(a, b)
Atenție la overflow: Calculăm a / CMMDC(a,b) * b (împărțim întâi!) pentru a evita depășirea.
Exemplu: CMMMC(12, 8)
CMMDC(12, 8) = 4
CMMMC = 12 / 4 × 8 = 3 × 8 = 24
Verificare: 24 este multiplu al lui 12 (24=12×2) și al lui 8 (24=8×3) ✓
int cmmdc(int a, int b) {
while (b != 0) { int r = a % b; a = b; b = r; }
return a;
}
int cmmmc(int a, int b) {
return a / cmmdc(a, b) * b; // imparte INTAI!
}
// Exemplu de utilizare:
// cmmmc(12, 8) = 12 / 4 * 8 = 24
Cazuri speciale
| Caz | Rezultat | Explicație |
|---|---|---|
| CMMDC(n, 0) | n | Orice număr divide 0 |
| CMMDC(0, 0) | 0 (nedefinit) | Convenție matematică |
| CMMDC(n, n) | n | n % n = 0, deci CMMDC = n |
| CMMDC(n, 1) | 1 | 1 divide totul |
| CMMDC(a, b) = 1 | Prime între ele | Fracția este deja ireductibilă |
Atenție în cod: Dacă numitorul este 0, programul ar face împărțire la 0! Întotdeauna verifică dacă numitorul != 0 înainte de a simplifica fracția.
Comparația eficienței
| Caracteristică | Metoda naivă (for) | Algoritmul Euclid |
|---|---|---|
| Nr. pași (a=48, b=18) | 18 pași | 3 pași |
| Nr. pași (a=1000000, b=999999) | ~999999 pași | ~20 pași |
| Nr. pași (a=270, b=192) | 192 pași | 4 pași |
| Complexitate | O(min(a,b)) | O(log(min(a,b))) |
| Rapiditate numere mari | Foarte lent | Foarte rapid |
| Ușurință implementare | Simplă | Simplă |
Lecția importantă (Competența 4.2): Doi algoritmi pot rezolva aceeași problemă, dar cu eficiențe foarte diferite. Algoritmul Euclid este demonstrabil mai rapid — e unul dintre cei mai vechi și mai eficienți algoritmi din istorie (300 î.Hr.)!
Verificare cunoștințe
1. CMMDC(24, 36) = ?
2. Câți pași face Euclid pentru CMMDC(100, 25)?
3. Fracția 60/45 simplificată este:
4. CMMDC(17, 13) = ? (ambele prime)
5. Care formulă calculează CMMMC corect în C++?
6. Ce returnează CMMDC(0, 15)?
Întrebări frecvente (FAQ)
La fiecare pas, restul (a%b) este mai mic decât b, iar b se micșorează de cel puțin 2 ori la fiecare 2 pași. Aceasta înseamnă că nr. de pași este proporțional cu log₂(min(a,b)). Pentru 1.000.000, asta înseamnă ~20 pași vs. ~1.000.000 la metoda naivă.
Da, dar trebuie să lucrezi cu valori absolute: CMMDC(|a|, |b|). În C++, operatorul % poate returna valori negative pentru numere negative, ceea ce poate cauza probleme. Cel mai simplu: convertește la pozitiv la început.
Când CMMDC(numărător, numitor) = 1, fracția este deja ireductibilă. Exemplu: 3/7 — CMMDC(3,7)=1, deci nu se mai poate simplifica. Două numere cu CMMDC=1 se numesc prime între ele (coprime).
Aplicăm CMMDC pe rând: CMMDC(a, b, c) = CMMDC(CMMDC(a, b), c). Exemplu: CMMDC(12, 8, 6) = CMMDC(CMMDC(12,8), 6) = CMMDC(4, 6) = 2.
PbInfo - CMMDC Euclid
Resturi succesive
Enunț:
Cerință: Se citesc doua numere naturale. Afiseaza CMMDC-ul lor folosind algoritmul lui Euclid.
Date de intrare:
a b.
Date de ieșire:
CMMDC(a,b).
Exemplu:
Intrare:
24 18
Ieșire:
6
Explicație: CMMDC este 6.
Cum gândim soluția:
- Cat timp b nu este 0, calculam restul.
- Inlocuim a cu b si b cu restul.
- Cand b devine 0, a este CMMDC.
Tip: Algoritmul lui Euclid este eficient pentru numere mari.
Scrie soluția în C++:
Soluție corectă:
#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;
}
PbInfo - Fractie ireductibila
Simplificare cu CMMDC
Enunț:
Cerință: Se citesc numaratorul si numitorul unei fractii. Afiseaza fractia simplificata.
Date de intrare:
a b.
Date de ieșire:
Fractia simplificata.
Exemplu:
Intrare:
18 24
Ieșire:
3/4
Explicație: Impartim 18 si 24 la 6.
Cum gândim soluția:
- Calculam CMMDC(a,b).
- Impartim a si b la CMMDC.
- Afisam a/b.
Tip: Pastreaza numitorul nenul.
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int cmmdc(int a, int b) {
while (b) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
int a, b;
cin >> a >> b;
int d = cmmdc(a, b);
cout << a / d << "/" << b / d;
}
PbInfo - Metoda eficienta
Euclid vs for
Enunț:
Cerință: Se citesc a si b. Afiseaza CMMDC si numarul de pasi facuti de Euclid.
Date de intrare:
a b.
Date de ieșire:
CMMDC si pasi.
Exemplu:
Intrare:
48 18
Ieșire:
6 3
Explicație: Euclid ajunge rapid la rezultat.
Cum gândim soluția:
- Initializam pasi=0.
- La fiecare rest calculat crestem pasi.
- La final afisam a si pasi.
Tip: Este o problema buna pentru competenta 4.2.
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int a, b, pasi = 0;
cin >> a >> b;
while (b != 0) {
int r = a % b;
a = b;
b = r;
pasi++;
}
cout << a << " " << pasi;
}
Exercițiul Practic: Simplificarea fracțiilor
Aplică algoritmul lui Euclid pentru simplificarea fracțiilor, CMMDC și CMMMC. Poți folosi funcții sau poți scrie algoritmul direct în fiecare exercițiu, dacă păstrezi pașii clari.
Observație importantă: algoritmul lui Euclid modifică valorile variabilelor. Dacă mai ai nevoie de numerele inițiale pentru afișare, simplificare sau CMMMC, salvează copii înainte de while. Copiile pot fi numite x, y sau mai clar a_initial, b_initial.
Sarcina 1: Simplificarea a n fracții
Citește n fracții (numărător/numitor) și afișează fiecare fracție simplificată. Poți face o funcție cmmdc sau poți scrie Euclid în interiorul buclei for.
Pași de rezolvare:
- Citește n (numărul de fracții)
- Pentru fiecare fracție: citește numărător (a) și numitor (b)
- Calculează CMMDC(a, b) cu Euclid
- Afișează
a/CMMDC/b/CMMDC
De ce funcționează? O fracție simplificată = numărător și numitor împărțite la cel mai mare divizor comun. Exemplu: 12/18 → CMMDC(12,18)=6 → 2/3. Algoritmul Euclid găsește CMMDC în O(log n) pași — mult mai rapid decât testarea tuturor divisorilor!
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
int a, b;
cin >> a >> b;
// Copii ale valorilor originale - Euclid modifica valorile!
int x = a, y = b;
// Algoritmul lui Euclid: restul repetat
while(y != 0){ int r = x % y; x = y; y = r; }
// Acum x = CMMDC(a, b)
// Simplificam: imparte AMBII la CMMDC
cout << a/x << "/" << b/x << endl;
}
return 0;
}
Sarcina 2: CMMMC (Cel Mai Mic Multiplu Comun)
Citește două numere a și b. Calculează și afișează CMMDC și CMMMC folosind formula CMMMC = a / CMMDC * b. Pentru numere mai mari, folosește long long.
Pași de rezolvare:
- Citește a și b, salvează copii (Euclid modifică valorile!)
- Calculează CMMDC cu Euclid
- Formula:
CMMMC = a / CMMDC * b— împarte ÎNTÂI (evită overflow)
De ce funcționează? CMMMC = cel mai mic multiplu comun. Formula: CMMMC = a·b/CMMDC. Dar dacă scriem a*b/cmmdc, produsul a*b poate depăși limita int (~2 miliarde). Scriind a/cmmdc*b împărțim ÎNTÂI — rezultatul parțial e mic, apoi înmulțim. În soluție salvăm CMMDC-ul în d, deci formula devine x/d*y. Exemplu: CMMMC(12,18) = 12/6*18 = 2*18 = 36.
#include <iostream>
using namespace std;
int main(){
long long a, b, x, y;
cin >> a >> b;
x = a; y = b; // salvam copii (Euclid modifica a si b!)
// Algoritmul Euclid
while(b != 0){ long long r = a % b; a = b; b = r; }
// Acum a = CMMDC(x, y). Il salvam in d ca formula sa fie usor de citit.
long long d = a;
cout << "CMMDC = " << d << endl;
// CMMMC = x * y / CMMDC, dar impartim INTAI pt a evita overflow
cout << "CMMMC = " << x / d * y << endl;
return 0;
}