promotion image of download ymail app
Promoted

Qual è il costo (teta) per calcolare 2^n usando la ricorsione in Java? Grazie?

3 risposte

Classificazione
  • 2 mesi fa
    Risposta preferita

    Con l'algoritmo "semplice" siamo a Θ(n-1) cioè asintoticamente Θ(n), visto che si devono effettuare n-1 moltiplicazioni. 

    Con un algoritmo efficiente siamo a O(log n), per la theta vedi Teorema Principale dell'analisi degli algoritmi.

    • Commenter avatarAccedi per rispondere alle risposte
  • exProf
    Lv 7
    2 mesi fa

    PRECONDIZIONE: n intero non negativo

    cioè

    n non intero → errore

    n < 0 → 1/dueAllaN(- n)

    ---------------

    dueAllaN(n)

    n = 0 → 1

    n = 1 → 2

    n pari → dueAllaN(rightShift(n)) * dueAllaN(rightShift(n))

    n dispari → leftShift(dueAllaN(pred(n)))

    ------------------------------

    Non so dirti come stimare con precisione Θ(*) [Theta grande]: non vedo differenze sostanziali fra il caso ottimo e il caso pessimo.

    I dati per la stima di O(*) [O grande] dell'algoritmo astratto sono i seguenti: poi come effettuare il calcolo che richiedi tu ("usando la ricorsione in Java") dipende dai particolari tecnici dell'implementazione che usi.

    ------------------------------

    A) Scrivere il numerale binario di n

    B) Contare gli zeri e gli uni

    C1) Per ogni uno:

    * due operazioni additive (left shift e predecessore)

    * una ricorsione.

    C2) Per ogni zero:

    * due operazioni additive (right shift)

    * un'operazione moltiplicativa (moltiplicazione)

    * due ricorsioni.

    C3) Per ogni ricorsione:

    * tre operazioni additive (i confronti: di test di parità ne basta uno)

    * zero o uno salti.

    • Commenter avatarAccedi per rispondere alle risposte
  • Anonimo
    2 mesi fa

    Non lo so, vedi tu, questo è in C:

    #include <stdio.h>

    int duen(int);

    main()

    {

        int n;

        printf("\nInserisci n: ");

        scanf("%d",&n);

        printf("%d",duen(n));

    }

    int duen(int d) // funzione ricorsiva per il calcolo di 2^n

    {

        if(d==0)

         return 1;

        else

         return 2*duen(d-1);

    }

    • Commenter avatarAccedi per rispondere alle risposte
Altre domande? Fai una domanda e ottieni le risposte che cerchi.