2006 – 3

Considerate le seguenti sei funzioni, con argomento N (un intero non negativo).
Ciascuna di esse calcola un qualche valore scelto tra: N, 2N, N², N³, 2^N, N!

Dovete stabilire qual è il valore calcolato da ogni funzione (potrebbero esserci doppioni: più funzioni potrebbero calcolare lo stesso valore; notate inoltre che N! denota il fattoriale di N ed è definito come N! = 1x2x3….xN; quindi 2!=2, 3!=6 e 5!=120; inoltre si assume che 0!=1).

int A(int N)
{
   if(N > 0)
      return 2*A(N-1);
   else
      return 1;
}

int B(int N)
{
   if(N > 0)
      return B(N-1)+2*N-1;
   else
      return 0;
}

int C(int N)
{
   int i, R;
   R=1;
   for(i=0; i < N; i++)
      R=R+R;
   return R;
}

int D(int N)
{
   int i, R;
   R=1;
   for(i=1; i <= N; i++)
      R=R*i;
   return R;
}

Soluzione

• A: 2^N
• B: N²
• C: 2^N
• D: N!

Osserva

      0   1   2   3   4   5
A():  1   2   4   8  16  32
B():  0   1   4   9  16  25
C():  0   2   4   8  16  32
D():  1   1   2   6  24 120

In particolare

• A(5) = 2*A(4) = 2*2*A(3) = 2*2*2*A(2) = 2*2*2*2*A(1) = 2*2*2*2*2*A(0) = 2*2*2*2*2*1 = 32
• B(5) = B(4) +2*5-1 = B(3)+2*4-1+9 = B(2)+2*3-1+7+9 = B(1)+2*2-1+5+7+9 = B(0)+2*1-1+3+5+7+9 = 0+1+3+5+7+9 = 25
• C(5) =
  1. 2*1 = 2
  2. 2*2 = 4
  3. 2*4 = 8
  4. 2*8 = 16
  5. 2*16 = 32
• D(5) =
  1. 1*1 = 1
  2. 2*1 = 2
  3. 3*2 = 6
  4. 4*6 = 24
  5. 5*24 = 120