Pages: [1]   Go Down
Print
Author Topic: Esercizi ricorsione e alberi  (Read 2309 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« on: 29-09-2010, 18:26:35 »

Mi chiedevo, ma per gli esercizi sulla ricorsione, c'è un modo per risolverli più velocemente o dobbiamo metterci con un computer ad eseguire l'intero metodo? 

Per gli alberi, io ho una domanda del genere:

Quote
Sia dato un albero binario completo contenente 8 nodi, il cui ultimo livello è riempito da sinistra a destra. Indicare il corretto output di una visita Inorder del suddetto albero nel caso in cui la sua visita Preorder sia definita dal seguente output.
(30, 29, 12, 7, 30, 27, 16, 7)

Ora come faccio a stabilire cosa darà la visita Inorder se non so esattamente com'è, e non ho una figura dell'albero?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #1 on: 30-09-2010, 12:39:56 »

Beh diciamo che devi diventare un minicomputer  pc
Prima disegni l'albero completo con i nodi vuoti, nel nostro caso così:
                      O
                 O       O
             O   O   O    O
         O

Poi il tuo cervello deve chiamare il metodo di inserimento Preorder, riempendo di conseguenza l'albero vuoto
(30, 29, 12, 7, 30, 27, 16, 7)
                      30
                29         27
            12   30    16    7
         7
             
A questo punto devi visitare mentalmente l'albero secondo la visita inorder, ottenendo la risposta all'esercizio
(7, 12, 29, 30, 30, 16, 27, 7)
Il procedimento che usavo è questo... a meno di errori dovrebbe essere giusto  ok
Logged
dani89
Apprendista Forumista
**
Offline Offline

Posts: 254



« Reply #2 on: 30-09-2010, 13:06:29 »

 
giustissimo
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #3 on: 30-09-2010, 13:48:34 »

Ah....bè..avevo difficoltà a capire come disegnare l'albero, alla fine pare che l'ultimo nodo sia l'unico figlio in basso, non ero certo di questa cosa.....grazie mille 
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #4 on: 05-10-2010, 15:06:37 »

Ma per quanto riguarda gli esercizi ricorsivi non è un pò lungo?
Cioè non c'è un modo più veloce per risolvere gli esercizi oppure bisogna mettersi proprio su carta a fare tutte le sostituzioni negli array e ad eseguirsi tutto il codice?

Ad esempio:

Code:
BinarySelect(A, a, b)
1. if (a==b) then return A[a];
2. c = floor ((a+b)/2);
3. S1 = S2 = 0;
4. for i=a to c do S1 = S1 + A[i];
5. for i=c+1 to b do S2 = S2 + A[i];
6. if (S1 > S2) then return BinarySelect(A, a, c);
7. else return BinarySelect(A, c+1, b);

Descrivere il corretto output ritornato dall'algoritmo se eseguito sui parametri (A, 1, 9), dove A corrisponde al seguente array:
[4, 6, 1, 1, 2, 3, 3, 8, 3]

Cioè mentre non c'è un modo per farlo più velocemente piuttosto che eseguiro come un computer l'intero algoritmo?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
dani89
Apprendista Forumista
**
Offline Offline

Posts: 254



« Reply #5 on: 05-10-2010, 18:36:29 »

si il modo c'è, col binary select devi fare così:
1) dividi l'array in 2 parti;
2) sommi gli elementi delle 2 sottoparti e tieni la parte con somma degli elementi maggiore e l'altra la "butti via";
3) dividi la parte che ti è rimasta in 2;
e così via finchè non ti rimangono 2 sottoarray di dimensione 1 o 2 e scegli il numero maggiore.
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #6 on: 05-10-2010, 19:42:46 »

Ah...e oltre a questo, binary select mi pare ci sia binaryswap...e non mi ricordo se ce n'è altri....come si fanno quelli?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #7 on: 11-10-2010, 13:54:32 »

Daréios ti ho risposto nel topic che sta in primo piano...
Logged
Pages: [1]   Go Up
Print
Jump to: