Anno 2021 – 8
Considera la seguente funzione
function x(n)
{
if(n <= 0)
return 0
return 1+y(n-2)
}
function y(n)
{
if(n <= 0)
return 0
return 2+x(n-3)
}
Quale numero ritorna la chiamata a y(100)?
SOLUZIONE 1
| n | x(n) | y(n) |
|---|---|---|
| -2 | 0 | 0 |
| -1 | 0 | 0 |
| 0 | 0 | 0 |
| 1 | 1+y(-1) = 1 | 2+x(-2) = 2 |
| 2 | 1+y(0) = 1 | 2+x(-1) = 2 |
| 3 | 1+y(1) = 3 | 2+x(0) = 2 |
| 4 | 1+y(2) = 3 | 2+x(1) = 3 |
| 5 | 1+y(3) = 3 | 2+x(2) = 3 |
| 6 | 1+y(4) = 4 | 2+x(3) = 5 |
| — | — | — |
| 100 | 1+y(98) | 2+x(97) |
SOLUZIONE 2
Osserva
- x(n) = 1+y(n-2) = 1+(2+x((n-2)-3)) = 3+x(n-5), n >= 5
- y(n) = 2+x(n-3) = 2+(1+y((n-3)-2)) = 3+y(n-5), n >= 5
- y(100) = 3+y(95) = 6+y(90) = 9+y(85) = … = 3*(i)+y(100-5*i) = … = 3*20+y(100-5*20) = 60+y(0) = 60
Anno 2021 – 9
Data la seguente funzione:
function f(a, b)
{
if(b == 0)
return a
if(b > 0)
return 1 + f(a, b-1)
return f(a, b+1) - 1
}
Cosa calcola f(a, b)?
SOLUZIONE
| a | b | … | f(a, b) |
|---|---|---|---|
| 0 | 0 | 0 | |
| 0 | 1 | 1+f(0, 0) | 1 |
| 1 | 0 | 1 | |
| 0 | 2 | 1+f(0, 1) = 1+1+f(0, 0) = 2+0 | 2 |
| 1 | 1 | 1+f(1, 0) = 1+1 | 2 |
| 2 | 0 | 2 | |
| … | … | ||
| a | b | b+f(a, 0) = b+a | a+b |
Anno 2021 – 11
Data la seguente funzione:
function f(n)
{
if(n < 4)
{
return 1
}
return 2*f(n-1) - 3*f(n-2) + 1*f(n-1)
}
Cosa ritorna la chiamata a f(82)?
SOLUZIONE
| n | 3 [f(n-1) – f(n-2)] | f(n) |
|---|---|---|
| 0 | 1 | |
| 1 | 1 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 3*[f(3)-f(2)] = 3*[1-1] = 3*0 | 0 |
| 5 | 3*[f(4)-f(3)] = 3[0-1] = 3*(-1) | -3 |
| 6 | 3*[f(5)-f(4)] = 3*[-3-0] = 3*(-3) | -9 |
| 7 | 3*[f(6)-f(5)] = 3*[-9+3] = 3*(-6) | -18 |
| 8 | 3*[f(7)-f(6)] = 3*[-18+9] = 3*(-9) | -27 |
| 9 | 3*[f(8)-f(7)] = 3*[-27+18] = 3*(-9) | -27 |
| 10 | 3*[f(9)-f(8)] = 3*[-27+27] = 3*(0) | 0 |
f(4) = 3(1-1) = 0
f(10) = 3*f(9)-3*f(8) = 9*f(8)-9*f(7)-3*f(8) = 6*f(8)-9*f(7) = 18*f(7)-18*f(6)-9*f(7) = 9*f(7)-18*f(6) = 27*f(6)-27*f(5)-18*f(6) = 9*f(6)-27*f(5) = 27*f(5)-27*f(4)-27*f(5) = -27*f(4) = 0
f(16) = … = -27*f(10) = 0
f(82) = f(4+13*6) = 0
…
SOLUZIONE
…