Minimo comune multiplo con ricorsione

di
JosAm93
il
18 risposte

18 Risposte - Pagina 2

  • CarDeFusco
    CarDeFusco
    Utente Attivo
    Iscritto da
    feb, 2016
    Messaggi:
    220

    Re: Minimo comune multiplo con ricorsione

    JosAm93 ha scritto:

    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?
    Si che c'è.
  • J
    JosAm93
    Pochi posts
    Iscritto da
    ott, 2016
    Messaggi:
    20

    Re: Minimo comune multiplo con ricorsione

    CarDeFusco ha scritto:

    JosAm93 ha scritto:

    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?
    Si che c'è.
    In che modo posso trasformare il codice che ho implementato per il mcm, senza usare il MCD, utilizzando la ricorsione? Riposto il codice precedente: 
    
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;
    }
}
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6051

    Re: Minimo comune multiplo con ricorsione

    Parti da questo fatto:

    qualunque cosa che viene fatta in modo iterativo, puo' essere fatta in modo ricorsivo.

    Ora comincia con cose semplici:

    coverti in ricorsivo un semplice ciclo che stampa il valore dell'indice.

    Attenzione: mentre mediante il ciclo for stampi "1,2,...N-1,N"

    molto probabilmente nella tua implementazione ricorsiva stamperai "N, N-1,...,2,1"

    quindi attento

    Una volta fatto questo, puoi convertire la tua implementazione del mcm in forma ricorsiva.

    Comunque, la tua implementazione e' MOSTRUOSAMENTE INEFFICENTE!!!!!!
  • J
    JosAm93
    Pochi posts
    Iscritto da
    ott, 2016
    Messaggi:
    20

    Re: Minimo comune multiplo con ricorsione

    migliorabile ha scritto:

    Parti da questo fatto:

    qualunque cosa che viene fatta in modo iterativo, puo' essere fatta in modo ricorsivo.

    Ora comincia con cose semplici:

    coverti in ricorsivo un semplice ciclo che stampa il valore dell'indice.

    Attenzione: mentre mediante il ciclo for stampi "1,2,...N-1,N"

    molto probabilmente nella tua implementazione ricorsiva stamperai "N, N-1,...,2,1"

    quindi attento

    Una volta fatto questo, puoi convertire la tua implementazione del mcm in forma ricorsiva.

    Comunque, la tua implementazione e' MOSTRUOSAMENTE INEFFICENTE!!!!!!
    L'idea di fondo che ho implementato è questa: per calcolare il minimo comune multiplo tra 2 numeri (per esempio tra 6 e 8 ) controllo prima che uno sia diviso interamente dall'altro (sia da a sia da b), se non si verificano queste 2 condizioni allora moltiplico il primo ad ogni ciclo fin quando la divisione tra a e b diviene senza resto (in questo caso 6...12...18...24, 24/8=3 con resto 0).
    Poiché la mia implementazione è MOSTRUOSAMENTE INEFFIC(I)ENTE, come si può rendere efficiente?
Devi accedere o registrarti per scrivere nel forum
18 risposte