mostrielo

boolean

User info:

Registered: Sep 2004
Posts: 47 (0.01 al dì)
Location: Milano
Corso: Informatica (F49)
Anno: c++
Time Online: 2 Days, 15:14:46 [...]
Status: Offline

Post actions:

Operazione impianto (alfa):
sembrerebbe essere un problema di ottimizzazione, quindi probabilmente Programmazione dinamica o Algoritmi golosi.
Se la soluzione fosse la seconda di che Stanze sarebbe goloso l'algoritmo?

mjfan80

User info:

Registered: Nov 2001
Posts: 140 (0.02 al dì)
Location: Vallecamonica (BRESCIA)
Corso: Informatica quinquennale
Anno: 5°? 6°? 7°? bho
Time Online: 19:22:16 [...]
Status: Offline

Post actions:

ho dei piccoli dubbi sull'eliminazione di un stanza

voi come l'avete interpretata?

io l'ho interpretata così:
se devo eliminare una stanza che non sia quella di ingresso, devo prendere tutti i suoi figli e farli diventare figli del padre della stanza da eliminare, giusto?

Allego immagini della mia interpretazione

Attachment: cancellazione.gif
This has been downloaded 47 time(s).

__________________
Heal The World
Just Because You Read It In A Magazine Or You See It On A Tv Scren Don't Make It Factual

ale82info

.grande:maestro.

User info:

Registered: Dec 2003
Posts: 2538 (0.33 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 17 Days, 13:18:39 [...]
Status: Offline

Post actions:

se lo rappresenti con un albero credo che la cancellazione si faccia sempre in quel modo

iCENiCE

User info:

Registered: Dec 2001
Posts: 165 (0.02 al dì)
Location:
Corso:
Anno: troppi...
Time Online: 3 Days, 1:23:55 [...]
Status: Offline

Post actions:

Sinceramente ne sono usciti di molto piu' difficili(questo e' anche carino come "storia"), io personalmete credo di essere a buon punto, a parte qualche piccola questione di puntatori facilmente risolvibile.
Come struttura dati ho usato un AVL-Tree, nel caso peggiore il tempo e' di O(log n), e cmq la percorrenza media e' O(h), ottimo sopratutto se l'albero diventa molto grande (cosa molto prevedibile).

ale82info

.grande:maestro.

User info:

Registered: Dec 2003
Posts: 2538 (0.33 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 17 Days, 13:18:39 [...]
Status: Offline

Post actions:

ma scusa...l'albero del progetto non è binario! L'albero avl non permette di bilanciare un albero binario?

full

User info:

Registered: Sep 2004
Posts: 35 (0.00 al dì)
Location:
Corso: informatica
Anno: 3
Time Online: 9:26:01: [...]
Status: Offline

Post actions:

ciao a tutti
effettivamente credo sia impossibile usare gli alberi binari visto che, ogni stanza ha dei collegamenti (corridoi) con k stanze, come nell' esempio, ho pensato anche io agli alberi, ma a quelli k-ari, anche se non c'è molto su libro, come implementazione.
Solo che in mente c'è sempre la stessa frase, mi sembra troppo facile che il prof. abbia disegnato un albero a pag 2 per dirci di usare gli alberi, quella sembra l'idea più intuitiva ma è chiaro che per capire se una stanza è sorvegliata in qualche modo ci vuole un altra struttura, boo, ancora non ho capito come "sorvegliare" le stanze.

buon lavoro

ciao

lino

User info:

Registered: Jun 2003
Posts: 96 (0.01 al dì)
Location: lodi
Corso: informatica
Anno: terzo
Time Online: 2 Days, 1:25:20 [...]
Status: Offline

Post actions:

Qualcuno ha capito quale potrebbe essere la struttura migliore per sorvegliare le stanze?

ale82info

.grande:maestro.

User info:

Registered: Dec 2003
Posts: 2538 (0.33 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 17 Days, 13:18:39 [...]
Status: Offline

Post actions:

ma voi come pensate di implementare la funzione Impianto?!
Io non riesco a trovare nemmeno un modo per calcolarla a mano!!!!

lfn

***La Femme Nikita***

User info:

Registered: Nov 2004
Posts: 171 (0.02 al dì)
Location: Milano
Corso: TICOM
Anno: 2° anno
Time Online: 1 Day, 12:50:30 [...]
Status: Offline

Post actions:

ankio sono in crisi con la struttura, visto che gli alberi k-ari non ho idea di come rappresentarli, visto che in questo caso non si puo' fare una struttura nodo con puntatori fissi a padre e due figli.. qualche suggerimento??
secondo me in apparenza è più facile, ma nella realtà è complicato come gli altri..
per quanto riguarda l'impianto, ankio ho pensato a programmazione dinamica o allgoritmi golosi ma non sono ancora arrivata al dunque..
lfn

__________________
an arrow from the sun

black_mamba

User info:

Registered: Jan 2004
Posts: 15 (0.00 al dì)
Location: milano
Corso: informatica
Anno: 4
Time Online: 12:43:07: [...]
Status: Offline

Post actions:

gli alberi k-ari pg 203 del libro, un puntatore per il padre un puntatore per in primo figlio, e un puntatore per il fratello quindi su ogni livello c'è una lista concatenata.
C'è anche il problema della ricerca del nome della stanza

ale82info

.grande:maestro.

User info:

Registered: Dec 2003
Posts: 2538 (0.33 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 17 Days, 13:18:39 [...]
Status: Offline

Post actions:

Originally posted by black_mamba

C'è anche il problema della ricerca del nome della stanza

black_mamba

User info:

Registered: Jan 2004
Posts: 15 (0.00 al dì)
Location: milano
Corso: informatica
Anno: 4
Time Online: 12:43:07: [...]
Status: Offline

Post actions:

La ricerca è un'operazione frequente, mi chiedevo se sarebbe meglio farla in tempo lineare, o mantenere una struttura dati ordinata e farla in tempo logaritmico.


Partendo dall'idea di grafo, e considerando le stanze come l'insieme dei vertici e i corridoi come insieme dei lati...secondo voi quest'idea può portare da qualche parte?

lino

User info:

Registered: Jun 2003
Posts: 96 (0.01 al dì)
Location: lodi
Corso: informatica
Anno: terzo
Time Online: 2 Days, 1:25:20 [...]
Status: Offline

Post actions:

Secondo me sono buone sia l'dea dell' albero k-ario che quella di grafo... alla fine voi cosa state utilizzando?

L'impianto come lo avete pensato?

full

User info:

Registered: Sep 2004
Posts: 35 (0.00 al dì)
Location:
Corso: informatica
Anno: 3
Time Online: 9:26:01: [...]
Status: Offline

Post actions:

Ciao ragazzi, ho appena avuto una specie di illuminazione! per caso sfogliando il libro (molto a caso direi) sono giunta alle foreste di alberi radicati, vi chiederete cosa centrano, io ci ho fatto caso solo ora: nell'input del prof. alle prime due righe c'è,
d frutta e d mobili. questi sono due depositi diversi! quindi due alberi diversi.
L'idea di usare un grafo non so se è possibile perchè 1) dobbiamo avere un solo ingresso, 2)ogni stanza deve avere un cammino unico e credo che solo gli alberi permettano un' implementazione del genere (poi non so, sui grafi non sono il massimo).
Da qualche parte nei lucidi, avevo visto qualche progetto fa, un modo che dato un nodo (il nome di una stanza) risaliva alla sua radice e quindi al deposito di appartenenza.

che ne dite? secondo voi è un possibile inizio?

ale82info

.grande:maestro.

User info:

Registered: Dec 2003
Posts: 2538 (0.33 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 17 Days, 13:18:39 [...]
Status: Offline

Post actions:

mi dici dove l'hai trovato gentilmente?