funzione ricorsiva mcm (c++)

[ivan92]

mi potreste dire la definizione della funzione ricorsiva del minimo comune multiplo?...

[M@ttia]

Solitamente si parte dal fatto che:

Codice: Seleziona tutto

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

e quindi si scrive una funzione ricorsiva per il GCD (il famoso Algoritmo di Euclide) e poi si ritorna mcm(a,b) := (a * b) / MCD(a,b,)

L'algoritmo di Euclide per il GCD è molto semplice:

Formula Diretta (quindi non-ricorsiva):

Codice: Seleziona tutto

 function MCD(a, b)
     while a ≠ b
         if a > b
             a := a - b
         else
             b := b - a
     end while
     return a

Formula Ricorsiva:

Codice: Seleziona tutto

   
 function MCD(a, b)
  if b = 0
    return a;
  else
    return MCD(b, a % b);     <- Qui con a % b intendo a MOD b, che in C++, ecc. si scrive appunto tramite l'operatore %
}


[ivan92]

grazie mille

[M@ttia]

Prego