Esame - #3 - 17 Gen 2023

[notedo]

Soluzione Prof

 

[ZGianluigi]

a) Descrizione a parole: L’algoritmo inizia controllando se l’albero è vuoto, se è vuoto, restituisce 1 perché tutti i nodi hanno lo stesso valore. Se l’albero non è vuoto, l’algoritmo controlla se entrambi i figli del nodo radice sono None o se hanno lo stesso valore del nodo radice. Se una di queste condizioni è vera, l’algoritmo continua a chiamare ricorsivamente se stesso sui sottoalberi sinistro e destro. Se entrambe le chiamate ricorsive restituiscono 1, allora l’algoritmo restituisce 1; altrimenti, restituisce 0.

b) Pseudocodice:

def check_equal(p):
    if p is None:
        return 1
    if p.sx is not None and p.sx.val != p.val:
        return 0
    if p.dx is not None and p.dx.val != p.val:
        return 0
    if check_equal(p.sx) and check_equal(p.dx):
        return 1
    else:
        return 0

c) Giustificazione del costo computazionale:

$$T(n) = 2T\left(\frac{n}{2}\right) + O(1)$$

$T\left(\frac{n}{2}\right)$ rappresenta il tempo per processare i due sottoalberi. $O(1)$ rappresenta il tempo per le operazioni non ricorsive (verifica dei valori dei nodi, ecc.).

Utilizzando il Master Theorem, poiché $f(n) = O(1)$, confrontiamo $c$ con $\log_b a$: $c = 0$ $\log_b a = \log_2 2 = 1$

Poiché $c < \log_b a$, abbiamo $T(n) = O(n^{\log_b a})$. Quindi, $T(n) = O(n^1) = O(n)$.

TESTING (modificate i valori e provate come volete)

class Node:
    def __init__(self, val, sx=None, dx=None):
        self.val = val
        self.sx = sx
        self.dx = dx

def check_equal(p):
    if p is None:
        return 1
    if p.sx is not None and p.sx.val != p.val:
        return 0
    if p.dx is not None and p.dx.val != p.val:
        return 0
    if check_equal(p.sx) and check_equal(p.dx):
        return 1
    else:
        return 0

# Creazione di un albero di esempio
root = Node(1)
root.sx = Node(1)
root.dx = Node(1)
root.sx.sx = Node(1)
root.sx.dx = Node(1)

# Verifica se tutti i nodi hanno lo stesso valore
print(check_equal(root))  # Stampa: 1

[rimaout]

Codice:

def es(p):
    if p == None: return 1

    if (p.left != None and p.left.key != p.key) or (p.right != None and p.right.key != p.key):
        return 0

    return es(p.left) * es(p.right)

Costo Computazionale:

[luckignolo32]

def es3(T, i=None)
    if T is None: return 1
    n = 1
    if i == None:
        i = T.key
    if T.key != i: return 0
    if T.left:
        n *= es3(T.left, i)
    if T.right:
        n *= es3(T.right, i)
    return n

[notedo]

True/False e 1/0 sono la stessa cosa

def es3(p):
    sx = False
    dx = False
    if p == None or (p.left == p.right == None):
        return True
    if (p.left and p.left.key == p.key) or p.left == None:
        sx = True and es3(p.left)
    if (p.right and p.right.key == p.key) or p.right == None:
        dx = True and es3(p.right)
    return sx and dx

[alem1105]

def es(t):
    if t == None:
        return 1
    if t.left == t.right == None:
        return 1
    if t.left == None and t.right.key == t.key:
        return es(t.right)
    if t.right == None and t.left.key == t.key:
        return es(t.left)
    if t.key == t.left.key == t.right.key:
        return es(t.left) and es(t.right)
    return 0