[C]programma da realizare in C su grattacieli

[WarDuck]

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

Originariamente inviato da 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

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]

Originariamente inviato da lupoxxx87

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]

Originariamente inviato da lupoxxx87

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]

Originariamente inviato da Furla

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]

Originariamente inviato da lupoxxx87

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/c...string/strcmp/

[matteo.pata]

Ragazzi problema help me

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