Minimo comune multiplo con ricorsione

di Anonimizzato20161 il
18 risposte
/
Anonimizzato20161
Utente anonimizzato
Buonasera a tutti,
ho implementato un metodo per il calcolo del minimo comune multiplo tra 2 numeri, è corretto?

int mcm(int a, int b)
{
    int i=1;

    if (a%b == 0) return a;
    else if (b%a == 0) return b;
    else
    {
        i++;
        return mcm(a*i, b);
        }
}

18 Risposte

  • /
    Anonimizzato19069
    Utente anonimizzato
    Credo proprio di no...
  • /
    Anonimizzato20161
    Utente anonimizzato

    CarDeFusco ha scritto:

    Credo proprio di no...
    Che problemi hai riscontrato nel codice?
  • /
    Anonimizzato19069
    Utente anonimizzato

    JosAm93 ha scritto:

    CarDeFusco ha scritto:

    Credo proprio di no...
    Che problemi hai riscontrato nel codice?
    Non funziona, hai provato ad eseguirlo ? Prima di chiedere se è corretto potresti verificarlo già tu testandolo...
  • /
    Anonimizzato20161
    Utente anonimizzato
    Ho testato il programma ma in alcuni casi non funziona: posso risolvere il problema utilizzando sempre la ricorsione o in altro modo?
  • /
    Anonimizzato19069
    Utente anonimizzato

    JosAm93 ha scritto:

    Ho testato il programma ma in alcuni casi non funziona: posso risolvere il problema utilizzando sempre la ricorsione o in altro modo?
    Puoi provare entrambe le strade, sia con la ricorsione che attraverso la iterazione.
  • /
    Anonimizzato20161
    Utente anonimizzato

    CarDeFusco ha scritto:

    JosAm93 ha scritto:

    Ho testato il programma ma in alcuni casi non funziona: posso risolvere il problema utilizzando sempre la ricorsione o in altro modo?
    Puoi provare entrambe le strade, sia con la ricorsione che attraverso la iterazione.
    Ho modificato il metodo in questa maniera, senza ricorsione: funziona correttamente adesso?
    
int mcm(int a, int b)
{
    int c=a;
    
    for (int i=1; i < a*b; i++)
    {
        if (a%b == 0) return a;
        else if (b%a == 0) return b;
        else
            a += c;
    }
}
  • /
    Anonimizzato19069
    Utente anonimizzato

    JosAm93 ha scritto:

    CarDeFusco ha scritto:

    JosAm93 ha scritto:

    Ho testato il programma ma in alcuni casi non funziona: posso risolvere il problema utilizzando sempre la ricorsione o in altro modo?
    Puoi provare entrambe le strade, sia con la ricorsione che attraverso la iterazione.
    Ho modificato il metodo in questa maniera, senza ricorsione: funziona correttamente adesso?
    
int mcm(int a, int b)
{
    int c=a;
    
    for (int i=1; i < a*b; i++)
    {
        if (a%b == 0) return a;
        else if (b%a == 0) return b;
        else
            a += c;
    }
}
    Si ora sembra andare bene.
  • /
    Anonimizzato20161
    Utente anonimizzato
    Adesso come potrei implementare il minimo comune multiplo attraverso la ricorsione?
  • Super Famoso
    Iscritto da
    apr, 2013
    Messaggi
    6268
    Stai facendo pasticci, e non stai sfruttando le proprieta' del mcm e della sua CONTROPARTE, il mcd/gcd (massimo comun divisore).

    Intanto: a*b = mcm(a,b)*gcd(a,b).

    Ora, ti serve una definizione ricorsiva dell'mcm OPPURE del gcd!

    Ragionaci un po' e ci arrivj
  • /
    Anonimizzato20161
    Utente anonimizzato

    migliorabile ha scritto:

    Stai facendo pasticci, e non stai sfruttando le proprieta' del mcm e della sua CONTROPARTE, il mcd/gcd (massimo comun divisore).

    Intanto: a*b = mcm(a,b)*gcd(a,b).

    Ora, ti serve una definizione ricorsiva dell'mcm OPPURE del gcd!

    Ragionaci un po' e ci arrivj
    Precedentemente avevo realizzato il MCD in modo ricorsivo: lo devo utilizzare per il mcm? In base alla formula che mi hai indicato potrei calcolare il mcm facendo il rapporto (a*b)/MCD(a,b)?
  • /
    Anonimizzato19069
    Utente anonimizzato

    JosAm93 ha scritto:

    migliorabile ha scritto:

    Stai facendo pasticci, e non stai sfruttando le proprieta' del mcm e della sua CONTROPARTE, il mcd/gcd (massimo comun divisore).

    Intanto: a*b = mcm(a,b)*gcd(a,b).

    Ora, ti serve una definizione ricorsiva dell'mcm OPPURE del gcd!

    Ragionaci un po' e ci arrivj
    Precedentemente avevo realizzato il MCD in modo ricorsivo: lo devo utilizzare per il mcm? In base alla formula che mi hai indicato potrei calcolare il mcm facendo il rapporto (a*b)/MCD(a,b)?
    Implementa ricorsivamente la gcd(a,b) e poi usi la formula per avere mcm(a,b).

    Come ti diceva migliorabile data una forma ricorsiva di uno dei due, ad esempio di gcd, il grosso è fatto. Non è difficile da trovare la definizione ricorsiva, basta googlare un po'.
  • /
    Anonimizzato20161
    Utente anonimizzato

    CarDeFusco ha scritto:

    JosAm93 ha scritto:

    migliorabile ha scritto:

    Stai facendo pasticci, e non stai sfruttando le proprieta' del mcm e della sua CONTROPARTE, il mcd/gcd (massimo comun divisore).

    Intanto: a*b = mcm(a,b)*gcd(a,b).

    Ora, ti serve una definizione ricorsiva dell'mcm OPPURE del gcd!

    Ragionaci un po' e ci arrivj
    Precedentemente avevo realizzato il MCD in modo ricorsivo: lo devo utilizzare per il mcm? In base alla formula che mi hai indicato potrei calcolare il mcm facendo il rapporto (a*b)/MCD(a,b)?
    Implementa ricorsivamente la gcd(a,b) e poi usi la formula per avere mcm(a,b).

    Come ti diceva migliorabile data una forma ricorsiva di uno dei due, ad esempio di gcd, il grosso è fatto. Non è difficile da trovare la definizione ricorsiva, basta googlare un po'.
    Il metodo che ho implementato per calcolare il MCD è questo: 
    
int mcd(int a, int b)
{
    if (b == 0) return a;
        else return mcd(b, a%b);
}
    Mentre il mcm l'ho implementato in questo modo: 
    
int mcm(int a, int b)
{
    return a*b/mcd(a,b);
}
    Sono corrette le implementazioni?
  • /
    Anonimizzato19069
    Utente anonimizzato

    JosAm93 ha scritto:

    CarDeFusco ha scritto:

    JosAm93 ha scritto:

    Precedentemente avevo realizzato il MCD in modo ricorsivo: lo devo utilizzare per il mcm? In base alla formula che mi hai indicato potrei calcolare il mcm facendo il rapporto (a*b)/MCD(a,b)?
    Implementa ricorsivamente la gcd(a,b) e poi usi la formula per avere mcm(a,b).

    Come ti diceva migliorabile data una forma ricorsiva di uno dei due, ad esempio di gcd, il grosso è fatto. Non è difficile da trovare la definizione ricorsiva, basta googlare un po'.
    Il metodo che ho implementato per calcolare il MCD è questo: 
    
int mcd(int a, int b)
{
    if (b == 0) return a;
        else return mcd(b, a%b);
}
    Mentre il mcm l'ho implementato in questo modo: 
    
int mcm(int a, int b)
{
    return a*b/mcd(a,b);
}
    Sono corrette le implementazioni?
    Si dovrebbe andare. A quanto vedo hai usato .

    EDIT : Un consiglio invece di mcd, per il massimo comun divisore, scrivi gcd è più leggibile, a prima vista ho confuso mcm con mcd.
  • /
    Anonimizzato20161
    Utente anonimizzato
    Sì ho utilizzato il metodo euclideo, di cui non conoscevo l'esistenza, scoperto in questa occasione. C'è un modo per implementare il mcm in modo ricorsivo senza utilizzare il MCD?
Devi accedere o registrarti per scrivere nel forum
18 risposte