OLICYBER e Pseudocodice


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

n12345678910
x(n)1133344666
y(n)2223355566
n11121314151617181920
x(n)779991010121212
y(n)888991111111212

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

abf(a, b)
000
011+f(0, 0)1
101
021+f(0, 1) = 1+1+f(0, 0) = 2+02
111+f(1, 0) = 1+12
202
abb+f(a, 0) = b+aa+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

n3 [f(n-1) – f(n-2)]f(n)
01
11
21
31
43*[f(3)-f(2)] = 3*[1-1] = 3*00
53*[f(4)-f(3)] = 3[0-1] = 3*(-1)-3
63*[f(5)-f(4)] = 3*[-3-0] = 3*(-3)-9
73*[f(6)-f(5)] = 3*[-9+3] = 3*(-6)-18
83*[f(7)-f(6)] = 3*[-18+9] = 3*(-9)-27
93*[f(8)-f(7)] = 3*[-27+18] = 3*(-9)-27
103*[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