Home Introduzione News Lezioni e laboratorio Programma Esame Esoneri Materiale Progetti studenti Link

 

Algoritmo A7

Calcolo del massimo comun divisore (MCD) e del minimo comune multiplo (mcm) fra due interi positivi

1. Input(m, n)
2. m > n ? // vuole assegnare a MCD il min fra m ed n
   2.1 Se sì:
      2.1.1 MCD = n
   2.2 Se no:
      2.2.1 MCD = m
3. MCD * (m / MCD) = m ? // la div. è intera!
      3.1 Se sì:
         3.1.1 MCD * (n / MCD) = n ? // div. intera
            3.1.1.1 Se sì:
               3.1.1.1.1 mcm = (m * n) / MCD
               3.1.1.1.2 Output(MCD, mcm)
               3.1.1.1.3 Stop
4. MCD = MCD - 1
5. Vai al passo 3

Commenti

  1. L'algoritmo sfrutta la proprietà: MCD(m, n) * mcm(m, n) = m * n.
  2. Si cerca dapprima il MCD, provando tutti gli interi possibili, a partire dal min fra m ed n.
  3. Il ciclo 3-5 termina sicuramente perché prima o poi viene trovato il MCD (se i due interi sono primi fra loro il MCD sarà 1).
 

 

Bacheca di Informatica Grafica

Forum studenti:

by FdA
ultima modifica: 09/02/2004 13.23