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 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
x(n) | 1 | 1 | 3 | 3 | 3 | 4 | 4 | 6 | 6 | 6 |
y(n) | 2 | 2 | 2 | 3 | 3 | 5 | 5 | 5 | 6 | 6 |
n | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
x(n) | 7 | 7 | 9 | 9 | 9 | 10 | 10 | 12 | 12 | 12 |
y(n) | 8 | 8 | 8 | 9 | 9 | 11 | 11 | 11 | 12 | 12 |
6 -> 12 -> 18 -> 24 -> 30 -> 36 -> 42 -> 48 -> 52 -> 60
SOLUZIONE 2
Per n=5m: y(n) = 2+x(n-3) = 2+1+y(n-3-2) = 3+y(n-5)
y(100) = 3+y(95) = 6+y(90) = 9+y(85) = … = 3*20 +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)
}
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)=0, …, f(10)=0, …, f(16)=0, …, f(4+18*6)=f(82)=0
…
SOLUZIONE
…