Scelta struttura dati

[L\'Esecutore]

Devo realizzare il progetto spiegato dopo in C, non vi chiedo grossi aiuti, solo di aiutarmi a scegliere le strutture dati più adeguate. Non ci possono essere vincoli di dimensione, quindi le matrici vanno escluse. Devo tenere conto delle prestazioni quindi le scelte devono portarmi a evitare che le operazioni richieste abbiano costi eccessivi. Grazie mille, ogni aiuto è gradito

Le tessere del mosaico sono costituite da quadrati di lato 1. Due tessere sono definite adiacenti se i corrispondenti quadrati hanno un lato in comune. Un mosaico ` un insieme di tessere connesse almeno per un lato: cioè deve essere possibile percorrere l’intero mosaico muovendosi tra tessere adiacenti.
Il programma dovrà definire una struttura dati per l’oggetto mosaico e permettere le seguenti operazioni:
- nuovo()
Inizializza un nuovo mosaico con una sola tessera in posizione (0,0) (definite un opportuno sistema di riferimento), eventualmente cancellando il mosaico precedente.
- inserisci a caso()
Aggiunge al mosaico corrente un quadrato in una posizione scelta a caso tra le ammissibili (ossia con probabilità pari a 1 diviso il numero di posizioni ammissibili).
- inserisci(x, y)
Aggiunge al mosaico un quadrato in posizione (x, y) se la posizione è ammessa, altrimenti segnala un errore.
- perimetro()
Restituisce il perimetro del mosaico corrente (ossia il numero di lati liberi da quadrati)
- ordine()
Restituisce l’ordine del mosaico, ossia la lunghezza del lato del più piccolo quadrato che può contenere il mosaico.
- costruisci(n)
Costruisce un mosaico formato da n quadrati invocando n volte l’operazione inserisci a caso().

(Mantenete una struttura dati apposita per le posizioni ammissibili, vi servirà per facilitare l’estrazione casuale di una posizione ammissibile nell’operazione inserisci a caso(). )

[L\'Esecutore]

Up

[PGI-Bis]

Potresti usare un albero a quadranti. Non ho capito bene la distinzione tra ordine e perimetro ma dovrebbero diventare entrambi funzione della profondità dell'albero.

[L\'Esecutore]

Io me lo sono immaginato come un piano cartesiano, la prima tessera sta in (0,0).
Se ho 3 tessere rispettivamente in(0,-1), (0,0), (0,1) il mio mosaico avrà ordine 3 e perimetro 8.

[PGI-Bis]

Carta e penna alla mano dopo un paio di scarabocchi mi risulta papabile un quadtree costruito dal basso.

In pratica quando introduci la prima tessera crei un quadrante senza genitore di lato unitario e posizione (xa,ya)

Quando introduci la seconda tessera crei un secondo quadrante senza genitore di lato unitario e posizione (xb,yb)

Dopodichè unisci i due quadranti con un parente comune di lato Max(xb-xa, yb-ya)

In generale per unire due quadranti in un genitore devi determinare il minimo quadrante sufficiente a contenerli entrambi partendo dalla radice dell'albero.

Il quadrante esiste se la sua superficie è contenuta nella radice dell'albero. Altrimenti occorrerà congiungere la radice alla foglia inserendo tutti i nodi del ramo a cui la foglia appartiene.

Risulta a questo punto che il perimetro dell'albero sia il perimetro della radice e l'ordine il lato della stessa.

L'albero ti consente di determinare con efficienza se le posizioni astrattamente accessibili che crei quando introduci una nuova tessera siano effettivamente disponibili.

[L\'Esecutore]

Non ho molta familiarità sui quadtree, ora vedo di fare qualche tentativo.
Grazie dell'aiuto, spero di riuscire a metterlo in pratica:)

[gugoXX]

Io invece ti propongo tale classe (Beh, in C un insieme di strutture dati e di funzioni).
Per memorizzare le tessere del mosaico gia' inserite userei una Lista di coordinate.
Per memorizzare le posizioni papabili per i prossimi inserimenti userei un'altra Lista di coordinate, da aggiornarsi ogni volta che si inserisce una nuova tessera.
La funzione per verificare se una coordinata e' possibile e' banalmente la ricerca in quest'ultima lista.
le funzioni di inserimento e cancellazione, quest'ultima necessaria per la lista dei papabili, sarebbero quindi O(N Log N) come da lista.
La funzione perimetro dovrebbe essere semplicmente la lunghezza della lista dei papabili, quindi O(1). Non ho capito nel caso di buchi interni se il perimetro li deve considerare. Questo approccio lo farebbe.
Per la funzione ordine dovrebbe essere sufficiente tenere a mente la massima coordinata X e la massima coordinata Y (ed evenutlamente anche le minime, nel caso di coordinate negative), durante l'inserimento di una nuova tessera, quindi di nuovo O(1)


Poi in realta' io userei 2 Hashtable con chiave doppia al posto delle 2 liste, dove le 2 chiavi sarebbero ovviamente le coordinate.
In tal modo anche tutte le funzioni di inserimento e cancellazione sarebbero con complessita' O(1). Avresti quindi tutto in O(1), direi con conseguente massimo dei voti.

[L\'Esecutore]

La hashtable mi piace molto come soluzione, ma temo che per questo progetto sia fuori discussione :(