Newsgroup: it.scienza.informatica
Titolo: Algoritmo per il calcolo del minimo comune multiplo

Scusate avrei un problema:
devo implementare nel linguaggio C un algoritmo per il calcolo del
minimo comune multiplo di "n" numeri potete per caso aiutarmi?
Grazie.

Scusa, ma mi sono dimenticato di dire che se i numeri sono più di due,
devi seguire il famoso principio per cui:
MCD (a, b, c) = MCD (a, MCD (b,c))     .......
E così per tutti i numeri che ti servono.
Scusa, ma ho la brutta abitudine di non fare attenzione a tutto ciò
che c'è scritto nel msg e poi i risultati si vedono ...
Paolo


Grazie.
Primo metodo: utilizza il resto della divisione euclidea (operatore:
"%"):
int MCD (int a, int b)
{
    while ((a != 0) && (b != 0) {
        if (a<b)   b = b % a;
        else       a = a % b;
    }
    if (a != 0) return a;
    else return b;
}
Secondo metodo: più complesso, ma non presenta problemi:
int MCD (int a, int b)
{
    while (a != b) {
        if (a < b)  b = b % a;
        else        a = a % b;
    }
    return a;   //Sarebbe identico se tu scrivessi return b;
Non li ho provati, ma dovrebbero funzionare (almeno spero).
Sperando di esserti stato di aiuto.
Paolo 

Beh, un metodo banale: prendi il più alto, con un while moltiplicalo per
1,2,3,... finché il risultato non è divisibile per tutti gli n numeri, e
avrai ottenuto il mcm.
Ciao
Michele


Sbagliato.
Occorre sostituire l'operatore di modulo ' % '
con quello di sottrazione ' - '. Tra l'altro cosě concepito il ciclo
non solo non fornisce un risultato corretto, ma non riesce neanche
a terminare: si genera un errore a run-time (divisione per zero)!!
Per il calcolo dell'm.c.m. basti considerare che dati due numeri
interi arbitrari <a> e <b>, vale la relazione seguente (facilmente
dimostrabile):
(1)                            a * b = m.c.m. * M.C.D
Quindi ottenuto l'M.C.D. fra due interi a e b (tramite l'algoritmo di cui
sopra), si ha:
                                m.c.m. = (a * b) / M.C.D.
Nel caso di piů di due numeri puoi applicare la stessa relazione
valida nel caso dell'M.C.D.:
                m.c.m. (a, b, c) = m.c.m.( a  ,  m.c.m.(b , c) )
NOTA: non tentare di generalizzare a n numeri (n>2) la regola
al punto (1): vale solo per coppie di numeri!!!
Ciao,
Adriano.

che c'è scritto nel msg e poi i risultati si vedono ...
Soprattutto perchè quello è l'algoritmo per il calcolo del massimo comun
divisore non del minimo comune multiplo.........
io usere il seguente:
int mcm(int a,int b,int a1,int b1)
{ if(a=b) return(1);
  if(a>b) return(mcm(a,b+b1,a1,b1);
  else return(mcm(a+a1,b,a1,b1);
}
chiamala con mcm(a,b,a,b) fove a e b sono i numeri di cui vuoi l'mcm per n
numeri la chiami ciclicamente ovvero supponi di averli nell'array a;
p=1;
for(int i=0;i<n;i++) p=mcm(p,a[i]);
alla fine in p hai l'mcm di tutti....
Federico

 ha scritto nel messaggio ...

Hai mai sentito parlare di complessità degli
algoritmi?????????????????????????
Federico

 numeri la chiami ciclicamente ovvero supponi di averli nell'array a;
La funzione che tu proponi puo' essere ottimizzata all'inverosimile...
Quella qui sotto e' equivalente, eccetto che nel caso b==0 in cui la tua
prosegue in un loop infinito. Questa invece termina sempre: riporto solo
il corpo per brevita' (per il nome e la lista dei parametri ampio spazio
alla fantasia);
                return 1;
... o meglio ancora una macro...
Affinché calcoli l'm.c.m. la prima riga della tua funzione va modificata in:
                if(a==b) return(a);
(doppio segno '=' e
'a' o 'b' in luogo di 1)
Ciao,
Adriano.
P.S. Naturalmente ho scherzato un po'... ma riguardo la correzione
ero serissimo! ;-))




 metodo (almeno credo).
La ricorsione è un ottimo strumento per il progetto di algoritmi
perché ben si adatta ai nostri schemi di pensiero. Tuttavia
in applicazioni reali (vs didattiche) occorre valutare di volta in
volta se la sua introduzione è praticabile: l'insieme dei
dati da elaborare può essere  tale da renderla molto più complessa
in termini di spazio e di tempo (ripetute chiamate_a_funzioni incidono
pesantemente sulle prestazioni...) tanto da renderle preferibile una
struttura iterativa, benché concepibile (e implementabile) a prezzo di un
maggiore impegno.
Considerando poi che l'algoritmo proposto da Federico si può
tradurre con facilità in uno equivalente ma iterativo, non ci sono più
alibi... ;-))
/* mcm Iterative Version */
int mcm(int a, int b) {
 int aa=a;
 int bb=b;
 while(aa!=bb) (aa<bb)?(aa+=a):(bb+=b);
 return aa;
}
Più veloce e (molto) meno esigente in termini di memoria... ;-)))))
Ciao, Adriano.
____________________________________
Electronic Engineering Student
University of Tor Vergata - Rome, Italy
longd...@geocities.com

 }
Secondo me è perfetto, ma rimango dell'idea che per certi numeri
(poiché la complessità dipende da quali numeri considero, o meglio
qual'è la loro differenza) risulta più veloce il mio algoritmo:
int mcm(int a, int b)
{
    return a*b / MCD(a, b);
}
int MCD (int a, int b)
{
    while (a != b) {
        if (a == 0) return b;
        else if (b == 0) return a;
        else if (a<b)   b = b % a;
        else a = a % b;
    }
    return a; //equivalente a return b
}
Va puntualizzato che l'unica cosa che lo rende leggermente migliore è
la possibilità di utilizzare l'operazione di modulo (anche se devo
controllare che i due numeri siano diversi da 0), se avessi sottratto
i due numeri il mio sarebbe risultato enormemente più complesso.
Comunque quest'anno studierò Algoritmi e Strutture Dati 1 e alla fine
del corso sapro postare certamente un algoritmo più efficace.
Mox.


Beh, mi sembra il meno pesante di quelli proposti prima, non è neanche
ricorsivo!!
Cosa intendi di preciso?


wrote:

Scusa se mi intrometto, ma volevo solo darti un'indicazione: quando si
parla di complessità generalmente si intende complessità di tempo,
quindi non ci interessiamo di quanto spazio occupiamo....
Per il resto, il fatto che utilizziamo la ricorsione generalmente non
è negativo, salvo la presenza di un metodo iterativo avente lo stesso
ordine di complessità.
Gli algoritmi proposti da me e da Federico (a proposito, con le
modifiche proposte da # Bright Pixel #, diventa un algoritmo che
occupa pochissima memoria e con una complessità di tempo piuttosto
bassa) ciclano relativamente poche volte.
Probabilmente il tuo algoritmo si sviluppa in poche righe di codice,
che però impiegano moltissimo tempo per generare un risultato. Se non
sbaglio con un sistema simile potresti anche ottenere la scomposizione
in fattori primi di un numero e dovresti avere una complessità O(n^2).
Però potresti semplicemente esserti espresso male, quindi prova a
postare un po' di codice, così possiamo farci un'idea più chiara.
Ciao, Mox

 ordine di complessità.
Cioè sempre. O parlavi della complessità di scrittura/lettura del codice?
--
Alessandro Monti

 per ovviare a questo problema?
Accetto la sfida...
Il codice che segue minimizza (o almeno queste sono le mie intenzioni)
il numero di confronti del tipo a<b ovvero b<a; in più evita che ad ogni
ciclo
vi sia un doppio confronto con lo zero (cioè per ciascuno dei due termini
'a'
e 'b'), riducendolo ad uno solo (dopo ogni applicazione dell'operatore '%').
Si basa sulla considerazione che se ad un ciclo eseguo l'operazione a%b
al successivo sarà certamente il turno di quella opposta (b%a), fino a
quando si verifichi il succitato (e atteso!) annullamento del termine
correntemente considerato ('a' oppure 'b').
Piccola nota: è necessario un test di uguaglianza a zero per entrambi i
parametri di input prima di entrare nel ciclo. Ma ai fini della complessità
vale una costante (è cioè indipendente dallo specifico input).
L'MCD non è definito per valori nulli: io ho scelto di restituire 0 in
tal caso...
Entrando nel ciclo, è arbitrario iniziare con a%b o b%a, considerando che
se, nel caso che ho scelto, fosse a<b varrebbe a==a%b, come dire
che la _prima_ applicazione dell'operatore di modulo è inutile. Ma da
qualche
parte bisogna pur cominciare. Forse un test iniziale (confronto
variabile-costante, quindi sicuramente più veloce di un '%') gioverebbe alle
prestazioni, ma credo si tratti di una qtà di tempo risparmiata davvero
trascurabile e poi il codice così com'é è _piacevolmente_ corto!! ;-))))
/*a very short MCD function */
int MCD(int a, int b) {
 if(a==0 || b==0) return 0;
 while(a=a%b) if(!(b=b%a)) return a;
 return b;
}
... corto ma soprattutto veloce: fino a un 21% in più rispetto alla tua
funzione
(quella apparsa sul newsgroup in data 29/9)...
