Ce vei învăța astăzi?
După această lecție vei implementa algoritmul lui Euclid recursiv pentru calculul celui mai mare divizor comun (CMMDC) și vei folosi CMMDC în probleme practice precum fracțiile ireductibile.
Algoritmul lui Euclid
Definiție: CMMDC a două numere naturale este cel mai mare număr care le divide pe amândouă. Algoritmul lui Euclid se bazează pe proprietatea: cmmdc(a, b) = cmmdc(b, a % b) (unde a % b este restul împărțirii lui a la b), iar când b devine 0, rezultatul este a.
Forma recursivă: cmmdc(a, b) = b == 0 ? a : cmmdc(b, a % b).
Urmărirea pentru cmmdc(48, 18)
Funcția CMMDC recursivă în C++
#include <iostream>
using namespace std;
int cmmdc(int a, int b)
{
if (b == 0)
return a;
return cmmdc(b, a % b);
}
int main()
{
int a, b;
cout << "a b = ";
cin >> a >> b;
cout << cmmdc(a, b);
return 0;
}
Observă: funcția este foarte scurtă și elegantă; fiecare apel reduce rapid valorile, deoarece restul este întotdeauna mai mic decât împărțitorul.
Aplicație: fracții ireductibile
Simplificarea unei fracții
O fracție a/b se simplifică împărțind atât numărătorul, cât și numitorul la cmmdc(a, b). Fracția obținută se numește ireductibilă.
Exemplu: fracția 48/18 se simplifică cu cmmdc = 6, rezultând 8/3.
#include <iostream>
using namespace std;
int cmmdc(int a, int b)
{
if (b == 0)
return a;
return cmmdc(b, a % b);
}
int main()
{
int a, b, d;
cin >> a >> b;
d = cmmdc(a, b);
cout << a / d << " " << b / d;
return 0;
}
Exercițiu de completare
Completează enunțul despre CMMDC cu cuvintele potrivite:
CMMDC a două numere este cel mai mare număr care le ______ pe amândouă. Algoritmul lui Euclid folosește proprietatea cmmdc(a, b) = cmmdc(b, a ______ b). Cazul de ______ este atins când b = 0, iar rezultatul este ______. O fracție se numește ireductibilă când este simplificată cu ______.
Bancă de cuvinte:
Exercițiu de completare
Completează funcția cmmdc din codul C++:
Bancă de cuvinte:
Test de înțelegere
Test rapid - CMMDC:
1. Cazul de bază al algoritmului lui Euclid este:
2. cmmdc(48, 18) are valoarea:
3. Fracția 48/18 simplificată devine:
Aprofundare
De ce funcționează algoritmul lui Euclid? Orice divizor comun al lui a și b divide și restul a % b, deci mulțimea divizorilor comuni ai perechii (a, b) este identică cu cea a perechii (b, a % b). Reducând mereu perechea, ajungem la (cmmdc, 0), unde răspunsul este evident. Resturile descresc strict, deci algoritmul se termină după un număr mic de pași (logaritmic).
CMMMC prin CMMDC. Cel mai mic multiplu comun se calculează direct cu formula cmmmc(a, b) = (a / cmmdc(a, b)) * b. Împărțirea înainte de înmulțire evită depășirea tipului de date.
Fracții ireductibile. O fracție a / b se simplifică împărțind numărătorul și numitorul la cmmdc(a, b). Astfel se obține forma ireductibilă, folosită la rezolvarea problemelor cu fracții.
Cazuri particulare.
cmmdc(a, 0) = apentru orice a ≥ 0, inclusivcmmdc(0, 0)tratat separat (rezultat 0).- Pentru
a < b, primul pas realizeazăcmmdc(b, a)prin schimbare implicită de poziții, deci algoritmul funcționează fără sortare prealabilă. - Pentru numere negative se ia valoarea absolută, deoarece CMMDC este definit doar pentru numere naturale.
PbInfo - CMMDC
Enunț:
Cerință: Se citesc două numere naturale a și b. Să se afișeze cel mai mare divizor comun al lor, folosind un subprogram recursiv.
Date de intrare:
Programul citește de la tastatură numerele a și b.
Date de ieșire:
Programul va afișa pe ecran valoarea cmmdc(a, b).
Restricții și precizări:
1 ≤ a, b ≤ 2.000.000.000.
Exemplu:
Intrare:
48 18
Ieșire:
6
Cum gândim soluția:
- Definim funcția
cmmdc(a, b) - Cazul de bază: dacă
b == 0, întoarcem a - Altfel întoarcem
cmmdc(b, a % b) - În main citim a și b și afișăm rezultatul
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int cmmdc(int a, int b)
{
if (b == 0)
return a;
return cmmdc(b, a % b);
}
int main()
{
int a, b;
cin >> a >> b;
cout << cmmdc(a, b);
return 0;
}
Ce învățăm: algoritmul lui Euclid este foarte eficient, deoarece resturile scad rapid.
PbInfo - Fracții ireductibile
Enunț:
Cerință: Se citesc două numere naturale a și b (numărătorul și numitorul unei fracții). Să se afișeze fracția simplificată la forma ireductibilă, folosind cmmdc calculat recursiv.
Date de intrare:
Programul citește de la tastatură numerele a și b.
Date de ieșire:
Programul va afișa numărătorul și numitorul simplificați, separați printr-un spațiu.
Restricții și precizări:
1 ≤ a, b ≤ 2.000.000.000, b nenul.
Exemplu:
Intrare:
48 18
Ieșire:
8 3
Cum gândim soluția:
- Definim funcția recursivă
cmmdc(a, b) - În main citim a și b
- Calculăm d = cmmdc(a, b)
- Afișăm a / d și b / d
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int cmmdc(int a, int b)
{
if (b == 0)
return a;
return cmmdc(b, a % b);
}
int main()
{
int a, b, d;
cin >> a >> b;
d = cmmdc(a, b);
cout << a / d << " " << b / d;
return 0;
}
Ce învățăm: CMMDC-ul este util în practică pentru simplificarea fracțiilor.
Exercițiul Practic: CMMDC în practică
Sarcini de lucru
Rezolvă sarcinile următoare despre CMMDC
Sarcina 1: CMMDC a trei numere
Cerință: Scrie un program C++ care citește trei numere și afișează cmmdc al lor, folosind funcția recursivă cmmdc. Rezultatul este cmmdc(cmmdc(a, b), c). Pentru 24, 36, 60 rezultatul este 12.
Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;
int cmmdc(int a, int b)
{
if (b == 0)
return a;
return cmmdc(b, a % b);
}
int main()
{
int a, b, c;
cin >> a >> b >> c;
cout << cmmdc(cmmdc(a, b), c);
return 0;
}
Verifică: cmmdc(24, 36) = 12, iar cmmdc(12, 60) = 12.
Sarcina 2: CMMMC
Cerință: Folosind proprietatea cmmmc(a, b) = a * b / cmmdc(a, b), scrie un program C++ care afișează cel mai mic multiplu comun a două numere. Pentru 12 și 18, cmmmc este 36.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int cmmdc(int a, int b)
{
if (b == 0)
return a;
return cmmdc(b, a % b);
}
int main()
{
int a, b;
cin >> a >> b;
cout << (long long)a * b / cmmdc(a, b);
return 0;
}