Pages: [1]   Go Down
Print
Author Topic: Domanda su heap  (Read 3053 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: 18-12-2010, 15:09:30 »

Siano A e B due array diversi di n elementi rappresentanti due min heap sullo stesso insieme di numeri.
Quale delle seguenti affermazione è vera?

a) A[0]<=B[1]
b)A[1]<=B[2]
c)A[2]<=B[3]
d) Nessuna delle precedenti è sempre vera.

Io risponderei a, perchè in teoria se sono due min heap sugli stessi elementi la root sarà sempre il minimo, quindi A[0] sarà per forza minore di B[1].

Che dite?
Logged

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

Gender: Female
Posts: 204



« Reply #1 on: 18-12-2010, 15:12:57 »

la a è vera, perchè A[0]= B[0] <= B[1] 
Logged
Fr3d3R!K
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.463



« Reply #2 on: 18-12-2010, 16:21:34 »

[...] quindi A[0] sarà per forza minore di B[1].
Affatto. A te chi assicura che i due heap abbiano gli stessi identici elementi, o perlomeno la stessa root? La domanda dice solamente che sono due min heap sullo stesso insieme di numeri. Anzi ve lo dice pure all'inizio che gli array sono diversi. La root di A potrebbe anche corrispondere all'ultimo elemento di B (o qualsiasi altro), non c'e` affatto una condizione che lo vieta. Quindi sia la a) che la b), come anche la c) sono tutte risposte che descrivono situazioni possibili, ma nessuna di queste condizioni e` sempre verificata. A te la ovvia conclusione.
Fonte: E` una delle domande che ho trovato nel compito quando ho sostenuto l'esame io .
P.S. A scuola guida a me hanno insegnato che le risposte che pretendono di essere vere "sempre" e "mai" sono tutte sbagliate...
Logged

Search Button, CODE Tag, Google & Italian language are your friends! Use Them!
ga2486
Apprendista Forumista
**
Offline Offline

Gender: Female
Posts: 204



« Reply #3 on: 18-12-2010, 16:31:41 »

[...] quindi A[0] sarà per forza minore di B[1].
Affatto. A te chi assicura che i due heap abbiano gli stessi identici elementi, o perlomeno la stessa root?

magari perchè sono entrambe minheap sullo stesso insieme di numeri? 
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #4 on: 18-12-2010, 16:57:56 »

Bè si però se dice che sono due minheap sullo stesso insieme, alla fine, almeno la root non dovrebbe coincidere?
Perchè vale la proprietà che deve essere il minimo. Magari gli elementi posso essere diversi all' interno della struttura, ma la radice che è il minimo non dovrebbe coincidere in entrambi gli array poichè sono minheap sullo STESSO insieme numerico?  
Un' altra cosa.

Quote
Il numero minimo di elementi in una heap di altezza h>O è (una heap con un solo elemento ha altezza zero)

Mi sembra...2^h+1
« Last Edit: 18-12-2010, 17:01:30 by Daréios » Logged

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

Gender: Male
Posts: 2.463



« Reply #5 on: 18-12-2010, 17:51:07 »

[...] quindi A[0] sarà per forza minore di B[1].
Affatto. A te chi assicura che i due heap abbiano gli stessi identici elementi, o perlomeno la stessa root?

magari perchè sono entrambe minheap sullo stesso insieme di numeri? 
Appunto. Sono entrambe minheap, non c'e` scritto da nessuna parte che sono due minheap uguali. E non essendo specificato, puo` anche capitare che siano due minheap con elementi differenti al loro interno. Inoltre l'insieme numerico in oggetto e` un'insieme qualunque, senza alcuna specifica (ad esempio) sul numero degli elementi. La tua risposta deriva dell'erronea supposizione che i due minheap siano uguali solo perche` hanno l'insieme numerico di riferimento in comune. Non so se mi spiego...

Il numero minimo di elementi in una heap di altezza h>O è (una heap con un solo elemento ha altezza zero)
Mi sembra...2^h+1
http://forum.sdai.unict.it/index.php?topic=7092.msg45178#msg45178
Logged

Search Button, CODE Tag, Google & Italian language are your friends! Use Them!
Naive
Matricola
*
Offline Offline

Posts: 57


Impossible is Nothing


« Reply #6 on: 19-12-2010, 11:00:20 »

Correggetemi se sbaglio, due minheap differenti ma sullo stesso insieme di numeri vuol dire che i numeri sono uguali, di sicuro la radice è uguale e man mano che scendiamo alla foglia l'ordine dei numeri può variare quindi quello che dice Fr3d3R!K dovrebbe essere sbagliato e la risp esatta dovrebbe essere la a.
Se ho detto una cavolato correggetemi.
Logged
Crasher
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 417



« Reply #7 on: 19-12-2010, 12:14:05 »

Correggetemi se sbaglio, due minheap differenti ma sullo stesso insieme di numeri vuol dire che i numeri sono uguali, di sicuro la radice è uguale e man mano che scendiamo alla foglia l'ordine dei numeri può variare quindi quello che dice Fr3d3R!K dovrebbe essere sbagliato e la risp esatta dovrebbe essere la a.
Se ho detto una cavolato correggetemi.
È quello che ho pensato ank'io.
I 2 array sono differenti, ma hanno lo stesso insieme di numeri, quindi nei 2 minheap la radice sarà uguale in entrambi, mentre i nodi interni potrebbero essere diversi.
Boh ognuno la interpreta a modo suo questa domanda...
Logged

Diventa ciò che sei nato per essere
Naive
Matricola
*
Offline Offline

Posts: 57


Impossible is Nothing


« Reply #8 on: 19-12-2010, 12:20:24 »

Quote
Boh ognuno la interpreta a modo suo questa domanda...
Sperando che il prof la interpreti come noi...
Logged
Crasher
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 417



« Reply #9 on: 19-12-2010, 12:42:19 »

sarei curioso di sapere la sua, così ci togliamo questo dubbio
Logged

Diventa ciò che sei nato per essere
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #10 on: 19-12-2010, 13:10:52 »


Appunto. Sono entrambe minheap, non c'e` scritto da nessuna parte che sono due minheap uguali. E non essendo specificato, puo` anche capitare che siano due minheap con elementi differenti al loro interno. Inoltre l'insieme numerico in oggetto e` un'insieme qualunque, senza alcuna specifica (ad esempio) sul numero degli elementi. La tua risposta deriva dell'erronea supposizione che i due minheap siano uguali solo perche` hanno l'insieme numerico di riferimento in comune. Non so se mi spiego...
Secondo me non e' affatto erroneo pensare che se viene detto che le 2 min-heap sono sullo stesso insieme numerico allora contengono tutti gli elementi di questo insieme anche se ordinati in modo differente inoltre quello che dici te avviene quando nell'esercizio fosse specificato che le 2 min-heap sono su 2 partizioni differenti (o quanto meno non necessariamente uguali) dell'insieme numerico dato.
Per esempio sia A={1,2,1} l'insieme numerico di riferimento allora
B={1,2,1} e
C={1,1,2}
sono 2 array su A, con la proprieta' min-heap, diversi tra loro (quello che chiedeva l'ex) 
« Last Edit: 19-12-2010, 13:12:25 by shiny » Logged
Fr3d3R!K
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.463



« Reply #11 on: 19-12-2010, 13:54:56 »

Shiny il tuo e` un caso. Io parlo in generale, in quanto non c'e` nulla di specifico.
Logged

Search Button, CODE Tag, Google & Italian language are your friends! Use Them!
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #12 on: 19-12-2010, 14:10:05 »

Shiny il tuo e` un caso. Io parlo in generale, in quanto non c'e` nulla di specifico.

Bè ma che vuol dire è un caso, sinceramente leggendo la domanda e immaginando la struttura la prima cosa che verrebbe da pensare a chiunque è proprio quella, quindi non vedo perchè rispondere che nessuna delle precedenti è vera, poichè la A lo è/sembra.
Nè tanto meno si può andare ad intuito.....magari non si verifica sempre, però fra le altre è l' unica vera, ha un suo margine di verità e quindi io la seleziono, non posso stare a vedere tutti i casi in cui si verifica o meno  boh
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #13 on: 19-12-2010, 15:51:45 »

Ma perché non chiedete al prof e vi levate ogni dubbio testate?

E poi festeggiate:
heap heap hurrà !
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 600


« Reply #14 on: 20-12-2010, 12:05:03 »

Siano A e B due array diversi di n elementi rappresentanti due min heap sullo stesso insieme di numeri.
Quale delle seguenti affermazione è vera?

a) A[0]<=B[1]
b)A[1]<=B[2]
c)A[2]<=B[3]
d) Nessuna delle precedenti è sempre vera.

Io risponderei a, perchè in teoria se sono due min heap sugli stessi elementi la root sarà sempre il minimo, quindi A[0] sarà per forza minore di B[1].

Che dite?
Io dico che hai ragione.
Logged
Pages: [1]   Go Up
Print
Jump to: