Soluzioni del compito del 9/7/2008

Soluzione per gli esercizi 2, 3 e 5

Il testo chiede di determinare l'output del seguente programma Python:

def f(x,y):
        return x+y*2
 
def g(x,y=[1]):
        return x>y
 
a=[1,2]
b=['a','b']
 
print g(f(a,b))
print f(b,a)
print g(f(a,b),f(b,a))
 
def h(y):
        def f(x):
                return x+y
        return f
 
f=h(a)
print f(b)

La risposta corretta e':

 True
 ['a', 'b', 1, 2, 1, 2]
 False
 ['a', 'b', 1, 2]

Bisogna infatti ricordare che l'operazione di confronto si applica fra liste di qualunque lunghezza, e l'operatore * applicato ad una lista ed un numero intero n restituisce una nuova lista pari alla lista originale replicata n volte. Per seconda parte, la funzione f=h(x) esegue la somma (o la concatenazione, nel caso delle liste) fra x e l'argomento di f.

Gli ultimi due casi si risolvono applicando il teorema maestro. Il primo si svolge considerando che T(n) = T(n-3) + lg n = lg n + lg n-3 + lg n-6 … = Θ(n lg n).

Se l'albero, per essere valido, deve avere in ogni nodo un'etichetta pari alla somma delle etichette nei sottoalberi, allora e' anche vero che in ogni nodo l'etichetta deve essere pari al doppio della somma delle etichette dei figli (a meno che i figli non siano foglie). Di conseguenza, si puo' scrivere una soluzione (in Python) in questo modo:

def check(node):
        if node.isLeaf() :
                return True
        sum = 0
        for c in node.children :
                if c.isLeaf() :
                        sum+=c.value
                else :
                        sum+=c.value*2
        if sum != node.value :
                return False
        return reduce(lambda x, y: x and y, [ check(c) for c in node.children ], 1)

La complessita' di questa soluzione e' O(n) nel numero dei nodi.