001: #include<stdio.h>
002: #include<stdlib.h>
003: #include<time.h>
004: #include<math.h>
005: 
006: // definizione struttura per array punti
007: struct punto
008: {
009:   double         x, y; // coordinate
010: };
011: 
012: double costo(struct punto *, int);
013: 
014: int main(int argc, char **argv){
015: 
016:   srand(time(NULL));    
017: 
018:   // per #1 capisco se nome file era passato su linea comando altrimenti chiedo all'utente
019:   FILE *fp;
020:   if(argc < 2)
021:   {
022:     char nome_file[1000];
023:     printf("Inserisci il nome del file da analizzare: ");
024:     scanf("%s", nome_file);
025:     fp = fopen(nome_file, "r");
026:   }
027:   else
028:   {
029:     fp = fopen(argv[1], "r");
030:   }
031:   // Nota: in base al testo potevo comunque limitarmi a una sola delle due alternative
032: 
033:   if(!fp)
034:   {
035:     perror("");
036:     exit(EXIT_FAILURE);
037:   }
038: 
039:   int npunti;   // numero punti da gestire
040:   fscanf(fp, "%d", &npunti);
041: 
042:   struct punto p[npunti];  // uso VLA per allocare array punti
043: 
044:   for(int i = 0; i < npunti; ++i)
045:     fscanf(fp, "%lg %lg", &p[i].x, &p[i].y);
046: 
047:   double L = costo(p, npunti);  // invoco la funzione costo() per calcolare la lunghezza del percorso
048: 
049:   double T = 50.0;              // inizializzo "temperatura"
050: 
051:   int niter = 0;                // per contare numero iterazioni
052: 
053:   do
054:   {
055:     ++niter; // incremento comunque numero iterazioni
056: 
057:     // calcolo due indici a caso di due punti da scambiare
058:     int i1, i2;
059:     i1 = rand()%npunti;
060:     do
061:     {
062:       i2 = rand()%npunti;
063:     }
064:     while(i1 == i2);
065: 
066:     // scambio i due punti
067:     struct punto tmp = p[i1];
068:     p[i1] = p [i2];
069:     p[i2] = tmp;
070: 
071:     // calcolo lunghezza percorso dopo aggiornamento
072:     double Lnew = costo(p, npunti); 
073: 
074:     // calcolo variazione
075:     double D = Lnew - L;
076: 
077:     if(D <= 0) // ripeto 
078:     {
079:       L = Lnew; // ma mi salvo la lunghezza aggiornata del percorso
080:       T *= 0.995;
081:       continue; 
082:     }
083: 
084:     // qui ci arrivo solo se D < 0
085: 
086:     if(rand()/(double)RAND_MAX < exp(-D/T)) // rand()/RAND_MAX e' numero tra 0 e 1, se inferiore a e^(-D/T) ok scambio
087:     {
088:       //printf("DEBUG: %g\n", exp(-D/T));
089:       L = Lnew; // ma mi salvo la lunghezza aggiornata del percorso
090:       T *= 0.995;
091:     } 
092:     else
093:     {
094:       // se arrivo qui devo annullare lo scambio (li riscambio)
095:       tmp = p[i1];
096:       p[i1] = p [i2];
097:       p[i2] = tmp;
098:     }
099: 
100:   }
101:   while(T >= 0.01 && niter < 500000);
102: 
103:   printf("La sequenza contiene %d punti, ho terminato con T = %g e dopo %d iterazioni, la lunghezza del percorso stimato e' %g\n", npunti, T, niter, L);
104:   printf("Sequenza ottenuta:\n");
105:   for(int i = 0; i < npunti; ++i)
106:     printf("%+.2f,%+.2f\n", p[i].x, p[i].y);
107: 
108: 
109:   return 0;
110: }
111: 
112: 
113: // questa funzione prende in input array di punti e loro numerosita'
114: // calcola e restituisce la lunghezza del percorso complessivo effettuato spostandosi
115: // da un punto all'altro e ritornando all'inizio
116: double costo(struct punto *p, int n)
117: {
118:   double l = 0;  
119:   for(int i = 0; i < n - 1; ++i) // ciclo su tutti i punti (lascio fuori l'ultimo che usero' dopo)
120:     l += sqrt((p[i].x - p[i+1].x)*(p[i].x - p[i+1].x) + (p[i].y - p[i+1].y)*(p[i].y - p[i+1].y));
121: 
122:   // chiusura anello
123:   l += sqrt((p[n - 1].x - p[0].x)*(p[n - 1].x - p[0].x) + (p[n - 1].y - p[0].y)*(p[n - 1].y - p[0].y));
124: 
125:   return l;
126: }
127: 
128: