programmazione – FilosofoMed

Nel post di oggi scopriremo insieme cos’è il Massimo Comune Divisore (MCD) e in particolare vedremo come calcolarlo in modo efficiente utilizzando l’algoritmo di Euclide. Approfondiremo anche la relazione tra il MCD e il Minimo Comune Multiplo (mcm), illustrando la formula che li lega. Inoltre, per gli amanti della programmazione, presenteremo un semplice codice in C++ che vi permetterà di calcolare il MCD in modo automatico.

Indice:

L’algoritmo di Euclide per calcolare il Massimo Comune Divisore (MCD)

Ci sono “trucchi” matematici che permettono di velocizzare la risoluzione di un esercizio. Per chi li conosce, ciò può significare ad esempio liberarsi rapidamente di un problema durante un test. Dunque non si tratta di semplici curiosità, ma di vere e proprie tecniche che possono salvarci in diverse occasioni, utilissime e da tenere a mente.

Uno di quegli espedienti frutto di ingegno matematico è l’algoritmo di Euclide, un metodo astuto per calcolare il Massimo Comune Divisore (MCD).

Che cos’è e a cosa serve il Massimo Comune Divisore?

Il Massimo Comune Divisore, o MCD, di due o più numeri, ad esempio di a e b, è – come dice il nome stesso – il più grande dei divisori comuni tra a e b.

Prendiamo ad esempio a=48 e b=18. Come forse avrai già intuito facilmente (dato che i numeri sono piccoli e si “vede” facilmente quali possono essere i loro divisori), tra 48 e 18 il MCD è 6.

Per rendere più “visibile” la funzione e dare un esempio d’uso pratico del Massimo Comune Divisore, immagina di avere due gruppi di oggetti da ripartire in modo da formare il massimo numero possibile di confezioni identiche. Inoltre, non deve rimaner escluso alcun oggetto (il massimo divisore comune divide ciascuno dei due gruppi dando resto zero).

Immagina allora di avere 48 matite e 18 gomme. Le confezioni che otterrai conterranno ciascuna un certo numero di matite e alcune gomme. Ma quante sono le confezioni che puoi formare? Semplice, te lo dice l’MCD. Nel nostro caso, potremo formare 6 kit con ciascuno 8 matite e 3 gomme (48 / 6 = 8; 18 / 6 = 3).

Perché usare l’algoritmo di Euclide?

Solitamente, a scuola insegnano a trovare il MCD tra due numeri partendo dalla scomposizione in fattori primi (fattorizzazione) dei due numeri.

Tuttavia, l’algoritmo di Euclide – una tecnica tanto antica ed elegante – offre una soluzione più veloce e meno laboriosa, soprattutto con numeri grandi, e permette di trovare il MCD in pochissimi passi.

Il genio antico di Euclide

L’argomento merita un brevissimo excursus. La matematica, infatti, che oggi si trova ovunque nell’informatica e in tantissime altre applicazioni, è una scienza che affonda le sue radici nei millenni passati. Ciò che mi affascina in particolare è come i pensatori di epoche remote siano riusciti a fondare la matematica praticamente senza strumenti, solo con il ragionamento, l’immaginazione, e al massimo riga e compasso.

Uno dei geni più brillanti del passato è stato proprio Euclide, noto come il “padre della geometria”. Euclide visse ad Alessandria d’Egitto tra il IV e il III secolo a.C. Anche se i dettagli della sua vita rimangono avvolti nel mistero, è noto soprattutto per essere l’autore di una delle opere più influenti della storia della matematica: gli Elementi.

Gli Elementi sono una raccolta di 13 libri. Quest’opera, che si prefiggeva di raccogliere in forma sistematica i principi della matematica e soprattutto della geometria, è stata il fondamento della matematica per i secoli seguenti. È un peccato che nelle scuole moderne si accenni poco o nulla a Euclide e non si dedichi il giusto spazio agli Elementi.

Proprio negli Elementi (libro VII) troviamo, tra le tante altre cose, anche la formalizzazione dell’algoritmo per calcolare il MCD, che oggi chiamiamo appunto “di Euclide”.

Cos’è un algoritmo?

In breve, dato che ci accingiamo a parlare dell’“algoritmo” di Euclide, è opportuno ricordare brevemente che cos’è un algoritmo.

In matematica e informatica, un algoritmo è una sequenza finita di istruzioni che, se eseguita correttamente, permette di risolvere un problema o di raggiungere un determinato risultato. Un po’ come una ricetta di cucina, l’algoritmo ti guida passo passo, indicandoti quali operazioni compiere e in quale ordine.

Come funziona l’algoritmo di Euclide?

Ecco come funziona l’algoritmo di Euclide.

Prendiamo due numeri naturali di cui vogliamo calcolare il Massimo Comune Divisore. Mettiamoli in una tabella fatta di due colonne (le chiameremo per comodità colonna A e colonna B), che gradualmente andremo a riempire mano a mano che i passi dell’algoritmo si succedono.

Nella prima cella della colonna A ci va il numero più grande dei due. Nella prima cella della colonna B ci va l’altro numero.

Ad esempio, prendiamo 56 e 24. Vogliamo calcolare il MCD tra i due.

Il prossimo passo, che sarà ripetuto ogni passo dell’algoritmo di Euclide, è composto di due passaggi:

1) Nella colonna A, sotto il numero più “grande” tra i due, riportiamo il numero della colonna B, quindi 24 (freccia verde in figura).

2) Facciamo la divisione tra 56 e 24, dopodiché scriviamo il resto della divisione nella colonna B (in questo caso 56:24 resto 8).

Ci fermeremo solo quando avremo resto = 0. E leggendo ciò che sta nella cella a sinistra dello 0, cioè nella colonna A, scopriremo qual è il MCD.

Continuiamo perciò riportando 8 sotto la colonna A, e facendo la divisione tra 24 e 8:

Abbiamo ottenuto resto zero! Allora il MCD è 8.

La relazione tra MCD e mcm

Una delle proprietà più eleganti della teoria dei numeri è la relazione che lega il Massimo Comune Divisore (MCD) e il Minimo Comune Multiplo (mcm) di due numeri interi positivi. (Ricordiamo brevemente che il minimo comune multiplo, abbreviato in mcm, è il più piccolo numero positivo che è multiplo di due (o più) numeri).

Eccola: presi due numeri naturali a e b, il prodotto a*b è uguale al prodotto dei loro MCD con il loro mcm.

$MCD(a,b)*mcm(a,b)=a*b$

Da quella relazione è possibile ricavare le formule inverse per ottenere velocemente ciò che ci interessa:

$mcm(a,b)=\frac{a*b}{MCD(a,b)}$

$MCD(a,b)=\frac{a*b}{mcm(a,b)}$

Codice C++ per calcolare il MCD con l’algoritmo di Euclide

Il calcolo del Massimo Comune Divisore (MCD) con l’algoritmo di Euclide è particolarmente efficiente e facile da implementare in un programma, permettendo di calcolare il MCD in modo rapido anche per numeri grandi.

Per chi si cimenta con il linguaggio di programmazione C++, ecco come scrivere un semplice programma in C++ che dati due numeri di input, a e b, restituisce come output il Massimo Comune Divisore tra i due:

#include <iostream>
using namespace std;

// Funzione per calcolare il MCD con l'algoritmo di Euclide
int mcd(int a, int b) {
    // Finché b non è zero, continua a trovare il resto
    while (b != 0) {
        int temp = b;
        b = a % b;  // Il resto della divisione tra a e b
        a = temp;   // Aggiorna a con il valore di b
    }
    return a;  // Quando b diventa zero, a contiene il MCD
}

int main() {
    int a, b;

    // Input da parte dell'utente
    cout << "Inserisci il primo numero (a): ";
    cin >> a;
    cout << "Inserisci il secondo numero (b): ";
    cin >> b;

    // Calcolo del MCD e output
    cout << "Il Massimo Comune Divisore di " << a << " e " << b << " è: " << mcd(a, b) << endl;

    return 0;
}

Come funziona:

Algoritmo di Euclide: il programma esegue una serie di operazioni di divisione tra i due numeri, sostituendo di volta in volta il primo numero con il secondo e il secondo con il resto della divisione, fino a quando il secondo numero (b) diventa zero. Il valore finale di a è il MCD.
Funzione mcd: prende come input due numeri interi, a e b, e continua a calcolare il resto della divisione tra a e b finché b non diventa zero.

Esecuzione:

Se, ad esempio, si inseriscono i numeri 48 e 60, l’output sarà:

Il Massimo Comune Divisore di 48 e 60 è: 12

Questo codice utilizza un ciclo while che ripete il calcolo del resto e aggiorna i numeri finché il resto non diventa zero, restituendo il valore di a come il MCD.

Nella seguente immagine c’è il medesimo codice riportato sopra, per il calcolo dell’MCD con Euclide in cpp, reso un po’ più chiaro dall’uso dei colori nell’editor di Xcode, per identificare le varie funzioni e istruzioni:

Tag: programmazione

L’algoritmo di Euclide per il Massimo Comune Divisore (MCD)