[C]programma da realizare in C su grattacieli

[matteo.pata]

Ciao a tutti mi servirebbe una mano su un progetto che devo consegnare per l'università.
Vi posto il testo del progetto.

Il problema
A New New York, la citta piu popolata nell'anno 3000 D.C., si costruiscono grattacieli di continuo e ad una
velocita impressionante. Purtroppo, non rimangono mai in piedi a lungo perche secoli di pessime politiche
estere hanno creato un clima internazionale talmente invivibile che attacchi terroristici si susseguono di
continuo, e non di rado i palazzi vengono rasi al suolo.
Ogni grattacielo al momento della costruzione viene battezzato con un nome (univoco).
New New York si affaccia sul mare, con la sua spiaggia si estende da Nord a Sud. Se la si osserva dal
mare, di notte, sopra alla spiaggia appare una tipica skyline (la linea di conne fra cielo e grattacieli).
Infatti, ogni metro di spiaggia (ad una certa latitudine) e sovrastato da un certo numero di grattacieli a
longitudini diverse (talvolta uno o nessuno). Chiaramente, e sempre il piu alto di questi a svettare sugli
altri, e la sua altezza denisce l'altezza dello skyline su quel metro di spiaggia. In assenza di palazzi, lo
skyline e alto zero.
Il problema consiste del misurare l'altezza media dello skyline di New New York durante la continua
costruzione e distruzione di palazzi.

Dati in input

L'input consiste in una serie di righe. Nella prima riga compare un numero, che corrisponde alla lunghezza
totale della spiaggia, in metri (per esempio, se vale 5, la spiaggia comincia nel punto 0 e si estende no
al punto 5). Ciascuna riga successiva descrive un evento (costruzione o, tragicamente, abbattimento di
un grattacielo), o una richiesta.
1 Le richieste sono semplicemente delle righe costituite da un unico punto interrogativo. Nel leggere una richiesta, il programma deve stampare nello standard output l'altezza media dello skyline,
espressa in metri, precisa al millimetro.
2 Gli eventi di tipo abbattimento cominciano dalla stringa \kaboom" (senza le virgolette), seguita
dal nome del palazzo abbattuto.
3 Gli eventi di tipo costruzione cominciano con la stringa \new" (senza le virgolette), seguita dal nome
del palazzo costruito, seguito da una tripletta di misure (separate da spazi) che rappresentano,
rispettivamente: da quale metro di spiaggia comincia e a quale metro nisce il grattacielo, e la
sua altezza, tutto in metri. Le prime due misure sono numeri naturali, la terzo è un razionale
(con virgola). Ad esempio, se compaiono i numeri 4 6 10.4, signica che il grattacielo si estende
nell'intervallo che comincia a 4 metri esatti, finisce al 6sto metro (sarà dunque lungo due metri), ed
è alto 10.4 metri.
La serie di righe è terminata da una riga composta da un solo punto esclamativo, che segnala la fine del
problema.


L'input viene fornito al programma sotto forma di file di testo, il cui nome viene specicato dal primo
argomento passato al programma. Se non ne viene specicato alcuno, l'input deve venir letto direttamente
dallo stdin.

Altri vincoli

E' richiesto che programma funzioni in modalità \on-line": cioè l'input può essere letto una sola volta,
e, nel leggere una richiesta, la risposta deve essere stampata sul video senza che sia necessario leggere
nessuna delle righe successive. Insomma il programma deve funzionare anche se ipoteticamente l'input
fosse fornito solo una riga alla volta, e se le risposte fossero necessarie prima di fornire la riga successiva.
La correttezza è un requisito necessario. Un progetto sarà considerato più o meno valido rispetto all'ef-
cienza (tempo di calcolo) nel risolvere le istanze del problema di dimensioni via via crescenti (non solo
le istanze fornite, ovviamente, ma anche altre del tipo di quelle fornite).

Esempi

Mettiamo che la spiaggia sia lunga 10 metri (da 0 a 10). Se abbiamo solo il grattacielo pippo e pluto,
costruiti con
new pippo 7 10 25.0
new pluto 5 10 15.0
allora la skyline sara' ad altezza 0 no al quinto metro (per cinque metri), 10:0 per i metri dal quinto al
settimo (dunque per due metri), e 25,0 dal settimo al decimo (dunque per tre metri). L'altezza media
sara (2 * 15 + 3 * 25)=10, cioè 10,5 metri.
Dal sito del corso è possibile scaricare esempi di input (file di testo) di dicolta crescente.

Dimensioni tipiche dei problemi

Gli abbattimenti sono frequenti. Si sa che i grattacieli che vengono distrutti sono, grossomodo, una
percentuale ssa dei grattacieli che vengono costruiti (es. il 20-50%).
I nomi non sono mai piu lunghi di qualche centinaio di caratteri.
I grattacieli possono essere molto numerosi. Tuttavia, istanze anche grandi del problema (in numero di
grattacieli) hanno di solito spiagge relativamente poco estese.
Gli esempi forniti sono rappresentativi delle dimensioni possibili che ci si puo attendere.

Suggerimenti

1. Per leggere l'input e scrivere l'output si possono usare le funzioni standard ANSI C fscanf() e
printf(). Il primo parametro della fscanf() sia una variabile posta a stdin oppure ad un FILE*
aperto in lettura (a seconda del numero di argomenti).
2. Soluzioni che impiegano un tempo quadratico (o peggio) nel numero di eventi NON saranno
abbastanza efficienti da risolvere le istanze grandi del problema.
3. SEMPRE: pensare bene sulla carta prima di cominciare a scrivere codice!

Qui vi riporto l'intero testo.
http://rapidshare.com/files/37346856...2010c.pdf.html

Mi servirebbe una mano nella struttura dati da utilizzare per ottimizzare al meglio i tempi e il costo delle varie funzioni inerenti al progetto.

[lupoxxx87]

contro regolamento

[matteo.pata]

Non era una richiesta di risoluzione del progetto ma una mano nella scelta della struttura dati da scegliere tutto qua....

[matteo.pata]

up

[Furla]

a pelo, la consegna sembra suggerire un array in cui ogni elemento è un metro di spiaggia, cioè una lista ordinata delle altezze degli edifici che lo sovrastano. una ulteriore lista ordinata alfabeticamente (o un albero ternario, se vuoi fare il sofisticato) favorirà la ricerca degli edifici da abbattere, data l'alta frequenza con cui l'evento si presenta.

seguendo l'esempio, al termine delle new avrai:

array di liste spiaggia:
0 0 0 0 0 15 15 25 25 25
          0  0  15 15 15
                0  0  0

lista edifici:
pippo 7 10 25.0
pluto 5 10 15.0

se arrivasse un segnale di abbattimento per pippo, lo cercheresti nella lista edifici, da cui ricavi che devi rimuovere le altezze 25 dai metri tra 7 e 10.

spero di essermi spiegato... tu a cosa avevi pensato?

[matteo.pata]

Avevo pensato anche io ad una lista ordinata per gli edifici in ordine alfabetico così da velocizzare la ricerca e la cancellazione però non ho ben capito la storia dell'array per la spiaggia.Praticamente tu dici immaginamio di avere una spiaggia lunga 10 metri e poi l'inserimento di 4 grattacieli

0   0     0     0     0     0    0    0    0    0     ->array spiaggia
   12.3  12.3 12.3    0     0    0    0    0    0
   16.4  16.4 16.4   16.4   0    0    0    0    0     ->questi come li rappres?
0   0     0      0     0    0    0    0  19.4 19.4         array?liste?
                     13.7 13.7 0    0    0     0 

new pippo   1   3          12.3   
new pluto    1   4         16.8    altezza =[(12.3*3)+16.4+13.7+(19.4*2)]/10
new pinco   8    9       19.4
new palla    4    5         13.7

la lista dei grattacieli ci sono in ordine alfabetico e così velocizzo.
Però come dici tu per la questione della spiaggia non ho molto ben capito se mi fai un altro esempio sarebbe meglio...grazie intanto

[lupoxxx87]

tu a runtime tieni in memoria solamente la lista dei grattacieli, poi quando ti chiede informazioni sulla spiaggia generi l'array.

lo inizializzi a zero, poi scorri la lista e ogni volta che incontri un grattacielo nella lista scorri l'array dal punto di inizio al punto di fine di quel grattacielo e confronti l'altezza che hai nell'array con quella che hai nella spiaggia. se è il caso aggiorni quella della spiaggia.

easy enough ?
ah, se vuoi ottimizzare puoi tenere in memoria una sorta di hash code per sapere se sono state effettuate modifiche, per non dover calcolare di seguito la stessa spiaggia due volte, e puoi evitare l'ordinamento della lista, perchè non ti giova come credi e la costruzione/abbattimento è casuale, non ordinata

[matteo.pata]

si l'abbattimento è casuale però se devo abbattare un grattacielo che inizia con A se la lista è in ordine non la devo scandire tutta..metti che inserisco un grattacielo in ultima posizione che inizia con A e dopo un paio di inserimenti lo voglio cancellare se non tengo ordinata la lista devo scorre tutta la lista per cancellarlo se invece è ordinata sarà nell prime posizioni..quindi risparmieri o sbaglio??

[lupoxxx87]

se non hai un indice ad albero, o ad hash, non ti serve a nulla tenerla ordinata, perchè non sai dove cercare...

prova a immaginare..se hai 40 grattacieli chiamati "AA%" e vuoi cancellare un grattacielo che si chiama "AB%" tu penserai che è nelle prime posizioni, invece è nelle ultime...

la cosa ideale sarebbe una mappa

[matteo.pata]

in effetti il ragionamento non fa una piega...una mappa cosa intendi...

[lupoxxx87]

una mappa è un po' come un array..... solo che non è ordinato...

per dirla in modo semplice....un array è questo

vett : array
vett := ( elem0, elem1, elem2, elem3 .... )

per cui vale

vett[n] = elemn


mentre una mappa è

mappa : map
mappa := ( '0' => 'a', 'paperino' => 'pluto', '*x' => '7' )

per cui vale

mappa[0] = a, mappa[paperino] = pluto




adesso probabilmente molti commenteranno questo messaggio per le inesattezze formali, ma la linea teorica è questa.
un array è un elenco di elementi omogenei, una mappa è una funzione che lega elementi di uno o più insiemi, non necessariamente omogenei.

capisci che se tu realizzi una mappa (hashset) puoi accedere ad un qualsiasi elemento con complessità costante.

se hai voglia di non dormire le prossime notti puoi realizzarla sfruttando i puntatori...
ovvero crei una funzione che prende una stringa restituisce un intero, e all'indirizzo di memoria corrispondente all'intero ci salvi la tua struttura grattacielo....con tutte le precauzioni che servono...

[matteo.pata]

interessante come cosa ma le mie possibilità e le mie capacità in stesura di codice non mi sembrano molto all'altezza di fare tutto ciò quindi penso proprio di usare una lista e un array.Non sarà ottimizzato al massimo però almeno funzionerà si spera....

[wingman87]

Che esercizio triste... L'idea dell'orizzonte della città visto dalla spiaggia poi mi sa di molto malinconico, non so perché...

[matteo.pata]

beh si diciamo che non è proprio allegro come progetto però lo devo fare quindi chi mi aiuta per qualche linea di codice è sempre ben accetto....

[Furla]

ricostruire l'array ad ogni richiesta è computazionalmente gravoso, e non rispetta la consegna (tempo di esecuzione meno che quadratico rispetto al numero di eventi). meglio tenerlo aggiornato ad ogni evento con operazioni O(1) o al limite O(logn) per la ricerca.
di strutture per velocizzare la ricerca alfabetica ce ne sono a iosa, sbizzarrisciti

[matteo.pata]

non ho ben capito il tuo ragionamento io avevo pensato di tenere traccia dei grattacieli in una lista ogni volta inserisco e cancello.alla chiamata della funzione media mi creavo il mio array con le varie altezze e poi facevo la media.Corretta come soluzione oppure no?te cosa intendevi spiegami un po' non sono proprio una volpe in fatto di programmazione...

[lupoxxx87]

se ti riferivi alla mia proposta....

Originariamente inviato da Furla

ricostruire l'array ad ogni richiesta è computazionalmente gravoso, e non rispetta la consegna (tempo di esecuzione meno che quadratico rispetto al numero di eventi). meglio tenerlo aggiornato ad ogni evento con operazioni O(1) o al limite O(logn) per la ricerca.

esempio: tu crei 40 grattacieli, ne distruggi 30, e chiedi la media.

• l'array pensato a mio modo valuterà 10 grattacieli e calcola la media una volta sola.

• l'array a tuo modo viene aggiornato 70 volte, ogni volta deve scandire l'intera lista, a meno che non tenga in memoria a quale grattacielo si sta riferendo in ogni singolo elemento, e calcolerà la media una volta sola


mi sembra che sia il tuo ad essere gravoso

[matteo.pata]

anche io l'avevo pensata così...ad ogni richiesta della funzione media mi calcolavo il nuovo array costruito con i grattacieli presenti nella lista...giusto come ragionamento??

[Fabietto206]

Vedo ke 6 impegnato con il progetto di quel folle di Tarini!!

[lupoxxx87]

radicioni (si chiamava così ?) era 10 volte più bastardo...questo è un giochetto a confronto