[Algoritmi]Chiarimento esercizi divide et impera

[Skeggia1]

Ciao a tutti!
Ho difficoltà a svolgere questi esercizi:
1-
Sia dato un albero binario T con puntatore alla radice z. Si scriva un algoritmo basato sulla tecnica Divide et Impera che calcoli la quantita: $sum_{x:x è una foglia di T} d_T(X)$
dove $d_T(X)$ è la distanza (ovvero il livello) della foglia x dalla radice di T .

Cioè non riesco a capire come posso calcolare $d_T(X)$??

2-
Sia dato un albero binario T con puntatore alla radice z. Per ogni nodo x dell’albero vale che $key[x] in {0, 1}$. Si scriva un algoritmo basato sulla tecnica Divide et Impera che calcoli lo XOR (ovvero l’OR esclusivo) dei valori key[x].

Per questo esercizio, la mia difficoltà è capire come calcolare l'XOR. Supponiamo che come caso base metto che quando ho una foglia mi faccio restituire il valore key e lo metto poi in XOR con il nodo padre. Però se quest'ultimo ha un'altro figlio come lo calcolo lo XOR. Ciò è un po' difficile da spiegare, ma non riesco a capire come devo muovermi.

Se qualcuno è così gentile da riuscire a chiarirmi queste tracce gliene sono grato. Grazie.

[apatriarca]

1. Prova a pensare a come calcolare quella quantità quando l'albero è vuoto, la radice è una foglia e infine per l'albero generale in funzione del valore della funzione sugli alberi figli.

2. Non c'è alcuna ragione per cui tu non possa fare lo xor di tre valori. Non ha alcuna importanza l'ordine in cui effettui le operazioni, esattamente come accadrebbe per la somma o il prodotto di numeri.

[Skeggia1]

Ciao e grazie.
1.Per il primo ho buttato giù questo pseudocodice: inizilmente viene passato n=0;

Algo1(z,n)
//Se l'albero è vuoto
if z = NIL then return 0
//se z punta ad una foglia
if (left[z] = NIL) AND (right=NIL) then
   return n
//divide
a<- Algo1(left[z],n+1)
b<-Algo2(right[z],n+1)
//impera
return (a+b)

Vorrei evitare di usare quella n, ma non riesco a trovare un modo migliore.

2.Mentre per il secondo:

Algo2(z)
if z = NIL then return 0
else
  a<-Algo2(left[z])
  b<-Algo2(right[z])
  return key[z] XOR a XOR b

Questo credo che non sia corretto ma al moment non riesco a migliorarlo.
Cosa ne pensi?
Grazie mille.

[apatriarca]

Nel primo esercizio non mi vengono in mente metodi che non richiedano il passaggio di \(n\) come argomento oppure un secondo valore di ritorno dalle funzioni. E' possibile esista un modo per reinterpretare il problema diversamente, ma al momento non lo vedo.

Il secondo esercizio mi sembra invece corretto, perché pensi che non lo sia?

[Skeggia1]

Ok per il primo. Il secondo, a differenza del primo, non avevo effettuato il test (l'ho scritto direttamente qui sul forum) e non ero sicuro che a e b facevano riferimento alle key del nodo. Comunque, proseguendo con gli esercizi ho incontrato quest'altro:
< >= 2$. Provare che ogni vettore A di $n >= 2$ interi per cui $A[n] − A[1] >= n$ possiede almeno un salto. Progettare un algoritmo che, dato un vettore A di $n >= 2$ interi per cui $A[n] − A[1] >= n$, trovi un salto in $O(log n)$ tempo.>>
Se $n=2$ allora per ipotesi $A[n] − A[1] >= n$ ovvero $A[2]-A[1] >=2$ quindi contiene un salto. Ma non riesco ad approcciare bene questa prova, che credo sia fondamentale per svolgere l'altro punto. Riusciresti a darmi una dritta?
Ti ringrazio molto.

[apatriarca]

Considera il vettore \(B\) di \(n-1\) interi definito da \( B = A[i+1] - A. \) Abbiamo che se c'è un salto in \(i\) allora \( B \geq 2 \) e si ha la relazione \( \sum_{i = 1}^{n-1} B = A[n] - A[1]. \) Supponiamo allora che valga \( \sum_{i = 1}^{n-1} B \geq n \) e che non ci siano salti. Abbiamo quindi che \(1 \geq B\) e quindi
\[ n > n-1 = \sum_{i = 1}^{n-1} 1 \geq \sum_{i = 1}^{n-1} B = A[n] - A[1] \geq n. \]
Siamo quindi arrivati ad una contraddizione e possiamo allora dire che ci deve essere almeno un salto.

[Skeggia1]

"apatriarca":Considera il vettore \(B\) di \(n-1\) interi definito da \( B\[i\] = A[i+1] - A. \) Abbiamo che se c'è un salto in \(i\) allora \( B \geq 2 \) e si ha la relazione \( \sum_{i = 1}^{n-1} B = A[n] - A[1]. \) Supponiamo allora che valga \( \sum_{i = 1}^{n-1} B \geq n \) e che non ci siano salti.

Fin qui ti seguo...poi mi perdo

"apatriarca":Abbiamo quindi che \(1 \geq B\) e quindi \[ n > n-1 = \sum_{i = 1}^{n-1} 1 \geq \sum_{i = 1}^{n-1} B = A[n] - A[1] \geq n. \]
Siamo quindi arrivati ad una contraddizione e possiamo allora dire che ci deve essere almeno un salto.

[apatriarca]

Se un qualche numero intero è \( < 2, \) allora il massimo valore che può assumere è \( 1. \) La somma di tali numeri sarà quindi pertanto inferiore alla somma di uno stesso numero di \(1\) (il valore massimo che può assumere tale somma può quindi essere il loro numero).