|

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:

  1. C.M.M.D.C. pentru două numere pozitive:
    • Intrare: 48 și 18.
    • Algoritmul lui Euclid: 6.
  2. 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:

  1. Scrieți un program care citește un șir de numere și determină C.M.M.D.C. pentru toate.
  2. Realizați un program care folosește algoritmul lui Euclid pentru a calcula C.M.M.D.C. între trei numere.
  3. 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:

  1. Algoritmul lui Euclid (împărțiri succesive):
    • Start -> Cât timp b ≠ 0 -> r = a % b -> a = b -> b = r -> Stop.
  2. 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.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *