Facciamo un piccolo programma in Python che ci permetta di gestire le distanze da percorrere tra due stazioni, di partenza ed arrivo.
Abbiamo le seguenti tratte:
| Stazione A | Stazione B | Distanza |
| Firenze | Bologna | 100km |
| Firenze | Roma | 250km |
| Roma | Napoli | 200km |
| Bologna | Milano | 220km |
| Bologna | Venezia | 150km |
Ogni tratta è percorribile sia in andata che in ritorno. Quello che vogliamo è che il programma ci permetta di inserire due città e calcolare la distanza minima da percorrere e le stazioni da attraversare.
Anzitutto vediamo come sono disposti i nodi dell’intero percorso:
Notiamo che in questa configurazione elementare solo Bologna ha 3 rami, mentre tutte le altre città hanno solo 2 rami ciascuna.
Potremmo affrontare l’esercizio lavorando sui nodi oppure sulle tratte. In questa soluzione lavorerò sulle tratte.
Cominciamo quindi creando anzitutto una classe che ci permetta di descrivere ogni tratta come abbiamo visto nel mandato dell’esercizio.
|
1 2 3 4 5 6 |
class Tratta(): def __init__(s,citta1,citta2,distanza): s.__citta_a = citta1 s.__citta_b = citta2 s.__distanza = distanza |
In questo modo dichiariamo 3 variabili private per registrare le due città della tratta e la rispettiva distanza.
Adesso registriamo tutte le tratte in una lista, nel modo seguente:
|
1 2 3 4 5 6 |
tratte = [] tratte.append(Tratta("Firenze","Bologna",100)) tratte.append(Tratta("Firenze","Roma",250)) tratte.append(Tratta("Roma","Napoli",200)) tratte.append(Tratta("Bologna","Milano",220)) tratte.append(Tratta("Bologna","Venezia",150)) |
Ora cominciamo a pensare all’algoritmo che potrebbe permetterci di calcolare il percorso.
Immaginiamo anzitutto la soluzione più semplice, dove io penso di andare da Firenze a Napoli. Su questa tratta non ci sono diramazione e sostanzialmente il percorso che dovrà venire fuori sarà Firenze – Roma – Napoli.
Fase 1:
Faccio un ciclo su ogni elemento della lista tratte[] e cerco anzitutto dove è presente la città di partenza. Siccome la città può essere sia in A che in B, per ogni oggetto Tratta dovrò implementare un metodo all’interno dell’oggetto stesso che mi permetta di valutare se la città sia presente in modo comodo. Implementiamo quindi la classe nel modo seguente:
|
1 2 3 4 5 6 7 8 9 |
class Tratta(): def __init__(s,citta1,citta2,distanza): s.__citta_a = citta1 s.__citta_b = citta2 s.__distanza = distanza def presente(s,citta): return citta in [s.__citta_a,s.__citta_b] |
Il metodo presente(citta) mi permette di valutare se la città sia presente nella tratta.
Fase 2:
Se trovo la città di partenza su una tratta allora controllo se l’altra città della tratta sia quella di arrivo. Allo stesso tempo registro la città di partenza all’interno di una lista percorso[] in modo da metterla come partenza del percorso complessivo.
Quindi se l’altra città è quella di arrivo posso chiudere il percorso, altrimenti passo il controllo sull’altra città.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
def calcolatore(da,a,percorso=[]): # aggiungo la partenza al percorso percorso.append(da) # comincio a controllare tutte le tratte for t in tratte: # se la città di partenza è sulla tratta allora analizzo la tratta if t.presente(da): # se l'altra città è presente allora la aggiungo al percorso if t.presente(a): percorso.append(a) # altrimenti controllo la partenza e l'arrivo sull'altra città else: calcolatore(t.altra(da),a,[]+percorso) |
Quando mi trovo nella riga 10 capisco anche che ho trovato la fine del percorso, quindi posso salvare l’intero percorso da qualche parte. Siccome potrei avere molteplici percorsi possibili decido di salvare il percorso in una lista globale chiamata percorsi = []
Modifichiamo quindi il codice nel modo seguente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
def calcolatore(da,a,percorso=[]): # aggiungo la partenza al percorso percorso.append(da) # comincio a controllare tutte le tratte for t in tratte: # se la città di partenza è sulla tratta allora analizzo la tratta if t.presente(da): # se l'altra città è presente allora la aggiungo al percorso if t.presente(a): percorso.append(a) percorsi.append(percorso) # altrimenti controllo la partenza e l'arrivo sull'altra città else: calcolatore(t.altra(da),a,[]+percorso) |
Adesso analizziamo due aspetti dell’ultima istruzione, quella dove richiamo la funzione.
|
1 |
calcolatore(t.altra(da),a,[]+percorso) |
Anzitutto voglio tirare fuori dalla tratta l’altra città, rispetto alla città di partenza. Per farlo implemento la classe principale nel modo seguente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Tratta(): def __init__(s,citta1,citta2,distanza): s.__citta_a = citta1 s.__citta_b = citta2 s.__distanza = distanza def presente(s,citta): return citta in [s.__citta_a,s.__citta_b] def altra(s,citta): if s.__citta_a == citta: return s.__citta_b return s.__citta_a |
In questo modo quando mi trovo per esempio sulla tratta Firenze – Roma posso passare all’oggetto tratta Firenze, che conosco essendo il punto di partenza e chiedergli di darmi l’altra città della tratta, in questo caso Roma.
Il secondo aspetto che voglio evidenziare è che passo la lista percorso[] alla funzione medesima in partenza dall’altra città, per farlo utilizzo l’istruzione []+percorso, in caso contrario percorso passerebbe per riferimento e qualora fosse passato su più rami verrebbe elaborato contemporaneamente da più rami. Io invece voglio che resti un oggetto singolo e lineare per ogni percorso.
Arrivati a questo punto del codice la situazione è la seguente:
- Prendo in input partenza DA = Firenze e A = Napoli
- Aggiungo DA (Firenze) al
percorso[] - Passo a setaccio la lista delle
tratte[] - In posizione 0 trovo la tratta Firenze – Bologna a cui DA appartiene
- Controllo se A (Napoli) appartiene alla tratta
- Dal momento che non appartiene, prendo l’altra città della tratta, ovvero Bologna e la passo come nuovo DA alla funzione medesima
- La funzione ricomincia e aggiungendo DA (Bologna) al
percorso[] - Scorro la lista delle
tratte[]in cerca di DA (Bologna) - Trovo che DA nella posizione 0 sulla tratta Firenze – Bologna
- LOOP INFINITO!
Fase 3:
Devo evitare il loop infinito in cui il percorso possa tornare indietro. Per farlo modifico la mia funzione aggiungendo il seguente controllo all’inizio:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
def calcolatore(da,a,percorso=[]): # interrompo la funzione qualora la destinazione sia già nel percorso if da not in percorso: # aggiungo la partenza al percorso percorso.append(da) # comincio a controllare tutte le tratte for t in tratte: # se la città di partenza è sulla tratta allora analizzo la tratta if t.presente(da): # se l'altra città è presente allora la aggiungo al percorso if t.presente(a): percorso.append(a) percorsi.append(percorso) # altrimenti controllo la partenza e l'arrivo sull'altra città else: calcolatore(t.altra(da),a,[]+percorso) |
In questo modo controllo che il punto di partenza DA non sia già presente nel percorso[].
Adesso ricomincio a controllare il mio algoritmo da capo:
- Prendo in input partenza DA = Firenze e A = Napoli
- Aggiungo DA (Firenze) al
percorso[] - Passo a setaccio la lista delle
tratte[] - In posizione 0 trovo la tratta Firenze – Bologna a cui DA appartiene
- Controllo se A (Napoli) appartiene alla tratta
- Dal momento che non appartiene, prendo l’altra città della tratta, ovvero Bologna e la passo come nuovo DA alla funzione medesima
- La funzione ricomincia e aggiungendo DA (Bologna) al
percorso[] - Scorro la lista delle
tratte[]in cerca di DA (Bologna) - Trovo che DA nella posizione 0 sulla tratta Firenze – Bologna
- L’altra città (Firenze) è uguale ad A? No, quindi ripasso l’altra città come nuovo DA alla funzione medesima
- La funzione si interrompe, perché DA (Firenze) è già presente in
percorso[] - Torno al punto 9
- In posizione 3 trovo Bologna – Milano dentro
tratte[]dove appartiene il mio DA - Questo pezzo di codice adesso si ripete uguale a quello tra 10 e 12 fino a chiudersi su Milano e Venezia che terminano il percorso
- Trono al punto 3
- In posizione 1 trovo la tratta Firenze – Roma a cui DA (Firenze) appartiene
- Controllo se A (Napoli) appartiene alla tratta
- Dal momento che non appartiene, prendo l’altra città della tratta, ovvero Roma e la passo come nuovo DA alla funzione medesima
- La funzione ricomincia e aggiungendo DA (Roma) al
percorso[] - Scorro la lista delle
tratte[]in cerca di DA (Bologna) - Trovo che DA nella posizione 1 sulla tratta Firenze – Roma
- L’altra città (Firenze) è uguale ad A? No, quindi ripasso l’altra città come nuovo DA alla funzione medesima
- La funzione si interrompe, perché DA (Firenze) è già presente in
percorso[] - Torno al punto 20
- Trovo che DA nella posizione 2 sulla tratta Roma – Napoli
- Controllo se A (Napoli) appartiene alla tratta
- Napoli appartiene alla tratta nel pezzo di codice
if t.presente(a) - A questo punto aggiungo A (Napoli) alla fine di
percorso[] - Aggiungo il
percorso[]aipercorsi[]con l’istruzionepercorsi.append(percorso)
Fase 4:
Apporto ancora un paio di correzioni tecniche alla mia funzione per evitare inutili duplicati.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
def calcolatore(da,a,percorso=[]): if a in percorso: if percorso not in percorsi: percorsi.append(percorso) return if da not in percorso: percorso.append(da) for t in tratte: if t.presente(da): if t.presente(a): percorso.append(a) percorsi.append(percorso) else: calcolatore(t.altra(da),a,[]+percorso) |
A questo punto posso scrivere la parte principale del mio programma con:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
while True: percorsi = [] print "-- calcola percorso --" print "DA: ", da = input() print "A: ", a = input() calcolatore(da,a,[]) for i, p in enumerate(percorsi): print "-- soluzione %s--" % (i+1) print "Percorso: " + " - ".join(p) |
Per stampare il percorso faccio una join su ogni percorso che trovo dentro a percorsi[]
Fase 5:
Aggiungo soltanto un metodo per calcolare le distanze. Potrei farlo anche in modi più ottimizzato, ma per le finalità di questo esercizio ci accontentiamo di percorrere tutte le stazioni, esclusa l’ultima, e di calcolare la distanza tra la stazione corrente e la successiva sommandole tutte insieme.
A tale proposito aggiunto un metodo che mi permetta di valutare se 2 città appartengono entrambe alla tratta ed un getter per la distanza.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Tratta(): def __init__(s,citta1,citta2,distanza): s.__citta_a = citta1 s.__citta_b = citta2 s.__distanza = distanza def presente(s,citta): return citta in [s.__citta_a,s.__citta_b] def altra(s,citta): if s.__citta_a == citta: return s.__citta_b return s.__citta_a def getDistanza(s): return s.__distanza def questa(s,citta1,citta2): return citta1 in [s.__citta_a,s.__citta_b] and citta2 in [s.__citta_a,s.__citta_b] |
La funzione quindi sarà:
|
1 2 3 4 5 6 7 |
def distanziatore(percorsi): distanza = 0 for i in range(len(percorsi)-1): for t in tratte: if t.questa(percorsi[i],percorsi[i+1]): distanza += t.getDistanza() return distanza |
Fatto tutto questo posso completare il mio programma nella sua versione finale nel modo seguente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
class Tratta(): def __init__(s,citta1,citta2,distanza): s.__citta_a = citta1 s.__citta_b = citta2 s.__distanza = distanza def presente(s,citta): return citta in [s.__citta_a,s.__citta_b] def altra(s,citta): if s.__citta_a == citta: return s.__citta_b return s.__citta_a def getDistanza(s): return s.__distanza def questa(s,citta1,citta2): return citta1 in [s.__citta_a,s.__citta_b] and citta2 in [s.__citta_a,s.__citta_b] tratte = [] tratte.append(Tratta("Firenze","Bologna",100)) tratte.append(Tratta("Firenze","Roma",250)) tratte.append(Tratta("Roma","Napoli",200)) tratte.append(Tratta("Bologna","Milano",220)) tratte.append(Tratta("Bologna","Venezia",150)) def calcolatore(da,a,percorso=[]): if a in percorso: if percorso not in percorsi: percorsi.append(percorso) return if da not in percorso: percorso.append(da) for t in tratte: if t.presente(da): if t.presente(a): percorso.append(a) percorsi.append(percorso) else: calcolatore(t.altra(da),a,[]+percorso) def distanziatore(percorsi): distanza = 0 for i in range(len(percorsi)-1): for t in tratte: if t.questa(percorsi[i],percorsi[i+1]): distanza += t.getDistanza() return distanza while True: percorsi = [] print "-- calcola percorso --" print "DA: ", da = input() print "A: ", a = input() calcolatore(da,a,[]) for i, p in enumerate(percorsi): print "-- soluzione %s--" % (i+1) print "Percorso: " + " - ".join(p) print "Distanza: %.2fkm" % distanziatore(p) |
Se volessimo complicare un po’ lo schema potremmo aggiungere altre tratte:
|
1 2 3 4 5 6 7 8 |
tratte.append(Tratta("Milano","Venezia",260)) tratte.append(Tratta("Milano","Torino",140)) tratte.append(Tratta("Bologna","Torino",340)) tratte.append(Tratta("Firenze","Livorno",90)) tratte.append(Tratta("Firenze","Pisa",90)) tratte.append(Tratta("Livorno","Pisa",30)) tratte.append(Tratta("Grosseto","Pisa",160)) tratte.append(Tratta("Roma","Grosseto",190)) |
Ed ottenere una versione finale del programma in questo modo:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
class Tratta(): def __init__(s,citta1,citta2,distanza): s.__citta_a = citta1 s.__citta_b = citta2 s.__distanza = distanza def presente(s,citta): return citta in [s.__citta_a,s.__citta_b] def altra(s,citta): if s.__citta_a == citta: return s.__citta_b return s.__citta_a def getDistanza(s): return s.__distanza def questa(s,citta1,citta2): return citta1 in [s.__citta_a,s.__citta_b] and citta2 in [s.__citta_a,s.__citta_b] tratte = [] tratte.append(Tratta("Firenze","Bologna",100)) tratte.append(Tratta("Firenze","Roma",250)) tratte.append(Tratta("Roma","Napoli",200)) tratte.append(Tratta("Bologna","Milano",220)) tratte.append(Tratta("Bologna","Venezia",150)) tratte.append(Tratta("Milano","Venezia",260)) tratte.append(Tratta("Milano","Torino",140)) tratte.append(Tratta("Bologna","Torino",340)) tratte.append(Tratta("Firenze","Livorno",90)) tratte.append(Tratta("Firenze","Pisa",90)) tratte.append(Tratta("Livorno","Pisa",30)) tratte.append(Tratta("Grosseto","Pisa",160)) tratte.append(Tratta("Roma","Grosseto",190)) def calcolatore(da,a,percorso=[]): if a in percorso: if percorso not in percorsi: percorsi.append(percorso) return if da not in percorso: percorso.append(da) for t in tratte: if t.presente(da): if t.presente(a): percorso.append(a) percorsi.append(percorso) else: calcolatore(t.altra(da),a,[]+percorso) def distanziatore(percorsi): distanza = 0 for i in range(len(percorsi)-1): for t in tratte: if t.questa(percorsi[i],percorsi[i+1]): distanza += t.getDistanza() return distanza while True: percorsi = [] print "-- calcola percorso --" print "DA: ", da = input() print "A: ", a = input() calcolatore(da,a,[]) for i, p in enumerate(percorsi): print "-- soluzione %s--" % (i+1) print "Percorso: " + " - ".join(p) print "Distanza: %.2fkm" % distanziatore(p) |
Il nostro nuovo programma genererà un output come questo:
