Esercizio 27C, resistenza equivalente di un circuito (albero)

Richiami

Alberi in C e visite ricorsive: Alberi e heap in CAlbero binario in C con nodo struct e figli left/right; funzioni ricorsive (conteggio, altezza, visita inorder, liberazione in postorder); inserimento in un albero binario di ricerca con Nodo **; min-heap su array con indici da 1 (insert, removeMin, bottomUp).Alberi e heap in C →. Le formule fisiche sono quelle di Teoria dei Circuiti (Resistenza equivalente e trasformazione stella-triangoloUna rete di soli resistori passivi vista da due morsetti A e B equivale a un unico resistore R_eq. Si calcola riducendo la rete con serie e parallelo, partendo dalla parte più lontana dai morsetti. Quando serie e parallelo non bastano (ponti), si usa la trasformazione triangolo→stella (R_A = R_AB·R_CA / somma) o stella→triangolo (R_AB = (R_A R_B + R_B R_C + R_C R_A)/R_C). Con tre resistori uguali R_Δ = 3 R_Y.Resistenza equivalente e trasformazione stella-triangolo →, Leggi di Kirchhoff (LKC e LKT)LKC: in ogni istante la somma algebrica delle correnti che attraversano una superficie chiusa (per esempio attorno a un nodo) è zero. LKT: in ogni istante la somma algebrica delle tensioni lungo un percorso chiuso che tocca solo nodi (per esempio una maglia) è zero. Dipendono solo da come sono collegati i componenti.Leggi di Kirchhoff (LKC e LKT) →): in serie le resistenze si sommano, $R=a+b$, perché la stessa corrente le attraversa e le tensioni si sommano; in parallelo si sommano le conduttanze, $\frac1R=\frac1a+\frac1b$, da cui $R=\frac{ab}{a+b}$ (si porta a denominatore comune: $\frac1a+\frac1b=\frac{b+a}{ab}$ e si inverte). Valutazione di un albero binario proprio con una visita in postorder: il valore di un nodo interno dipende dai valori dei figli (vedi Alberi binariAlbero binario e albero binario proprio; interfaccia; relazioni tra nodi, foglie e altezza (m = n-m+1, h+1 <= m <= 2^h, 2h+1 <= n <= 2^(h+1)-1) con dimostrazioni; visita inorder; parse tree e valutazione di espressioni; heightSum come esempio di calcolo di un'informazione più ricca.Alberi binari →, analogo alla valutazione di un'espressione).

Soluzione

double combinaResistenze(double a, double b, TipoNodo tipo) {
    if (tipo == SERIE)
        return a + b;
    return (a * b) / (a + b);          /* PARALLELO */
}

double resistenzaEquivalente(Circuito *root) {
    if (root == NULL)
        return 0.0;
    if (root->tipo == RESISTORE)
        return root->valore;
    double a = resistenzaEquivalente(root->left);
    double b = resistenzaEquivalente(root->right);
    return combinaResistenze(a, b, root->tipo);
}

int contaResistori(Circuito *root) {
    if (root == NULL)
        return 0;
    if (root->tipo == RESISTORE)
        return 1;
    return contaResistori(root->left) + contaResistori(root->right);
}

Traccia di resistenzaEquivalente sull'esempio del testo (radice SERIE, figli: resistenza $100$ e PARALLELO con due resistenze da $200$): la chiamata sulla radice richiama la sinistra, che è un RESISTORE e restituisce $100$; poi la destra, che richiama le sue due foglie ($200$ e $200$) e restituisce combinaResistenze(200, 200, PARALLELO) $=\frac{200\cdot200}{400}=100$; infine la radice restituisce combinaResistenze(100, 100, SERIE) $=200$. contaResistori conta le tre foglie: $1+(1+1)=3$.

Struttura. Entrambe le funzioni sono visite ricorsive: caso base NULL (e foglia = RESISTORE), poi si combinano i risultati dei due figli. resistenzaEquivalente è un postorder in cui la "visita" è combinaResistenze. Complessità $\Theta(n)$ tempo (una chiamata per nodo) e $O(h)$ stack.

Dettagli.

• Per $a + b = 0$ il parallelo divide per zero: nei circuiti dei test le resistenze sono positive, quindi non succede. Con un ramo in cortocircuito ($a = 0$) la formula darebbe $0/b = 0$, corretta.
• Il parallelo di due resistenze è sempre minore della minore delle due: $\frac{ab}{a+b}<a$ se $b<a+b$, cioè sempre per $b>0$; in particolare $100\parallel100=50$ e $50\parallel 200=40$. Per $a=b$ vale $\frac a2$ (resistenze uguali in parallelo). Il risultato è un double, quindi può avere errori di arrotondamento (Numeri in virgola mobile IEEE 754Virgola fissa e virgola mobile; formato IEEE 754 a 32 e 64 bit (segno, esponente in eccesso 127, mantissa con 1 implicito); conversioni svolte nei due versi; valori speciali, denormalizzati, intervallo, precisione e arrotondamento.Numeri in virgola mobile IEEE 754 →), irrilevanti per un test con tolleranza.
• Si usano double e non int: $(a b)/(a + b)$ in aritmetica intera troncherebbe il risultato.
• Si controlla root->tipo per distinguere foglia e nodo interno, senza guardare i figli: nelle foglie sono NULL, ma è il tipo a definire il significato del nodo.

Prove eseguite

(Controllo: $(10 \parallel 10) = 5$ e $5 \parallel 10 = \frac{50}{15} = 3{,}333\dots$; combinaResistenze(3, 6, SERIE) $= 9$, combinaResistenze(3, 6, PARALLELO) $= 2$. Provato compilando con gcc -std=c99.)

Errori comuni

• Usare la divisione tra interi (int a, b) o dimenticare la parentesi in (a * b) / (a + b).
• Dimenticare il caso RESISTORE e richiamarsi ricorsivamente sui figli NULL (non rompe, ma combinaResistenze verrebbe chiamata con tipo RESISTORE e darebbe un risultato errato).
• Contare i nodi interni invece delle foglie in contaResistori: i resistori sono le foglie (in un albero proprio sono $m = (n - m) + 1$, vedi Alberi binariAlbero binario e albero binario proprio; interfaccia; relazioni tra nodi, foglie e altezza (m = n-m+1, h+1 <= m <= 2^h, 2h+1 <= n <= 2^(h+1)-1) con dimostrazioni; visita inorder; parse tree e valutazione di espressioni; heightSum come esempio di calcolo di un'informazione più ricca.Alberi binari →).
• Confondere serie e parallelo: la serie somma, il parallelo ha la resistenza equivalente minore di ciascun ramo.