Pages: [1]   Go Down
Print
Author Topic: Info appello del 8 Marzo  (Read 1576 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
varPippo
Guest
« on: 11-03-2010, 12:08:30 »

Ragazzi chi ha le risposte corrette del suddetto compito?
Logged
KiLLing Spree
Matricola
*
Offline Offline

Posts: 81



« Reply #1 on: 18-03-2010, 16:11:16 »

1.b
2.a
3.c
4.c
5.c
6.a
7.d
8.c
9.b
10.c
11.b
12.a
13.a
14.a
15.d
Logged

Ciao!
xaviorx
Matricola
*
Offline Offline

Posts: 10


« Reply #2 on: 30-03-2010, 09:56:24 »

1.b
2.a
3.c
4.c
5.c
6.a
7.d
8.c
9.b
10.c
11.b
12.a
13.a
14.a
15.d

Perchè la 7 è d?
Logged
Neds
Matricola
*
Offline Offline

Gender: Male
Posts: 36


« Reply #3 on: 08-04-2010, 16:28:24 »

1.b
2.a
3.c
4.c
5.c
6.a
7.d
8.c
9.b
10.c
11.b
12.a
13.a
14.a
15.d

Perchè la 7 è d?

la 7 è il numero max di nodi interni che un albero rosso-nero con b-altezza 3 può avere?
la soluzione dovrebbe essere: 2^{bh(x)}-1, considerando bh(x)=3 viene 2^3-1 = 7 (che dovrebbe essere la risposta a)
o sbaglio???
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #4 on: 10-04-2010, 15:33:29 »

Quote
la 7 è il numero max di nodi interni che un albero rosso-nero con b-altezza 3 può avere?
la soluzione dovrebbe essere: 2^{bh(x)}-1, considerando bh(x)=3 viene 2^3-1 = 7 (che dovrebbe essere la risposta a)
o sbaglio???
vediamo di regionarci!
i nodi interni sono tutti i nodi dell'albero escluse le foglie nil.
la b-altezza è il numero di nodi neri che si incontrano nel cammino dalla radice ad una qualunque foglia.
il numero massimo di nodi si ha quando abbiamo alternativamente: livello nero-rosso....nero-rosso-nero e l'albero è bilanciato, e cioè quando h=2bh-1.
ad altezza h il numero massimo di nodi interni è (2^h)-1.
Giusto?
quindi.... prova a correggere!
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Neds
Matricola
*
Offline Offline

Gender: Male
Posts: 36


« Reply #5 on: 12-04-2010, 11:38:37 »

Quote
la 7 è il numero max di nodi interni che un albero rosso-nero con b-altezza 3 può avere?
la soluzione dovrebbe essere: 2^{bh(x)}-1, considerando bh(x)=3 viene 2^3-1 = 7 (che dovrebbe essere la risposta a)
o sbaglio???
vediamo di regionarci!
i nodi interni sono tutti i nodi dell'albero escluse le foglie nil.
la b-altezza è il numero di nodi neri che si incontrano nel cammino dalla radice ad una qualunque foglia.
il numero massimo di nodi si ha quando abbiamo alternativamente: livello nero-rosso....nero-rosso-nero e l'albero è bilanciato, e cioè quando h=2bh-1.
ad altezza h il numero massimo di nodi interni è (2^h)-1.
Giusto?
quindi.... prova a correggere!

quindi bh=3 da sostituire a  h=2bh-1=2*3 -1=5 che dobbiamo sostituire a (2^h)-1=(2^5)-1=31 e questa sarebbe la risposta c del compito, però quella corretta è la d, cioè 63 
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #6 on: 12-04-2010, 12:05:03 »

il 63 mi fa pensare ad un 64-1= 2^6-1; quindi magari il problema sta in quale altezza considerare. La radice e altezza 0 o 1?non ricordo quale consideri il prof.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #7 on: 12-04-2010, 12:09:29 »

eureka! mi sembra di ricordare che il numero dei nodi è 2^(h+1)-1. Poichè partiamo dalla radice che ha h=0.
di cinseguenza, se h = 5, numero nodi sarà n=2^(h+1)-1=2^(5+1)-1=2^6-1=64-1=63=D.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Pages: [1]   Go Up
Print
Jump to: