2014 – 7

di

Si consideri la seguente funzione, che viene chiamata con n >= k >= 1.

int f(int n, int k) 
{
   if(n == k || k == 0)
      return 1;
   else
      return f(n-1, k-1)+f(n-1, k);
}

Quale tra le seguenti espressioni viene calcolata dalla funzione f?

Si ricordi che

  • nk
  • n! è il fattoriale di n (cioè il prodotto dei numeri interi positivi da 1 a n, ovvero 1×2×3×…×n).
  1. nk0
  2. n-1k
  3. nk-1
  4. n-1k-1

Soluzione: a, nk0.

I valori di nk0 sono

     0  1  2  3  4  5  ...
  0  1
  1  1  1
  2  1  2  1
  3  1  3  3  1
  4  1  4  6  4  1
  5  1  5 10 10  5  1
...  ...

I valori di f(n, k) sono

  • f(0, 0) = 1, f(1, 0) = 1, f(2, 0) = 1,  …, cioè f(n, 0) = 1
  • f(1,1) = 1, f(2,2) = 1, …, cioè f(n,n) = 1
  • f(2,1) = f(1,0)+f(1,1) = 1+1 = 2
  • f(3,1) = f(2,0)+f(2,1) = 1+2 = 3
  • f(3,2) = f(2,1)+f(2,2) = 2+1 = 3
  • …

Si ottiene la stessa tabella…

     0  1  2  3  4  5  ...
  0  1
  1  1  1
  2  1  2  1
  3  1  3  3  1
  4  1  .......  1
  5  1  ..........  1
...  ...