Divizibilitate / Algoritmul lui Euclid


Editat de Candale Silviu (silviu) la data 2016-12-27
Etichete: nicio etichetă

Cel mai mare divizor comun al două numere naturale n și m poate fi determinat folosind descompunerea în factori primi a celor două numere. Această metodă este mai dificil de implementat. Există o metodă mai simplu de, numită algoritmul lui Euclid.

Sunt două variante ale algoritmului lui Euclid: cu scăderi și cu împărțiri.

Algoritmul lui Euclid cu scăderi

Algoritmul lui Euclid cu scăderi se bazează pe ideea că cele mai mare divizor a două numere divide și diferența acestora. Algoritmul este:

  • Cât timp numerele sunt diferite, se scade numărul mai mic din numărul mai mare.
  • Când numerele devin egale, valoare comună este cel mai mare divizor comun al valorilor inițiale.
  • Algoritmul nu poate fi aplicat dacă unul dintre numere este 0. De ce?

Exemplu:

  • Fie n=32 și m=24.
  • Numerele nu sunt egale, scădem numărul mai mic din numărul mai mare, n = n - m = 32 - 24 = 8.
  • Acum n = 8 și m = 24.
  • Numerele nu sunt egale, scădem numărul mai mic din numărul mai mare, m = m - n = 24 - 8 = 16.
  • Acum n = 8 și m =16.
  • Numerele nu sunt egale, scădem numărul mai mic din numărul mai mare, m = m - n = 16 - 8 = 8.
  • Acum n = 8 și m = 8.
  • Numerele sunt egale. Valoarea comună, 8, este cel mai mare divizor comun al valorilor inițiale, 32 și 24

Program C++:

#include <iostream>
int main()
{
    int n , m;
    std :: cin >> n >> m;
    while(n != m)
        if(n > m)
            n -= m;
        else
            m -= n;
    std :: cout << n << std :: endl;
    return 0;
}

Algoritmul lui Euclid cu împărțiri

Algoritmul lui Euclid cu împărțiri se bazează pe ideea că cel mai mare divizor a două numere divide și restul împărțirii acestora, conform teoremei împărțirii cu rest. Algoritmul este:

  • Cât timp m != 0:
    • Determinăm restul împărțirii lui n la m.
    • În continuare n devine m, iar m devine restul calculat.
  • Valoarea actuală a lui n este cel mai mare divizor comun a valorilor inițiale.

Exemplu:

  • Fie n=32 și m=24.
  • m != 0:
    • Calculăm r = n % m = 8
    • n devine m, iar m devine r.
  • Acum n=24 și m=8.
  • m != 0:
    • Calculăm r = n % m = 0
    • n devine m, iar m devine r.
  • Acum n=8 și m=0.
  • m este 0. Valoarea actuală a lui n = 8 este cel mai mare divizor comun al valorilor inițiale, 32 și 24.

Program C++:

#include <iostream>
int main()
{
    int n , m;
    std :: cin >> n >> m;
    while(m != 0)
    {
        int r = n % m;
        n = m;
        m = r;
    }
    std :: cout << n << std :: endl;
    return 0;
}

Pentru a determina cel mai mic multiplu comun a două numere naturale folosim următoarea observație:

Produsul a două numere naturale este egal cu produsul dintre cel mai mare divizor comun al lor și cel mai mic multiplu comun al lor.
n * m = cmmdc * cmmmc

Pentru a determina cel mai mare divizor comun a mai multor numere:

  • determinăm cmmdc dintre primele două numere.
  • determinăm cmmdc între cmmdc anterior și al treilea număr.
  • determinăm cmmdc între cmmdc anterior și al patrulea număr.
  • ș.a.m.d.

Fișiere atașate


Vezi și:

Editat de Candale Silviu (silviu) la data 2016-12-27