OliForum Matematico

ki d voi ha mai sentito parlare d un albero binario???
<BR>
<BR>si tratta d una \"lista\" usata nel mondo dell\'informatica in cui ogni elemeto (padre) ha 2 figli (destro e sinistro) (il primo elemento,\"detto radice\",ha indice zero,poi a seguire,dall\'alto verso il basso e da sinistra verso destra).
<BR>ho fatto alla buona uno schemino (scusate la scarsa qualità, ma nn sono un artista!)
<BR>
<BR>..............................indice zero O
<BR>.............................................. / \\
<BR>......................................uno O O due
<BR>............................................/ \\ / \\
<BR>....................................tre O OO O sei
<BR>.........................ecc.
<BR>
<BR>
<BR>
<BR>il quesito è :
<BR>DIMOSTRARE (PER INDUZIONE) CHE IL PADRE DI UN GENERICO ELEMENTO SI TROVA ALLA POSIZIONE (n - 1)/2 (considerare la parte intera)
<BR>
<BR>ciao e grazie
<BR>
<BR>ps: questo tipo di struttura dati massimizza in modo esponenziale i tempi d ricerca
<BR>
<BR>[ Questo Messaggio è stato Modificato da: Athos il 19-05-2004 17:22 ]
<BR>
<BR>[ Questo Messaggio è stato Modificato da: Athos il 20-05-2004 11:25 ]
<BR>
<BR>[ Questo Messaggio è stato Modificato da: Athos il 20-05-2004 11:27 ]<BR><BR>[ Questo Messaggio è stato Modificato da: Athos il 20-05-2004 11:28 ]

per favore, qualcuno mi dia la soluzione!!!è importante.ciao <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif">

innanzi tutto è facile dimostrare (sempre per induzione)che il primo elemento dell\'n-esima riga ha indice (2^n)-1 (si ricava da 1+2+4+8...+2^(n-1)) e il primo della riga successiva [2^(n+1)-1] che soddisfa il quesito. l\'elemento successivo, 2^(n+1), soddisfa anch\'esso il quesito(hanno lo stesso padre). l\'elemento successivo, 2^(n+1)+1 con il padre successivo,2^n, soddisfa nuovamente il quesito. ora, visto questo, induttivamente andrà bene anche per tutti i successivi fino all\'ultimo elemento dell\'n-esima riga.

prima d tutto t ringrazio x aver risposto,poi...
<BR>
<BR>dove hai dimostrato che il padre d un elemento è alla posizione (n - 1)/2 ?
<BR>
<BR> <IMG SRC="images/forum/icons/icon_smile.gif"> <IMG SRC="images/forum/icons/icon_smile.gif"> <IMG SRC="images/forum/icons/icon_smile.gif">

l\'ho dimostrato per i primi 2 elementi di ogni riga (dove ho scritto \"soddisfa il quesito\") e poi sono passato a dimostrarlo per tutti gli elementi della riga presi a due a due.se
<BR>
<BR> x allora il successivo è x+1
<BR>2x+1 2x+2 2x+3 2x+4
<BR>
<BR>quindi ambedue le terne soddisfano la tua relazione.

grazie tante (effettivamente prendendo carta e penna ho verificato ke avevi ragione anke senza il tuo secondo messaggio)
<BR>
<BR>ancora grazie
<BR>ciao