Algoritmi Elementari – Calcularea C.M.M.D.C. (Cel Mai Mare Divizor Comun) 9
1. Obiectivele lecției:
- Să înțeleagă conceptul de Cel Mai Mare Divizor Comun (C.M.M.D.C.).
- Să cunoască și să implementeze algoritmi pentru calcularea C.M.M.D.C.
- Să aplice metode diferite de calculare, inclusiv metoda scăderilor repetate și algoritmul lui Euclid.
- Să rezolve probleme practice utilizând C.M.M.D.C.
2. Conținutul lecției:
Ce este C.M.M.D.C.?
- Definiție: Cel mai mare divizor comun (C.M.M.D.C.) al două numere este cel mai mare număr care divide exact ambele numere, fără rest.
- Exemple:
- C.M.M.D.C. pentru 12 și 18 este 6 (deoarece 6 este cel mai mare număr care divide atât 12, cât și 18).
- C.M.M.D.C. pentru 8 și 14 este 2.
3. Metode de calculare a C.M.M.D.C.:
Metoda 1: Scăderile repetate
- Principiu: Dacă scădem numărul mai mic din numărul mai mare și repetăm acest proces până când cele două numere devin egale, valoarea comună este C.M.M.D.C.
- Pseudocod:
Intrare: a, b
Cât timp a ≠ b:
Dacă a > b:
a = a – b
Altfel:
b = b – a
Ieșire: a (sau b)
- Cod în C++:
#include <iostream>
using namespace std;
int main() {
int a, b;
cout << „Introdu doua numere: „;
cin >> a >> b;
while (a != b) {
if (a > b) {
a = a – b;
} else {
b = b – a;
}
}
cout << „C.M.M.D.C. este: ” << a << endl;
return 0;
}
Metoda 2: Algoritmul lui Euclid (împărțiri succesive)
- Principiu: Înlocuiește numărul mai mare cu restul împărțirii dintre cele două numere. Repetă până când restul devine 0. Ultimul divizor nenul este C.M.M.D.C.
- Pseudocod:
Intrare: a, b
Cât timp b ≠ 0:
r = a % b
a = b
b = r
Ieșire: a
- Cod în C++:
#include <iostream>
using namespace std;
int main() {
int a, b;
cout << „Introdu doua numere: „;
cin >> a >> b;
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
cout << „C.M.M.D.C. este: ” << a << endl;
return 0;
}
Metoda 3: Versiunea recursivă a algoritmului lui Euclid
- Principiu: Utilizează recursivitatea pentru a calcula C.M.M.D.C.
- Pseudocod:
Funcție Euclid(a, b):
Dacă b = 0:
returnează a
Altfel:
returnează Euclid(b, a % b)
- Cod în C++:
#include <iostream>
using namespace std;
int cmmmdc(int a, int b) {
if (b == 0) {
return a;
} else {
return cmmmdc(b, a % b);
}
}
int main() {
int a, b;
cout << „Introdu doua numere: „;
cin >> a >> b;
cout << „C.M.M.D.C. este: ” << cmmmdc(a, b) << endl;
return 0;
}
4. Exemple practice:
- C.M.M.D.C. pentru două numere pozitive:
- Intrare: 48 și 18.
- Algoritmul lui Euclid: 6.
- C.M.M.D.C. pentru un număr și 0:
- C.M.M.D.C. pentru orice număr și 0 este numărul însuși.
5. Activități practice pentru elevi:
- Scrieți un program care citește un șir de numere și determină C.M.M.D.C. pentru toate.
- Realizați un program care folosește algoritmul lui Euclid pentru a calcula C.M.M.D.C. între trei numere.
- Implementați versiunea recursivă a algoritmului pentru a calcula C.M.M.D.C. pentru mai multe perechi de numere introduse de utilizator.
6. Scheme logice:
- Algoritmul lui Euclid (împărțiri succesive):
- Start -> Cât timp b ≠ 0 -> r = a % b -> a = b -> b = r -> Stop.
- Metoda scăderilor repetate:
- Start -> Cât timp a ≠ b -> Dacă a > b, atunci a = a – b -> Altfel b = b – a -> Stop.
7. Concluzie:
- Calcularea C.M.M.D.C. este un algoritm fundamental cu aplicații multiple în matematică și informatică.
- Algoritmul lui Euclid este cel mai eficient și este utilizat pe scară largă datorită simplității și rapidității.
- Elevii vor înțelege mai bine conceptul de divizibilitate și aplicarea logicii algoritmice.