Ultima modifica:
Questa la specifica di un progetto:
Si consideri un’autostrada descritta come una sequenza di stazioni di servizio. Ogni stazione di servizio si trova
ad una distanza dall’inizio dell’autostrada espressa in chilometri da un numero intero positivo o nullo. Non esistono
due stazioni di servizio aventi la stessa distanza: ogni stazione di servizio è quindi univocamente identificata dalla
sua distanza dall’inizio dell’autostrada.
Ogni stazione di servizio è dotata di un parco veicoli elettrici a noleggio. Ogni veicolo è contraddistinto
dall’autonomia data da una carica delle batterie, espressa in chilometri, da un numero intero positivo. Il parco
veicoli di una singola stazione comprende al più 512 veicoli. Presa a noleggio un’auto da una stazione s, è possibile
raggiungere tutte quelle la cui distanza da s è minore o uguale all’autonomia dell’automobile.
Un viaggio è identificato da una sequenza di stazioni di servizio in cui il conducente fa tappa. Ha quindi inizio
in una stazione di servizio e termina in un’altra, passando per zero o più stazioni intermedie. Si assuma che il
conducente non possa tornare indietro durante il viaggio, e noleggi un’auto nuova ogniqualvolta faccia tappa in
una stazione di servizio. Quindi, date due tappe consecutive s e t, t deve essere sempre più lontana dalla partenza
rispetto a s, e t deve essere raggiungibile usando uno dei veicoli disponibili in s.
L’obiettivo del progetto è il seguente: data una coppia di stazioni, pianificare il percorso con il minor numero
di tappe tra di esse. Nel caso siano presenti più percorsi con lo stesso numero minimo di tappe (cioè a pari merito),
deve essere scelto il percorso che predilige le tappe con distanza più breve dall’inizio dell’autostrada. In altre parole,
si consideri l’insieme degli n percorsi a pari merito P = {p1, p2, . . . pn} dove ogni percorso è una tupla di m elementi
pi = ⟨pi,1, pi,2, . . . pi,m⟩ che equivalgono alla distanza da inizio autostrada di ogni tappa in ordine di percorrenza.
Deve essere scelto l’unico percorso pi tale che non esista un altro pj con le stesse k tappe finali precedute da una
tappa con distanza minore, cioè ∄j, k : ⟨pi,m−k+1, . . . pi,m⟩ = ⟨pj,m−k+1, . . . pj,m⟩ ∧ pj,m−k < pi,m−k.
Di seguito un esempio di autostrada. In questo esempio, il percorso corretto tra la stazione a distanza 20 e
quella a distanza 50 è 20 → 30 → 50 (e non 20 → 45 → 50). Si noti che, invece, 50 → 30 → 20 è il percorso
corretto tra la stazione a distanza 50 e quella a distanza 20 (quindi in direzione da destra a sinistra).
Il file testuale in ingresso contiene una sequenza di comandi, uno per riga, con il seguente formato. Tutti i valori
interi positivi o nulli sono codificabili in 32 bit.
• aggiungi-stazione distanza numero-auto autonomia-auto-1 ... autonomia-auto-n
Aggiunge una stazione, posta alla distanza indicata, dotata di numero-auto, dall’autonomia indicata.
Ad esempio:
aggiungi-stazione 10 3 100 200 300
aggiunge una stazione a distanza 10 dall’inizio dell’autostrada, con un parco di tre veicoli con autonomia
100, 200 e 300 km rispettivamente. Se esiste già una stazione alla distanza indicata, il comando non fa nulla.
Stampa attesa come risposta: aggiunta oppure non aggiunta.
• demolisci-stazione distanza
Rimuove la stazione posta alla distanza indicata, se essa esiste.
Stampa attesa come risposta: demolita oppure non demolita.
• aggiungi-auto distanza-stazione autonomia-auto-da-aggiungere
Se la stazione esiste, aggiunge un’auto alla stessa. È possibile avere più auto con la stessa autonomia.
Stampa attesa come risposta: aggiunta oppure non aggiunta.
• rottama-auto distanza-stazione autonomia-auto-da-rottamare
Rimuove un’automobile dalla stazione indicata, se la stazione esiste ed è dotata di almeno un’automobile
con l’autonomia indicata.
Stampa attesa come risposta: rottamata oppure non rottamata.
• pianifica-percorso distanza-stazione-partenza distanza-stazione-arrivo
Richiede di pianificare il percorso con i vincoli sopra indicati.
Stampa attesa come risposta: le tappe in ordine di percorrenza, rappresentate con la distanza delle stazioni
da inizio autostrada, separate da spazi e alla fine seguite da un a-capo. Devono essere incluse partenza e
arrivo; se coincidono la stazione viene stampata una sola volta. Se il percorso non esiste, stampa nessun
percorso. L’azione di pianificazione non altera le stazioni o il loro parco veicoli. Le stazioni date sono
sicuramente presenti.
Questo invece il mio codice. So che è completamente sbagliato. Soluzioni?
Si consideri un’autostrada descritta come una sequenza di stazioni di servizio. Ogni stazione di servizio si trova
ad una distanza dall’inizio dell’autostrada espressa in chilometri da un numero intero positivo o nullo. Non esistono
due stazioni di servizio aventi la stessa distanza: ogni stazione di servizio è quindi univocamente identificata dalla
sua distanza dall’inizio dell’autostrada.
Ogni stazione di servizio è dotata di un parco veicoli elettrici a noleggio. Ogni veicolo è contraddistinto
dall’autonomia data da una carica delle batterie, espressa in chilometri, da un numero intero positivo. Il parco
veicoli di una singola stazione comprende al più 512 veicoli. Presa a noleggio un’auto da una stazione s, è possibile
raggiungere tutte quelle la cui distanza da s è minore o uguale all’autonomia dell’automobile.
Un viaggio è identificato da una sequenza di stazioni di servizio in cui il conducente fa tappa. Ha quindi inizio
in una stazione di servizio e termina in un’altra, passando per zero o più stazioni intermedie. Si assuma che il
conducente non possa tornare indietro durante il viaggio, e noleggi un’auto nuova ogniqualvolta faccia tappa in
una stazione di servizio. Quindi, date due tappe consecutive s e t, t deve essere sempre più lontana dalla partenza
rispetto a s, e t deve essere raggiungibile usando uno dei veicoli disponibili in s.
L’obiettivo del progetto è il seguente: data una coppia di stazioni, pianificare il percorso con il minor numero
di tappe tra di esse. Nel caso siano presenti più percorsi con lo stesso numero minimo di tappe (cioè a pari merito),
deve essere scelto il percorso che predilige le tappe con distanza più breve dall’inizio dell’autostrada. In altre parole,
si consideri l’insieme degli n percorsi a pari merito P = {p1, p2, . . . pn} dove ogni percorso è una tupla di m elementi
pi = ⟨pi,1, pi,2, . . . pi,m⟩ che equivalgono alla distanza da inizio autostrada di ogni tappa in ordine di percorrenza.
Deve essere scelto l’unico percorso pi tale che non esista un altro pj con le stesse k tappe finali precedute da una
tappa con distanza minore, cioè ∄j, k : ⟨pi,m−k+1, . . . pi,m⟩ = ⟨pj,m−k+1, . . . pj,m⟩ ∧ pj,m−k < pi,m−k.
Di seguito un esempio di autostrada. In questo esempio, il percorso corretto tra la stazione a distanza 20 e
quella a distanza 50 è 20 → 30 → 50 (e non 20 → 45 → 50). Si noti che, invece, 50 → 30 → 20 è il percorso
corretto tra la stazione a distanza 50 e quella a distanza 20 (quindi in direzione da destra a sinistra).
Il file testuale in ingresso contiene una sequenza di comandi, uno per riga, con il seguente formato. Tutti i valori
interi positivi o nulli sono codificabili in 32 bit.
• aggiungi-stazione distanza numero-auto autonomia-auto-1 ... autonomia-auto-n
Aggiunge una stazione, posta alla distanza indicata, dotata di numero-auto, dall’autonomia indicata.
Ad esempio:
aggiungi-stazione 10 3 100 200 300
aggiunge una stazione a distanza 10 dall’inizio dell’autostrada, con un parco di tre veicoli con autonomia
100, 200 e 300 km rispettivamente. Se esiste già una stazione alla distanza indicata, il comando non fa nulla.
Stampa attesa come risposta: aggiunta oppure non aggiunta.
• demolisci-stazione distanza
Rimuove la stazione posta alla distanza indicata, se essa esiste.
Stampa attesa come risposta: demolita oppure non demolita.
• aggiungi-auto distanza-stazione autonomia-auto-da-aggiungere
Se la stazione esiste, aggiunge un’auto alla stessa. È possibile avere più auto con la stessa autonomia.
Stampa attesa come risposta: aggiunta oppure non aggiunta.
• rottama-auto distanza-stazione autonomia-auto-da-rottamare
Rimuove un’automobile dalla stazione indicata, se la stazione esiste ed è dotata di almeno un’automobile
con l’autonomia indicata.
Stampa attesa come risposta: rottamata oppure non rottamata.
• pianifica-percorso distanza-stazione-partenza distanza-stazione-arrivo
Richiede di pianificare il percorso con i vincoli sopra indicati.
Stampa attesa come risposta: le tappe in ordine di percorrenza, rappresentate con la distanza delle stazioni
da inizio autostrada, separate da spazi e alla fine seguite da un a-capo. Devono essere incluse partenza e
arrivo; se coincidono la stazione viene stampata una sola volta. Se il percorso non esiste, stampa nessun
percorso. L’azione di pianificazione non altera le stazioni o il loro parco veicoli. Le stazioni date sono
sicuramente presenti.
Questo invece il mio codice. So che è completamente sbagliato. Soluzioni?
C:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
// Definizione della struttura StazioneServizio
struct StazioneServizio {
int distanza;
int numero_auto;
int *autonomie_auto;
};
// Definizione della struttura Autostrada
struct Autostrada {
int numero_stazioni;
struct StazioneServizio *stazioni;
};
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void bubbleSort(int arr1[], int arr2[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
// Ultimi i elementi sono gia ordinati
for (j = 0; j < n - i - 1; j++) {
if (arr1[j] > arr1[j + 1]) {
swap(&arr1[j], &arr1[j + 1]);
swap(&arr2[j], &arr2[j + 1]);
}
}
}
}
int trovaMassimo(const int *arr, int n) {
int max = arr[0]; // Assumiamo che il primo elemento sia il massimo
for (int i = 1; i < n; i++) {
if (arr > max) {
max = arr;
}
}
return max;
}
int trovaIndice(int *vettore, int n, int valore) {
for (int i = 0; i < n; i++) {
if (vettore == valore) {
return i; // Restituisce l'indice se trova il valore
}
}
return -1; // Restituisce -1 se il valore non e presente nel vettore
}
// Funzione per trovare una stazione di servizio data la distanza
struct StazioneServizio *trovaStazione(struct Autostrada *autostrada, int distanza) {
for (int i = 0; i < autostrada->numero_stazioni; i++) {
if (autostrada->stazioni.distanza == distanza) {
return &autostrada->stazioni;
}
}
return NULL;
}
// Funzione per aggiungere una nuova stazione di servizio all'autostrada
void aggiungiStazione(struct Autostrada *autostrada, int distanza, int numero_auto, int *autonomie_auto) {
// Trova l'indice in cui inserire la nuova stazione in base alla distanza
int indice_inserimento = 0;
while (indice_inserimento < autostrada->numero_stazioni && autostrada->stazioni[indice_inserimento].distanza < distanza) {
indice_inserimento++;
}
// Sposta le stazioni successive per fare spazio alla nuova stazione
autostrada->numero_stazioni++;
autostrada->stazioni = realloc(autostrada->stazioni, autostrada->numero_stazioni * sizeof(struct StazioneServizio));
for (int i = autostrada->numero_stazioni - 1; i > indice_inserimento; i--) {
autostrada->stazioni = autostrada->stazioni[i - 1];
}
// Inserisci la nuova stazione nella posizione corretta
struct StazioneServizio *nuova_stazione = &autostrada->stazioni[indice_inserimento];
nuova_stazione->distanza = distanza;
nuova_stazione->numero_auto = numero_auto;
nuova_stazione->autonomie_auto = malloc(numero_auto * sizeof(int));
memcpy(nuova_stazione->autonomie_auto, autonomie_auto, numero_auto * sizeof(int));
printf("aggiunta stazione\n");
}
// Funzione per rimuovere una stazione di servizio dall'autostrada
void demolisciStazione(struct Autostrada *autostrada, int distanza) {
int indice_stazione = -1;
for (int i = 0; i < autostrada->numero_stazioni; i++) {
if (autostrada->stazioni.distanza == distanza) {
indice_stazione = i;
break;
}
}
if (indice_stazione != -1) {
struct StazioneServizio *stazione = &autostrada->stazioni[indice_stazione];
free(stazione->autonomie_auto);
autostrada->numero_stazioni--;
for (int i = indice_stazione; i < autostrada->numero_stazioni; i++) {
autostrada->stazioni = autostrada->stazioni[i + 1];
}
autostrada->stazioni = realloc(autostrada->stazioni, autostrada->numero_stazioni * sizeof(struct StazioneServizio));
printf("demolita\n");
} else {
printf("non demolita\n");
}
}
// Funzione per aggiungere un'auto a una stazione di servizio
void aggiungiAuto(struct Autostrada *autostrada, int distanza_stazione, int autonomia_auto) {
struct StazioneServizio *stazione = trovaStazione(autostrada, distanza_stazione);
if (stazione) {
stazione->numero_auto++;
stazione->autonomie_auto = realloc(stazione->autonomie_auto, stazione->numero_auto * sizeof(int));
stazione->autonomie_auto[stazione->numero_auto - 1] = autonomia_auto;
printf("aggiunta auto\n");
} else {
printf("non aggiunta\n");
}
}
// Funzione per rimuovere un'auto da una stazione di servizio
void rottamaAuto(struct Autostrada *autostrada, int distanza_stazione, int autonomia_auto) {
struct StazioneServizio *stazione = trovaStazione(autostrada, distanza_stazione);
if (stazione) {
int indice_auto = -1;
for (int i = 0; i < stazione->numero_auto; i++) {
if (stazione->autonomie_auto == autonomia_auto) {
indice_auto = i;
break;
}
}
if (indice_auto != -1) {
stazione->numero_auto--;
for (int i = indice_auto; i < stazione->numero_auto; i++) {
stazione->autonomie_auto = stazione->autonomie_auto[i + 1];
}
stazione->autonomie_auto = realloc(stazione->autonomie_auto, stazione->numero_auto * sizeof(int));
printf("rottamata\n");
} else {
printf("non rottamata\n");
}
} else {
printf("non rottamata\n");
}
}
int cercainlista(int array[], int lunghezza, int valoreDaCercare) {
for (int i = 0; i < lunghezza; i++) {
if (array == valoreDaCercare) {
return i; // Restituisce l'indice se il valore è stato trovato
}
}
return -1; // Restituisce -1 se il valore non è stato trovato
}
void aggiunginlista(int* array[], int valore){
int i=0;
while(array!=0){i++;}
*array=valore;
}
// Funzione per trovare il percorso tra due stazioni di servizio
void pianificaPercorso(int partenza, int arrivo, bool verso, struct Autostrada *autostrada){
//creo lista tra stazioni di partenza e di arrivo
int i=0;int inizio;int fine; int* lista; int delta;
if(verso){
while(autostrada->stazioni.distanza!=arrivo){i++;}
fine=i;
while(autostrada->stazioni.distanza!=partenza){i++;}
inizio=i;
delta=inizio-fine+1;
lista = (int *) malloc(sizeof(int) * (delta));
int a=inizio;
int j=0;
for(a; a>=fine;a--){ lista[j]=autostrada->stazioni[a].distanza;j++;}
}
else{
while(autostrada->stazioni.distanza!=partenza){i++;}
inizio=i;
while(autostrada->stazioni.distanza!=arrivo){i++;}
fine=i;
delta=fine-inizio+1;
lista; lista = (int *) malloc(sizeof(int) * (delta));
int a=inizio;
int j=0;
for(a; a<=fine;a++){ lista[j]=autostrada->stazioni[a].distanza; j++;}
}
struct nodo{
int nome;
struct nodo* prev;
int macchinamassima;
};
int *listanodivisitati=malloc(sizeof(int) * autostrada->numero_stazioni);
struct nodo* coda=malloc(sizeof(struct nodo) * autostrada->numero_stazioni);
struct nodo nodoprincipale;
if(verso){
nodoprincipale.nome=partenza;
nodoprincipale.macchinamassima=trovaMassimo(autostrada->stazioni[inizio].autonomie_auto, autostrada->stazioni[inizio].numero_auto);
listanodivisitati[0]=nodoprincipale.nome;
//printf("CV%d", nodoprincipale.macchinamassima);
}
else{
nodoprincipale.nome=arrivo;
nodoprincipale.macchinamassima=trovaMassimo(autostrada->stazioni[fine].autonomie_auto, autostrada->stazioni[fine].numero_auto);
listanodivisitati[0]=nodoprincipale.nome;
//printf("C%d", nodoprincipale.macchinamassima);
}
coda[0]=nodoprincipale;
int statocoda=0;
int finecoda=autostrada->numero_stazioni;
while(coda[statocoda].nome!=0){
struct nodo nodoattuale=coda[statocoda];statocoda++;
int* nuovechiavi= malloc(delta);
int* listatemp= malloc(delta);
int j=0; int k=0;
for(int i=0; i<delta; i++){
if(!verso && nodoattuale.nome<lista && lista<=(nodoattuale.nome+nodoattuale.macchinamassima) && cercainlista(listanodivisitati, delta, lista)==-1){
listatemp[j]=lista;j++;
}
else if (verso && lista>nodoattuale.nome && nodoattuale.nome>=(lista-nodoattuale.macchinamassima) && cercainlista(listanodivisitati, delta, lista)==-1){
listatemp[j]=lista;j++;
}
else nuovechiavi[k]=lista;k++;
}
memcpy(nuovechiavi, lista, sizeof(int)*delta);
for(int i=0; i<delta; i++){
if(cercainlista(listanodivisitati, delta, listatemp)==-1){
aggiunginlista(&listanodivisitati, listatemp);
struct nodo noddo;
noddo.nome=listatemp;
int indice;
while(autostrada->stazioni[indice].distanza!=listatemp){indice++;}
noddo.macchinamassima=trovaMassimo(autostrada->stazioni[indice].autonomie_auto, autostrada->stazioni[indice].numero_auto);
noddo.prev=&nodoattuale;
coda[finecoda]=noddo; finecoda++;
if(!verso && listatemp==arrivo){
memcpy(&nodoprincipale, &noddo, sizeof(struct nodo));
//nodoprincipale=noddo;
free(coda);
break;
}
if(verso && listatemp==partenza){
memcpy(&nodoprincipale, &noddo, sizeof(struct nodo));
//nodoprincipale=noddo;
free(coda);
break;
}
}
}
}
int percorso[delta];
printf("P%d ", nodoprincipale.nome);
//nodoprincipale=*nodoprincipale.prev;
printf("PR%d ", nodoprincipale.nome);
while(nodoprincipale.nome!=0){
int i=0;
percorso=nodoprincipale.nome;
memcpy(&nodoprincipale, nodoprincipale.prev, sizeof(struct nodo));
}
if(!verso){
for(int a=delta; a>0; a--)printf("%d ", percorso[a]);
}
for(int a=0; a>delta; a++) printf("%d ", percorso[a]);
}
// Funzione principale
int main() {
FILE *file = fopen("open1.txt", "r");
if (file == NULL) {
printf("Impossibile aprire il file.\n");
return 1;
}
struct Autostrada autostrada = {0, NULL};
char comando[50];
int riga=1;
int fscanf_result;
while ((fscanf_result = fscanf(file, "%s", comando)) == 1) {
printf("%d ", riga);riga++;
if (strcmp(comando, "aggiungi-stazione") == 0) {
int distanza, numero_auto;
fscanf_result = fscanf(file, "%d %d", &distanza, &numero_auto);
if (fscanf_result != 2) {
printf("Errore nella lettura dei dati.\n");
break;
}
int *autonomie_auto = (int *)malloc(numero_auto * sizeof(int));
for (int i=0; i < numero_auto; i++) {
fscanf_result = fscanf(file, "%d", &autonomie_auto);
if (fscanf_result != 1) {
printf("Errore nella lettura dei dati.\n");
free(autonomie_auto);
break;
}
}
aggiungiStazione(&autostrada, distanza, numero_auto, autonomie_auto);
free(autonomie_auto);
} else if (strcmp(comando, "demolisci-stazione") == 0) {
int distanza;
fscanf_result = fscanf(file, "%d", &distanza);
if (fscanf_result != 1) {
printf("Errore nella lettura dei dati.\n");
break;
}
demolisciStazione(&autostrada, distanza);
} else if (strcmp(comando, "aggiungi-auto") == 0) {
int distanza_stazione, autonomia_auto;
fscanf_result = fscanf(file, "%d %d", &distanza_stazione, &autonomia_auto);
if (fscanf_result != 2) {
printf("Errore nella lettura dei dati.\n");
break;
}
aggiungiAuto(&autostrada, distanza_stazione, autonomia_auto);
} else if (strcmp(comando, "rottama-auto") == 0) {
int distanza_stazione, autonomia_auto;
fscanf_result = fscanf(file, "%d %d", &distanza_stazione, &autonomia_auto);
if (fscanf_result != 2) {
printf("Errore nella lettura dei dati.\n");
break;
}
rottamaAuto(&autostrada, distanza_stazione, autonomia_auto);
} else if (strcmp(comando, "pianifica-percorso") == 0) {
int partenza, arrivo;
fscanf_result = fscanf(file, "%d %d", &partenza, &arrivo);
if (fscanf_result != 2) {
printf("Errore nella lettura dei dati.\n");
break;
}
//printf("\nPartenza: %d, Arrivo %d\n", partenza, arrivo);
//stampaAutostrada(&autostrada);
if(partenza>arrivo) pianificaPercorso(partenza, arrivo, true, &autostrada);
else pianificaPercorso(partenza, arrivo, false, &autostrada);
} else {
printf("Comando non riconosciuto.\n");
break;
}
}
// Deallocazione delle risorse
for (int i = 0; i < autostrada.numero_stazioni; i++) {
free(autostrada.stazioni.autonomie_auto);
}
free(autostrada.stazioni);
fclose(file);
return 0;
}
void stampaAutostrada(struct Autostrada *autostrada) {
for (int i = 0; i < autostrada->numero_stazioni; i++) {
struct StazioneServizio *stazione = &autostrada->stazioni;
printf("DISTANZA %d AUTO MASSIMA %d\n",
stazione->distanza,
trovaMassimo(stazione->autonomie_auto, stazione->numero_auto));
}
}