2007 – 3

di

Si consideri la seguente funzione

int ES3(int x)
{
    if(x <= 1)
        return 0;
    else
        return 1+ES3(x/2);
}

Dire cosa restituisce l'invocazione ES3(10).

Risposte:

  1. 1
  2. 2
  3. 3
  4. nessuna delle precedenti

Soluzione: c (3)

Osserva

  • ES3(10)
    • (10 <= 1)? No, 1+ES3(5) = 1+2 = 3
  • ES3(5)
    • (5 <= 1)? No, 1+ES3(2) = 1+1 = 2
  • ES3(2)
    • (2 <= 1)? No 1+ES3(1) = 1+0 = 1
  • ES3(1): (1 <= 1)? Sì 0

Alternativamente

  1. ES3(1) = 0
  2. ES3(2) = 1+ES3(1) = 1+0 = 1
  3. ES3(3) = 1+ES3(1) = 1+0 = 1
  4. ES3(4) = 1+ES3(2) = 1+1 = 2
  5. ES3(5) = 1+ES3(2) = 1+1 = 2
  6. ES3(6) = 1+ES3(3) = 1+1 = 2
  7. ES3(7) = 1+ES3(3) = 1+1 = 2
  8. ES3(8) = 1+ES3(4) = 1+2 = 3
  9. ES3(9) = 1+ES3(4) = 1+2 = 3
  10. ES3(10) = 1+ES3(5) = 1+2 = 3
  11. ...

La funzione restituisce l'esponente più grande al quale elevare 2 senza superare x (la parte intera del logaritmo in base 2)