Informatica I - Esercizi algoritmo di Euclide

Esercizio di laboratorio

Argomento: cicli, decisioni, confronto tra numeri interi

Scrivere un programma che calcoli il massimo comun divisore (MCD) fra due numeri interi positivi m e n acquisiti da standard input, e visualizzi il risultato a standard output.

Algoritmo di Euclide

Si usi il ben noto per il calcolo del MCD tra due due numeri interi positivi m ed n (con m>n):

• Finché il resto della divisione di m per n è diverso da zero o m n il nuovo valore di è il precedente valore di o n m il nuovo valore di è il resto della divisione del precedente valore di per il precedente valore di
• Quando il resto è zero, allora il MCD è l'attuale valore di n

Soluzione

import java.util.Scanner;

public class MCDTester{

public static void main(String[] args){

Scanner in = new Scanner(System.in);

System.out.print("Inserire due interi positivi m ed n: ");

int m = in.nextInt();

int n = in.nextInt();

// controllo dell'input: verifica che i numeri siano positivi

if (m <= 0 || n <= 0){

if (m <= 0)

System.out.println("m = " + m + ": ingresso non ammesso");

if (n <= 0)

System.out.println("n = " + n + ": ingresso non ammesso");

return; //attenzione: l'effetto di questo enunciato e` di

} //terminare l'esecuzione del metodo main e quindi

//dell'intero programma

//invoca il metodo statico ausiliario EuclideMCD (cfr. più sotto)

int mcd = EuclideMCD(m,n);

// Stampa su output standard

System.out.println("MCD(" + m + "," + n + ") = " + mcd);

}

public static int EuclideMCD(int m, int n){

// Ordinamento

int i = m;

int j = n;

if (m > n) // pongo i > j

{

i = n;

j = m;

}

// Algoritmo di Euclide

int tmpInt;

while ((tmpInt = i % j) != 0) //attenzione! qui succedono due cose:

{ //1.si assegna il valore i%j a tmpInt

//2.si controlla che tmpInt sia non-nulla

i = j;

j = tmpInt;

}

return j;

}

}