[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/373468562/prog2010c.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....:D :D

[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 :D

[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...:D :D

[lupoxxx87]

se ti riferivi alla mia proposta....

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

[WarDuck]

Premesso che non ho letto il testo poiché è abbastanza lungo...

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

Se l'array è ordinato può sfruttare questa cosa per effettuare una ricerca binaria, che a livello prestazionale è comparabile ad un albero, ed è più semplice da implementare.

Tuttavia l'inserimento ti costerebbe sempre O(N).

Il difetto dell'array è che è un po' troppo statico... potresti pensare di fare gli inserimenti sempre facendo una ricerca binaria:

1 2 3 5 7 9

Vuoi inserire 6... la chiave centrale è 3, quindi vai nel sotto-array destro [5 7 9], la chiave centrale è 7 quindi vai nel sotto-array sinistro [5], devi spostare 7 e 9 per ottenere:

1 2 3 5 6 7 9

Cmq non capisco una cosa... se vuoi usare una lista, perché dovresti crearti l'array per calcolarti la media, non basta scandirla?

[Fabietto206]

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

A me invece quelli di Radicioni parevano + fattibili, in quanto erano tt pressochè simili!!

Io ho fatto quello di febbraio di Tarini, quello dei puffi, e nn era facile x il mio livello....infatti mi ha sturato xkè alcune cose (che nn ho fatto io) nn gliele ho sapute spiegare!!

[lupoxxx87]

@warduck

sisi...sono tutti i sistemi di indicizzazione infatti utilizzati in dbms o simili...
il problema è realizzarli da zero in un paio di giorni

l'array lo fai perchè prima devi capire quali grattacieli sono sensibili per il landscape, e poi ti scandisci l'array per fare la media

@fabietto

radicioni voleva una relazione assurda assieme al progetto...quasi peggiore di quella di chinosi per mips
ed era comunque molto molto puntiglioso anche su cose inutili

[matteo.pata]

usavo un array in quanto la lunghezza della spiaggia tela da a priori lui quindi mi creavo un array di linghezza N dato dalle specifiche e poi scandivo la lista dei grattacieli e assegnavo ad ogni indice dell'array un altezza in base al grattacielo .fatto questo sommo tutte le posizioni dell'array e poi divido per la lunghezza della spiaggia....Mi sembra abbastanza buona come idea che ne dite??
cmq avevo fatto anche io quello di tarini di febbraio e anche a me mi aveva sturato perchè lo avevo fatto con un paio di miei amici e secondo lui lo aveva fatto solo una persona e gli altri lo avevo copiata...cosa non vera...cmq questo mi sembra un po' meno complicato rispetto a quello dei puffi...per le mie capacità diciamo che non è proprio uno scherzo però ci sono a dietro quindi appena ho qualche problema di codice ve lo posto.....grazie a tutti...

[Fabietto206]

[QUOTE=lupoxxx87;31606987@fabietto

radicioni voleva una relazione assurda assieme al progetto...quasi peggiore di quella di chinosi per mips
ed era comunque molto molto puntiglioso anche su cose inutili[/QUOTE]

Non lo so, xkè con Radicioni nn ci ho mai avuto a ke fare!! So solo ke ho provato a fare il progetto "Die Hard" di nov 2009 ma nn ci sono riuscito!!
Forse la migliore era la Gerla!!

Io ora mi sto dedicando a sistemi operativi e ho lasciato un attimo da parte algoritmi xkè è tostissimo!!

[Furla]

se ti riferivi alla mia proposta....



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
forse non hai letto bene la consegna, ad ogni richiesta deve essere ricalcolata la media. il ricalcolo può essere fatto in O(1) se tieni aggiornato l'array, o in O(n) se lo ricostruisci ogni volta; dopo n richieste il tempo di esecuzione sarà quindi O(n) con la mia soluzione (O(nlogn) contando anche i crolli) e O(n^2) con la tua.

[matteo.pata]

forse non hai letto bene la consegna, ad ogni richiesta deve essere ricalcolata la media. il ricalcolo può essere fatto in O(1) se tieni aggiornato l'array, o in O(n) se lo ricostruisci ogni volta; dopo n richieste il tempo di esecuzione sarà quindi O(n) con la mia soluzione (O(nlogn) contando anche i crolli) e O(n^2) con la tua.

Quindi come mi suggerisci di farlo...come tengo aggiornato l'array??una volta caricato con le altezze maggiori dei grattacieli quando faccio un altro inserimento oppure una cancellazione come faccio a tenerlo aggiornato?
se aggiungo un grattacielo basta che controllo che la sua altezza in quella porzione di spiaggia non sia maggiore di quello già presente nell'array ma s einvece cancello come faccio??dammi un'idea e se riesce anche un p' di codice questa cosa ci ho pensato un bel po' ma non mi viene in mente niente...

[lupoxxx87]

carissimo furla...
forse non l'hai letto tu il testo ...

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. [...]

2 Gli eventi di tipo abbattimento cominciano dalla stringa kaboom [...]

3 Gli eventi di tipo costruzione cominciano con la stringa new [...]

La serie di righe è terminata da una riga composta da un solo punto esclamativo, che segnala la fine del
problema.

io vado a calcolare l'array solo quando ho una RICHIESTA, non quando ho un EVENTO.

il vincolo su O(n^2) è proprio per invitare ad EVITARE di CALCOLARE qualcosa di NON NECESSARIO finchè questo non venga espressamente RICHIESTO, visto che O(n^2) si riferisce al numero di EVENTI

[matteo.pata]

Quindi come l'ho pensata va bene tengo un array ed ad ogni richiesta di media mi calcolo un nuovo array...ragazzi datemi risp perchè il tempo diventa sempre meno e l'idea di lupoxx mi sembra buona e anche non troppo difficile...

[lupoxxx87]

la scelta è tua...devi decidere tu come implementare...noi ti diamo solo dei consigli...

[Furla]

io vado a calcolare l'array solo quando ho una RICHIESTA, non quando ho un EVENTO.

hai ragione, ho fatto confusione tra richieste ed eventi.
la scelta tra tenere aggiornato l'array e ricalcolarlo ad ogni richiesta dipende quindi dal rapporto tra richieste ed eventi: se le richieste sono poche rispetto agli eventi, è più conveniente ricalcolare tutto, se invece sono frequenti conviene usare sempre il solito array.

[matteo.pata]

Ragazzi problema:
io ho una riga da leggere da stdin e poi devo memorizzarla all'interno del nodo della lista
la riga è
new pippo 2 5 23.5
oppure
kaboom pippo --> cancellazione
oppure
? -->media
oppure
! --> fine programma

come faccio a dirgli di leggere new e confrontarla con il tag new per poi leggere
la stringa pippo e le misure per poi chiamare la funzione inserimento che fa l'inserimento in lista
per le misure uso

scanf("%d",&variabile)

per leggere la parola io avevo creato una funzione legginome che restituisce il nome letto


char* leggiNome(char c) {
int i = 1;
char *nome = malloc(2 * sizeof(char));
while(c >= 'A' && c <= 'Z') {
nome[i - 1] = c;
nome = (char *)realloc(nome, ++i * sizeof(char)); /* Aggiungiamo un elemento */
c = getchar();
}
nome[i - 1] = '\0'; /* Fine nome */
return nome;
}

Però mi chiedevo come fare per fare tipo uno switch non uno switch perchè non leggo caratteri ma devo leggere sia nomi che caratteri quindi non posso usare uno switch per le varie scelte.
Come potrei fare?
Spero di essere stato chiaro..

[lupoxxx87]

http://www.cplusplus.com/reference/clibrary/cstring/strcmp/

[matteo.pata]

Ragazzi problema help me:help:


FILE *p;
char temp;
char linea[120];
char nome_file[120];
char *comando;
char stringa[120];
char carattere;
int posi,posf;
float altezza,mediaSkyLine=0;



else{
p=fopen(argv[1],"r");
if(p==NULL){
perror("Errore in apertura del file");
exit(1);
}


printf("NewNew York\n");
fscanf(p,"%d",&spiaggia); /* leggo il valore della spiaggia e lo assegno*/

while(!feof(p))
{

fscanf(p,"%s",&linea);
printf("%s\n",&linea);
if(strcmp(linea,"new")==0){
fscanf(p,"%s",&stringa); /*inserimento grattacielo*/
fscanf(p,"%d",&posi);
fscanf(p,"%d",&posf);
fscanf(p,"%f",&altezza);
Grattacieli = inserisci(Grattacieli,posi,posf,altezza,stringa);
stampa(Grattacieli);
}

if(strcmp(linea,"kaboom")==0){
fscanf(p,"%s",&stringa); /*cancellazione grattacielo*/
Grattacieli = cancella(Grattacieli,stringa);
stampa(Grattacieli);
}
if(strcmp(linea,"?")==0){
mediaSkyLine = media(Grattacieli,spiaggia); /* media Skyline*/
printf("la media dello skyline e' %f m \n",mediaSkyLine);
}
if(strcmp(linea,"s")==0){
printf("entro in s");
stampa(Grattacieli);
}
if(strcmp(linea,"!")==0){
printf("\n");
system("PAUSE");
return 0;
}
}
fclose(p);
printf("\n");
system("PAUSE");

return 0;
}

Questa è la chiamata per inserire
listaGrattacielo* inserisci(listaGrattacielo *p, int pos_i,int pos_f,float h,char *n)
in char *n arriva stringa[120] = OOEF che leggo dal file
e giusto poi fare all'interno di inserisci
q->nome=n;
in q->nome cosa ci finisce??


Questo pezzo di codice mi effettua la lettura da file e poi inserisce nella lista grattacieli il problema che alla prima riga che legge che è
new OOEF 2 4 421
la inserisce correttamente con il nome giusto
la seconda riga che è
new UVPV 2 3 67
la inserisce corretta però non riesco a capire perchè cambia il nome del primo elemento nella lista se faccio un altro inserimento tipo
YUPV 2 6 79
lo inserisce con i valori corretti però cambia i nomi di tutti i grattacieli in YUPV.Sto impazzendo non riesco a trovare l'errore se faccio invece l'inserimento da stdin da riga di comando e inserisco le stesse righe presennti nel file che gli passo mi effettua tutti i passaggi correti e non cambia i nomi.quindi il problema penso sia nella lettura da file.
Ragazzi:help: :help: devo consegnare entro domenica e devo corregge questo problema...grazie...

[Furla]

devi allocare dinamicamente le stringhe con la malloc, altrimenti i char* puntano tutti alla stessa area di memoria.