Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 20.Esercitazione di laboratorio: Problema del venditore Seconda parte


Esercizio

  • Si consideri nuovamente il problema del venditore introdotto nella precedente lezione di laboratorio. Si implementino in modo efficiente, descrivendone le scelte opportune e le complessità asintotiche, le seguenti due operazioni:
  • Il venditore vuole vendere una connessione ad internet via cavo ai suoi clienti. Implementare in linguaggio C una funzione efficiente che permetta di definire la lunghezza minima di cavo necessaria per collegare tutte le città, partendo dalla città del venditore e sfruttando soltanto i collegamenti esistenti tra le città (senza tener necessariamente conto delle loro direzioni).

Esercizio

Si supponga inoltre che una volta completato il lavoro precedente, il venditore voglia visitare tutte le città per riscuotere il pagamento del servizio dato. Si implementi dunque una funzione efficiente in linguaggio C che permetta di visitare tutte le città, rispettando i collegamenti e le direzioni esistenti tra le varie città. Tale funzione deve indicare:

  • l’ordine di visita
  • la distanza totale percorsa
  • la somma riscossa
  • le eventuali città che non sono raggiungibili

Esercizio

  • Le funzioni precedenti devono gestire anche la possibilità di modifica del numero di città e di collegamenti. In pratica, se un collegamento tra due città salta, bisogna ristabilire il collegamento internet tra per tutte le città utilizzando la parte di rete rimanente.
  • Si implementino in linguaggio C le operazioni precedenti utilizzando come struttura dati di appoggio un grafo, indipendentemente dal fatto che esso sia rappresentato con liste di adiacenza o con matrice di adiacenza.
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion