2003 – 5

Si consideri la seguente funzione:

int A(int n, int m)
{
   if(n == 0)
      return 1;
   else
      if(n%2 == 0)
         return A(n/2,m)*A(n/2,m);
      else
         return m*A(n-1,m);
}

Dire quale sarà il valore tornato dalle chiamate

  1. A(3,2)
  2. A(4,3)
  3. A(5,4)

Soluzione: 8, 81, 1024.


Prova…

  0 1  2   3    4
0 1 1  1   1    1
1 0 1  2   3    4
2 0 1  4   9   16
3 0 1  8  27   64
4 0 1 16  81  256
5 0 1 32 243 1024

Osserva

  • n=0: 1
  • n=1: m*A(0,m) = m*1 = m
  • n=2: A(1,m)*A(1,m) = m*m = m2
  • n=3: m*A(2,m) = m*m2 = m3
  • n=4: A(2,m)*A(2,m) = m2*m2 = m4
  • n=5: m*A(4,m) = m*m4 = m5

Quindi

A(n,m) = mn