Minimo comune multiplo con ricorsione

di il
18 risposte

Minimo comune multiplo con ricorsione

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

  • Re: Minimo comune multiplo con ricorsione

    Credo proprio di no...
  • Re: Minimo comune multiplo con ricorsione

    CarDeFusco ha scritto:


    Credo proprio di no...
    Che problemi hai riscontrato nel codice?
  • Re: Minimo comune multiplo con ricorsione

    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...
  • Re: Minimo comune multiplo con ricorsione

    Ho testato il programma ma in alcuni casi non funziona: posso risolvere il problema utilizzando sempre la ricorsione o in altro modo?
  • Re: Minimo comune multiplo con ricorsione

    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.
  • Re: Minimo comune multiplo con ricorsione

    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;
        }
    }
    
  • Re: Minimo comune multiplo con ricorsione

    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.
  • Re: Minimo comune multiplo con ricorsione

    Adesso come potrei implementare il minimo comune multiplo attraverso la ricorsione?
  • Re: Minimo comune multiplo con ricorsione

    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
  • Re: Minimo comune multiplo con ricorsione

    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)?
  • Re: Minimo comune multiplo con ricorsione

    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'.
  • Re: Minimo comune multiplo con ricorsione

    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?
  • Re: Minimo comune multiplo con ricorsione

    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.
  • Re: Minimo comune multiplo con ricorsione

    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