Massimo comun divisore di due numeri
Questa pagina ha due obiettivi didattici :
- Mostrare su un esempio concreto quanto sia importante, prima di affrontare la scrittura di un programma informatico, un accurato studio e analisi degli algoritmi utilizzabili, per implementare quello più efficiente dal punto di vista del "tempo macchina" e che in ogni caso meglio si presta alla traduzione in un linguaggio di programmazione.
- Mostrare il pericolo legato ai problemi di arrotondamento tipici di tutte le macchine calcolatrici che devono, di necessità, lavorare con un sottoinsieme finito degli insiemi numerici che si usano in matematica.
La ricerca del massimo comun divisore di due numeri a e b è fatta, di solito, seguendo l'algoritmo "standard": si cercano i divisori di a e b e poi si prendono i divisori comuni con il minimo esponente. Questo algoritmo è sufficiente per numeri che hanno divisori primi piccoli, ma basta provare, per esempio, con la coppia (4687, 2279) per toccare con mano la difficoltà pratica di un simile procedimento.
Esiste un algoritmo molto più efficiente, scoperto già da Euclide (Elementi, Libro VII, pr.1), e di immediata implementazione in un linguaggio informatico. L'algoritmo si basa sul seguente
Teorema: Se a e b sono
naturali con a≥b>0 e
a=bq+r, d é un divisore di a e
b se e solo se é un divisore di b ed
r.
La dimostrazione è immediata: poiché
r=a-bq ogni divisore di a e b é anche un divisore
di r; viceversa poiché a=bq+r, ogni divisore di b ed r
é anche un divisore di a.
Si può allora procedere eseguendo successivamente le divisioni intere: a=bq0+r0, b=r0q1+r1, r0=r1q2+r2, ecc., fin quando si ottiene come resto zero. Il penultimo resto è il massimo comun divisore cercato.
L'implementazione javascript è addirittura banale e si compone delle poche righe evidenziate in grassetto nella funzione qui sotto. Il resto è solo controllo dell'input e scambio dei numeri in ingresso in modo da avere come primo numero il maggiore dei due (perché nel fare la divisione si fa il più grande diviso il più piccolo).
function calcola()
{
var
num1=parseInt(document.getElementById('numero1').value);
var
num2=parseInt(document.getElementById('numero2').value);
if (isNaN(num1) || isNaN(num2)|| num1<0 || num2<0)
//controllo dell'input
{
window.alert("Dati in ingresso non
validi.\nInserisci interi maggiori o uguali a 0.");
return; //L'istruzione causa l'interruzione
della funzione, perché essa non è
calcolabile
}
if (num1<num2) //scambio in modo da avere num1 sempre
più grande
{
var temp;
temp=num1;
num1=num2;
num2=temp;
}
if (num2==0) //Se il numero più piccolo è zero
l'MCD è il più grande (anche quando il
più grande è zero, per def).
{
document.getElementById('risultato').value=("Il
massimo comun divisore tra "+num1+" e
"+num2+" è "+num1);
return;
}
var x=num1;
var y=num2;
var r;
while (y>0)
{
r=x % y;
x = y;
y = r;
}
document.getElementById('risultato').value=(" Il
massimo comun divisore tra "+num1+" e
"+num2+" è "+x+".");
} //end of calcola()
Per contro l'implementazione con l'algoritmo "standard" (quello che ci ha tanto fatto penare sui banchi della scuola media!!) è lunga e laboriosa e invitiamo i volenterosi a provare a realizzarla utilizzando il codice, opportunamente adattato, del programma per la scomposizione in fattori.
Commenti
- Il commento più importante a questo programma non è un commento sulle tecniche javascript utilizzate, quanto piuttosto sul fatto che per realizzare buon codice non è sufficiente conoscere alla perfezione un linguaggio di programmazione, bisogna anche conoscere alla perfezione il problema che il programma deve risolvere.
- L'algoritmo contenuto nell' if (num1<num2) è il classico algoritmo di scambio di due numeri con l'uso di una variabile di appoggio.
-
Questo programma consente di verificare facilmente i limiti
delle macchine calcolatrici in genere.
Basta eseguire le seguenti prove:
MCD(123456789123456789 , 2) = 2 (palesemente errato)
MCD(123456789123456780 , 3) = 1 (palesemente errato)
MCD(12345678912345678 , 3) = 3 (esatto).
Il problema è legato al superamento della capacità di calcolo con interi, e la cosa non viene segnalata da alcun messaggio. Per quanto riguarda i tre esempi proposti, la cosa più sorprendente è il comportamento rispetto agli ultimi due: avere o non uno zero come ultima cifra non cambia nulla nei confronti della divisibilità per tre. Il problema degli arrotondamenti e del superamento di capacità nei programmi per computer è cruciale e costituisce argomento di continui studi e ricerche.
Esercizi proposti
- Realizzare un controllo dell'input più efficiente che determini quale dei due dati in ingresso non è accettabile, dando il focus a quello da reinserire, se ce n'è uno solo.
- Realizzare (ma non è banale) un programma che utilizzi l'algoritmo della scomposizione in fattori per trovare l'MCD di due numeri.