.dsy:it. - [algoritmi] Progetto di Febbraio "Itinerari"

Pages (8): « 1 2 3 [4] 5 6 7 8 »
Show 150 posts per page

.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [algoritmi] Progetto di Febbraio "Itinerari" (http://www.dsy.it/forum/showthread.php?threadid=2641)

Posted by AlphaGamma on 08-02-2003 02:40:

In questo caso violi le specifiche del progetto che NON DEVE porre limiti alla lunghezza delle strade.
Molto piu' semplicemente, ho deciso di leggere da stdin carattere per carattere, poi col carattere devo ancora decidere cosa fare.

PS: ho messo on line nell'area filez->esame di algoritmi->progetto itinerari un piccolo programmino che genera strade casuali generando un output compatibile con l'input richiesto dal progetto. Potrebbe essere utile quando fate debugging nella costruzione delle strade.

Il link e' questo:
http://www.dsy.it/forum/showthread....44432#post44432

__________________
Attenzio', concentrazio', ritmo e VITALITÀ

Posted by AlphaGamma on 08-02-2003 02:52:

Originally posted by M3lkor
Scusa ma se l'algoritmo è scritto in pseudo codice un motivo c'è... ed è che SEI tu ad adattare il codice ad un algoritmo non il contrario.

Non sono del tutto d'accordo.

Il codice in C in un corso di algoritmi e' direttamente implementabile, modificabile e quindi piu' facilmente comprensibile (perche' e' empiricamente verificabile).
Inoltre il tuo lavoro non deve consistere nel TRADURRE ma nell'ADATTARE il codice esistente.
In altre parole non dobbiamo reinventare la ruota. Tantopiu' che 16 giorni sono pochi.

Comunque dando un occhiata al progetto (molto di sfuggita ad essere sincero) non mi è sembrato un eccessivo casino.

L'implementazione del cammino piu' breve e la cancellazione di tutti i cammini sono algoritmi complessi che richiedono attenzione sia nella scelta della struttura dati che nella implementazione.

Ok, non sono molto esperto di C e di programmazione, so qualcosina della teoria, pero' a me sembra un progetto assolutamente non banale per il poco tempo a disposizione.

__________________
Attenzio', concentrazio', ritmo e VITALITÀ

Posted by Cancer on 08-02-2003 09:36:

Originally posted by lord2y
vers. 1.2

#define DIM 1000

main(){

char stringa[DIM];
/*dimensiono una stringa di 1000*/
scanf("%s", stringa);

}

cmq la scanf mi inizializza a null il puntatore azzerando l'area di memoria...

Cosa intendi per "scanf inizializza a null il puntatore azzerando l'area di memoria"? Guarda ti assicuro che scanf il puntatore non lo tocca proprio...
Comunque se vuoi ti do un consiglio su come leggere una stringa di lunghezza arbitraria (almeno,come farei io,poi ci sono 1000 modi!):
Allochi un area di memoria di N bytes, leggi un carattere alla volta da stdin, se arrivi a leggere N caratteri, reallochi ulteriori N bytes (quindi 2N in tutto) e cosi via...
Ciao!

__________________
You can find all that you need in your mind...If you take the time

Posted by dan on 08-02-2003 09:45:

Cosa ne dite di un albero costituito da nodi con 4 figli a testa (denominati magari N S W E), i cui puntatori possano essere NULL o puntare al nodo che seguono il nodo nelle varie direzioni.

Non so però come implementare il numero di strade passanti per quel nodo!!

D.

Posted by lord2y on 08-02-2003 10:09:

Originally posted by Cancer
Cosa intendi per "scanf inizializza a null il puntatore azzerando l'area di memoria"? Guarda ti assicuro che scanf il puntatore non lo tocca proprio...
Comunque se vuoi ti do un consiglio su come leggere una stringa di lunghezza arbitraria (almeno,come farei io,poi ci sono 1000 modi!):
Allochi un area di memoria di N bytes, leggi un carattere alla volta da stdin, se arrivi a leggere N caratteri, reallochi ulteriori N bytes (quindi 2N in tutto) e cosi via...
Ciao!

infatti ho detto che questa nn era la soluzione giusta..
Per evitare di incorrere in seg fault, problemi di lunghezza di stringa uso un getchar per prendere il singolo carattere ponendo la condizione ... != '\n' .

La scanf la uso solo per prendere in input le coordinate del punto.

:ciao:

Ps s vuoi saperne di più sulla scanf --> da prompt man scanf

__________________
Linux User#271051
Only God can judge me, is that right?
Only God can judge me now
Only God baby, nobody else. All you other motherfuckers get out my business (2Pac)

Posted by lord2y on 08-02-2003 10:13:

Originally posted by AlphaGamma
Non sono del tutto d'accordo.
Il codice in C in un corso di algoritmi e' direttamente implementabile, modificabile e quindi piu' facilmente comprensibile (perche' e' empiricamente verificabile).
Inoltre il tuo lavoro non deve consistere nel TRADURRE ma nell'ADATTARE il codice esistente.
In altre parole non dobbiamo reinventare la ruota. Tantopiu' che 16 giorni sono pochi.

L'implementazione del cammino piu' breve e la cancellazione di tutti i cammini sono algoritmi complessi che richiedono attenzione sia nella scelta della struttura dati che nella implementazione.

Ok, non sono molto esperto di C e di programmazione, so qualcosina della teoria, pero' a me sembra un progetto assolutamente non banale per il poco tempo a disposizione.

apro una parentesi polemica:

il progetto è complesso. Il tempo è poco e il laboratorio di C che accompagnava le lezioni di algoritmi è stato del tutto inutile. Certi aspetti della programmazione in C nn sono stati minimamente visti..E certo esempi di strutture dati simili a quella che dovremo usare per implementare questo progetto non sono neanche stati accenati...
Quindi...........

chiudo la parentesi polemica

__________________
Linux User#271051
Only God can judge me, is that right?
Only God can judge me now
Only God baby, nobody else. All you other motherfuckers get out my business (2Pac)

Posted by Cancer on 08-02-2003 11:28:

Originally posted by lord2y
infatti ho detto che questa nn era la soluzione giusta..
Per evitare di incorrere in seg fault, problemi di lunghezza di stringa uso un getchar per prendere il singolo carattere ponendo la condizione ... != '\n' .

La scanf la uso solo per prendere in input le coordinate del punto.

Ps s vuoi saperne di più sulla scanf --> da prompt man scanf

Mah,dal tuo primo messaggio a riguardo mi sembra che tu volessi rispondere a chi aveva chiesto come leggere una stringa di lunghezza arbitraria...
Comunque se sappiamo tutti come farlo non c'è più nessun problema! :-D

L'unica cosa (e man scanf te lo potra' confermare) e' che scanf non ci pensa proprio a inizializzarti a null il puntatore... (bho, forse ho interpretato ancora male io quello che hai scritto, ma hai proprio detto "cmq la scanf mi inizializza a null il puntatore azzerando l'area di memoria... ").
Ri-Ciao!

__________________
You can find all that you need in your mind...If you take the time

Posted by nous on 08-02-2003 11:35:

Originally posted by M3lkor
Forse una tabella HASH sarebbe interessante da utilizzare...

Melkor

Secondo me sarebbe divertente usare la heap

__________________
Cristian,il Nous che invoglia ^_^

"La capa è troppo in la,e la sbarba è troppo giovane..mi sa che qua si va in bianco"
Ryo Saeba (City Hunter)

Posted by nous on 08-02-2003 11:50:

Originally posted by Wolf
Problema: come cavolo faccio a prendere in ingresso una maledetta stringa di dimensioni qualsiasi??

Copio e incollo dal mio progetto,adattatevelo al vostro caso :

int readline(FILE *stream, char **buffer) {
#define TBSIZE 10
int in_buffers=0;
char tmpbuf[TBSIZE+1]={0};
char *newline;

do {
in_buffers++;
*buffer=realloc(*buffer, in_buffers*TBSIZE*sizeof(char)+1);
if (!(*buffer)) return ERROR_CANT_MALLOC;

if (fgets(tmpbuf,TBSIZE+1,stream)==NULL) {
if(in_buffers==1) return ERROR_EOF;
else return 0;
}

newline=strchr(tmpbuf,'\n');
if(newline) *newline='\0';

strcpy((*buffer)+(in_buffers-1)*TBSIZE, tmpbuf);
} while (!newline);
return 0;

__________________
Cristian,il Nous che invoglia ^_^

"La capa è troppo in la,e la sbarba è troppo giovane..mi sa che qua si va in bianco"
Ryo Saeba (City Hunter)

Posted by rafnet on 08-02-2003 11:52:

Originally posted by Cancer
...
Comunque se sappiamo tutti come farlo non c'è più nessun problema!.....

Calma, calma io no ci ho capito un h, ho usato una normale stringa per prendere in input il percorso che per quanto lungo sia non potrà mai colmare la dimensione di una stringa no?

:ban:

__________________
La vita è una jungla!

Posted by M3lkor on 08-02-2003 12:18:

Originally posted by AlphaGamma
Non sono del tutto d'accordo.
Il codice in C in un corso di algoritmi e' direttamente implementabile, modificabile e quindi piu' facilmente comprensibile (perche' e' empiricamente verificabile).
Inoltre il tuo lavoro non deve consistere nel TRADURRE ma nell'ADATTARE il codice esistente.
In altre parole non dobbiamo reinventare la ruota. Tantopiu' che 16 giorni sono pochi.

L'implementazione del cammino piu' breve e la cancellazione di tutti i cammini sono algoritmi complessi che richiedono attenzione sia nella scelta della struttura dati che nella implementazione.

Ok, non sono molto esperto di C e di programmazione, so qualcosina della teoria, pero' a me sembra un progetto assolutamente non banale per il poco tempo a disposizione.

Ok sono d'accordo su alcuni punti... Diciamo che il tempo a disposizione non è sufficentemente lungo perchè tutti riescano a farlo. Ma rimane comunque una cosa non eccessivamente complessa escludendo il fattore tempo.

Non sono d'accordo sugli algoritmi. Un algoritmo deve essere utilizzabile con goni tipo di linguaggio e quindi non deve essere scritto in un linguaggio specifico proprio perchè noi dovremmo, in teoria, estrapolare dall'algoritmo il codice nel linguaggio che ci interessa. D'altro canto un algoritmo di per sè è un insieme di "istruzioni" che permettono il compimento di un compito in un tempo "x". Che poi tu lo scriva in Java, in C, in C++, in Perl, in CGI, in Algol o in Fortran la cosa cambia relativamente poco...

Questo presumo fosse lo scopo del corso... che poi sia più comodo che gli algoritmi vengano presentati nel linguaggio che poi sarà quello del progetto finale.... beh questo è ovvio che renderebbe le cose più semplici

Melkor

__________________
---Any sufficiently advanced technology is indistinguishable from magic.---

Per favore non mandatemi allegati in Word o PowerPoint.
Si veda http://www.fsf.org/philosophy/no-word-attachments.html

Posted by nous on 08-02-2003 12:36:

Trasudi saggezza,concordo su te in tutto e ti stringo virtualmente la mano

__________________
Cristian,il Nous che invoglia ^_^

"La capa è troppo in la,e la sbarba è troppo giovane..mi sa che qua si va in bianco"
Ryo Saeba (City Hunter)

Posted by Lestat de lioncourt on 08-02-2003 12:45:

Alphagamma, mi spieghi un po' meglio la tua idea per utilizzare gli alberi in questo prog.?
Sul pdf dell'ultima lezione di Fiorentini a pag.5 c'è un esempio in cui usa un albero di ricerca per rappresentare i punti del piano.
Se ogni nodo rappresenta i punti, dove memorizzi l'informazione relativa al reale percorso esistente fra questi punti?
Se tale info è rappresentata dai legami di parentela fra i nodi, l'albero rappresentato non degenera quasi in una lista nel caso del nostro progetto?
A parte che una volta che le strade iniziano ad incrociarsi non ci si trova più davanti ad un albero, ma ad un grafo, perchè si creano dei cicli.

:help:

Io sto usando un grafo non orientato rapp. con liste d'adiacenza

__________________
Non è detto che non ci sia nulla da capire soltanto perchè non si capisce nulla.

(by me)

Posted by AlphaGamma on 08-02-2003 17:39:

Originally posted by M3lkor
Non sono d'accordo sugli algoritmi. Un algoritmo deve essere utilizzabile con goni tipo di linguaggio e quindi non deve essere scritto in un linguaggio specifico proprio perchè noi dovremmo, in teoria, estrapolare dall'algoritmo il codice nel linguaggio che ci interessa. D'altro canto un algoritmo di per sè è un insieme di "istruzioni" che permettono il compimento di un compito in un tempo "x". Che poi tu lo scriva in Java, in C, in C++, in Perl, in CGI, in Algol o in Fortran la cosa cambia relativamente poco...
Melkor

Credo che esistano almeno due modi per approcciarsi a questa materia, uno piu' marcatamente teorico, ed uno piu' orientato ad applicazioni pratiche.

Se l'approccio e' teorico allora va bene una rappresentazione degli algoritmi indipendente dall'architettura dell'elaboratore. Questo e' utile per studi matematici sugli algoritmi, per mostrare il "nudo" algoritmo senza perdersi in "noiose" questioni di contorno.

Se tuttavia la finalita' principale dello studio e' alla fin fine una applicazione pratica, diventa assolutamente prioritario riferirsi ad un reale linguaggio di programmazione, che sappia implementare tutte le caratteristiche degli algoritmi.

In altre parole se sei interessato all'informatica piu' teorica, allo studio della complessita', la struttura degli algoritmi o problemi simili, vale il primo approccio. Se invece vuoi imparare a programmare, ed imparare a farlo bene, segui necessariamente una strada concretamente praticabile e sperimentale.

Questo tipo di scelta e' indipendente dall'esistenza o meno di un progetto finale in C. Si tratta infatti dell'ennesima riproposizione di una questione esistente in moltissimi esami.

Personalmente ho scelto per la seconda, perche' l'informatica mi appassiona per le sue applicazioni e perche' un domani dovrebbe darmi da mangiare.

Pertanto ben vengano delle soluzioni pratiche a quelli annosi problemi che parlano di implementazione pratica, di definizione di variabili, e tutto il resto.

Quindi credo che il lavoro di uno studente di algoritmi debba essere prima di tutto non quello di tradurre in C cose scritte in pseudolinguaggio, ma di adattarle alle proprie esigenze.

Anche Nous che contesta questa mia idea alla fin fine quando ha postato il codice per inserire strighe di dimensione a piacere mica ha usato un pseudolinguaggio. Li ha postati in maniera direttamente utilizzabile ed adattabile. Cioe' in C.

__________________
Attenzio', concentrazio', ritmo e VITALITÀ

Posted by AlphaGamma on 08-02-2003 17:41:

Originally posted by Lestat de lioncourt
Alphagamma, mi spieghi un po' meglio la tua idea per utilizzare gli alberi in questo prog.?
Sul pdf dell'ultima lezione di Fiorentini a pag.5 c'è un esempio in cui usa un albero di ricerca per rappresentare i punti del piano.

Io ho usato un albero binario per memorizzare i punti, ed uno 4-ario per memorizzare gli itinerari.
Devo ancora vedere se funziona.

__________________
Attenzio', concentrazio', ritmo e VITALITÀ

All times are GMT. The time now is 05:58.

Pages (8): « 1 2 3 [4] 5 6 7 8 »
Show all 116 posts from this thread on one page