[C++] Progetto Algoritmi

[Narat]

Testo del progetto:

Input atteso dal sistema:
Un file di testo contenente un elenco di stringhe che rappresentano nomi di aeroporti. Tale elenco è da interpretarsi come sequenza di tratte servite da voli diretti (aeroporto di partenza – aeroporto di arrivo) in cui però ciascun nome di aeroporto è inserito su una singola riga.
L’unica assunzione che è possibile fare su tale elenco è la seguente:
la lunghezza massima di ciascuna stringa è di 15 caratteri
Non è possibile fare assunzioni sul contenuto delle stringhe né tantomeno sulla quantità di stringhe presenti nel file. Ciascuna stringa è memorizzata su una singola riga e contiene solo simboli alfanumerici (lettere e numeri) senza spaziature o simboli di punteggiatura. Non possono essere presenti più stringhe sulla stessa riga e la stessa stringa potrebbe essere anche presente più volte nel file.
Un esempio di file in input che il sistema deve accettare (quindi “legale”) è il seguente:

LameziaT
Milano
LameziaT
Roma
Roma
Milano
...

Esso rappresenta un input di tre coppie <partenza-arrivo> di aeroporti. In particolare, esso contiene le tratte dirette <LameziaT-Milano>, <LameziaT-Roma>, <Roma-Milano>.
Una sequenza deve contenere almeno una tratta, quindi un file vuoto o un file con un numero dispari di aeroporti deve essere considerato illegale.
Specifiche del programma da realizzare
Il sistema deve inizialmente leggere da input il nome del file da elaborare e, successivamente, i nomi di due aeroporti da interpretarsi come partenza e arrivo. Attenzione: non si può in nessun modo fissare da programma il nome del file di input. Il programma deve garantire la terminazione con un messaggio di errore se il file non segue le specifiche di formattazione suesposte.
L’output del sistema deve indicare:
⌧ Tutti gli itinerari disponibili tra l’aeroporto di partenza e l’aeroporto di arrivo, ordinati per numero di cambi crescente, secondo il seguente formato (un itinerario per riga):
<Aeroporto1,Aeroporto2, ..., AeroportoN>
Se i due aeroporti non sono collegati da nessun itinerario ammissibile (vedi limitazioni descritte in seguito) è necessario stampare il messaggio “Gli aeroporti richiesti non sono collegati”
N.B. Per itinerario si intende l’elenco degli scali aeroportuali in cui il viaggiatore deve transitare, incluso l’aeroporto di partenza e quello di arrivo specificati nell’input.
Per cambio si intende la necessità di transitare in un aeroporto diverso sia da quello di partenza, sia da quello di arrivo.
Inoltre, a scopo puramente esemplificativo, si deve limitare il numero di cambi massimo da considerare a 3. Ciò vuol dire che gli itinerari da considerare possono elencare al più 5 aeroporti (quello di partenza, quello di arrivo più tre cambi).



Onestamente non so come farlo, se qualcuno ha qualche idea ne sarei molto grato. TNX

[isAlreadyInUse]

Secondo me lo devi fare in C++

[Narat]

ti ringrazio di aver dato una risposta cosi scontata!!!

[BlackAuron]

Sai nulla di teoria dei grafi?
Ogni aereoporto è un nodo. Quello che ti viene chiesto è di trovare tutti i cammini che vanno dal nodo S al nodo E, con un numero massimo di archi pari a 4.
Ora, per risolvere il problema operativamente, dovresti:
1) creare una matrice n*m, dove n è il numero di nodi ( = aereoporti) ed m il numero di archi ( = tratte presenti sul file)
2) ti scegli un qualche tipo di ordinamento sui nodi, e ordini gli archi in modo lessicografico basandoti sull'ordine dei nodi appena stabilito. Con ordine lessicografico intendo che l'arco (a,b) < (c,d) se (a < c) || ((a = c) && (b < d)).
3) riempi la matrice nel seguente modo:
per ogni colonna, metti un -1 nel nodo di partenza relativo all'arco che etichetta la colonna, ed un 1 nel nodo di arrivo. tutto il resto lo setti a 0
4) ti cerchi per la rete un qualsiasi algoritmo che trovi i cammini su un grafo data la matrice di incidenza, e lo implementi.

[stdecden]

Per trovare la tratta piú corta usa l' algoritmo di Dijkstra

[Narat]

grazie per l'aiuto

[Narat]

qualcuno avrebbe una libreria c++ di rappresentazione di GRAFI con matrici di adiacenza?

[Narat]

niente?

[giorgio_terr]

Se vuole io ho una libreria c++ che potrebbe fare al caso suo.
Mi invii nome, cognome o solo la sua matricola universitaria al mio indirizzo email editata


Sarò lieto di inviarle la mia libreria.

[cionci]

E' possibile sapere per quale motivo sono necessari nome, cognome e matricola universitaria ? Ovviamente invito l'utente Narat a non rispondere alla richiesta.

Devo inoltre eliminare il contatto email messo in pubblico in quanto vietato dal regolamento del nostro forum.

[giorgio_terr]

Semplice,
cosi quando valuterò il suo progetto potrò pubblicarne il voto sul forum.

Mi scuso per aver inserito l'email nel post.

[cionci]

Ah...è il suo professore ? Interessante
Comunque nessuno qui avrebbe mai fatto il progetto per intero. Solitamente le discussioni in cui viene chiesto di svolgere per intero un esercizio/progettino scolastico/universitario vengono chiuse direttamente.
In questo caso la discussione è rimasta aperta proprio perché è stato chiesto qualche generico "suggerimento".

[marko.fatto]

Dicesi sgammone in pieno

[Vjoke]

Ma LOOOOOL

Grande il mio prof eh

Oh, certo che il progetto non è proprio semplice... o almeno.. non è semplice fargli completare l'elaborazione in tempi ragionevoli..

[71104]

Ctrl+D!!!!

[]Rik`[]

AMO QUESTO FORUM

[RaouL_BennetH]

mmm... sono però perplesso...

Come faceva a sapere il prof che quel nick era di un suo studente?

Di compiti che richiedono questo tipo di elaborazione ce ne sono a pacchi sulla rete... sarà mica un fake ?!?

Ad ogni modo:

[]Rik`[]

Originariamente inviato da RaouL_BennetH

mmm... sono però perplesso...

Come faceva a sapere il prof che quel nick era di un suo studente?

Di compiti che richiedono questo tipo di elaborazione ce ne sono a pacchi sulla rete... sarà mica un fake ?!?

Ad ogni modo:

magari lo studente ha fatto solo copia incolla del testo e ovviamente così il prof l'ha sgamato, no?

[lorysmile]

Originariamente inviato da RaouL_BennetH

mmm... sono però perplesso...

Come faceva a sapere il prof che quel nick era di un suo studente?

Di compiti che richiedono questo tipo di elaborazione ce ne sono a pacchi sulla rete... sarà mica un fake ?!?

Ad ogni modo:

Che io sappia solo il nostro prof. ha richiesto un esercizio pratico in perl del genere per l'esame... e se c'è qualcosa in internet è ben poco! Io cercavo solo di capire meglio cosa voleva il testo dell'esercizio/esame... perchè in effetti si deve prima capire benissimo cosa fà la fat e le varie sfaccettature del suo funzionamento... e poi ovviamente si deve saper programmare in perl e saper applicare un qualcosa che crei un qualcosa il più simile possibile al funzionamento della FAT -.-' è dura come cosa... ma penso fattibbile anche se in tempi non brevi!!!!!