Esame - #3 - 31 Gen 2023

[notedo]

Soluzione Prof

 

[ZGianluigi]

a) Pseudocodice:

def findNode(p, sum=0):
    # Caso base: se la lista è vuota, ritorna None
    if p is None:
        return None

    # Se il valore del nodo corrente è uguale alla somma corrente, ritorna il nodo
    if p.key == sum:
        return p

    # Altrimenti, aggiorna la somma e continua ricorsivamente con il prossimo nodo
    return findNode(p.next, sum + p.key)

b) Giustificazione :
$$T(n) = T(n-1) + O(1)$$

$T(n-1)$ rappresenta il tempo per processare il prossimo nodo della lista. $O(1)$ rappresenta il tempo per le operazioni non ricorsive (controllo del valore del nodo, aggiornamento della somma, ecc.).

Metodo Iterativo

Partiamo dal caso base $T(0)$, che è una costante. Quindi, il costo di $T(1)$ sarà il costo di $T(0)$ più il costo di un'operazione costante. Il costo di $T(2)$ sarà il costo di $T(1)$ più il costo di un'altra operazione costante, e così via.

Possiamo osservare che ad ogni passo aggiungiamo un costo $O(1)$, quindi il costo totale è la somma dei costi su tutti i livelli.

T(n)=T(n−1)+O(1)=T(n−2)+O(1)+O(1)=⋯=T(0)+n⋅O(1) Dove $T(0)$ è la costante associata al caso base.

Dal momento che sia $T(0)$ che $O(1)$ sono costanti, possiamo semplificare ulteriormente:

$T(n)=O(n)$

Testing:

def findNode(p, sum=0):
    if p is None:
        return None
    if p.key == sum:
        return p
    return findNode(p.next, sum + p.key)

# Creiamo una lista di nodi per il test
class Node:
    def __init__(self, key, next=None):
        self.key = key
        self.next = next

# Creiamo una lista: 1 -> 2 -> 3 -> 6
p = Node(1, Node(2, Node(3, Node(6))))

# Testiamo la funzione
result = findNode(p)
if result:
    print("Trovato nodo con chiave:", result.key)
else:
    print("Nessun nodo trovato")

Trovato nodo con valore: 3

[luckignolo32]

def es3(p, s=0):
    if p is None: return None
    if p.key == s: return p.key
    return es3(p.next, s + p.key)

[rimaout]

[alem1105]

def es(p, somma = 0):
    if p == None:
        return None
    if somma == p.key:
        return p
    es(p.next, somma + p.key)