001: #include<stdio.h>
002: #include<stdlib.h>
003: 
004: void readdata(FILE*, int *, int *, int *);
005: int* simul(int m, int k, int n);
006: 
007: int main(int argc, char **argv){
008: 
009:   // apro file richiesto ed eventualmente esco in caso di errore
010:   FILE *fp = fopen("elezioni.txt", "r");
011:   if(!fp)
012:   {
013:     perror("");
014:     exit(EXIT_FAILURE);
015:   }
016: 
017:   int m, k, n;
018: 
019:   while(1)
020:   {
021: 
022:     // leggo dati
023:     readdata(fp, &m, &k, &n);
024:     // se m = 0 devo terminare
025:     if(!m) 
026:       exit(0);
027: 
028:     // stampo subito l'incipit
029:     printf("%d estratti su %d persone usando %d per la conta: ", n, m, k);
030: 
031:     int *eletti = simul(m, k, n);
032: 
033:     for(int i = 0; i < n; ++i)
034:       printf("%d, ", eletti[i]);
035:     printf("\b\b \n"); // little trick
036: 
037:     free(eletti);
038:   }
039: 
040: 
041:   fclose(fp);
042:   return 0;
043: }
044: 
045: void readdata(FILE* fp, int *m, int *k, int *n)
046: {
047:   // inizializzo i 3 valori a 0 (se la lettura fallisce rimangono a 0)
048:   *m = 0;
049:   *k = 0;
050:   *n = 0;
051: 
052:   // leggo i 3 numeri da file (se la lettura fallisce rimangono a 0)
053:   fscanf(fp, "%d %d %d", m, k, n);
054: 
055: }
056: 
057: int* simul(int m, int k, int n)
058: {
059:   // definisco struttura, banalmente un array di m elementi che alloco dinamicamente usando VLA visto che lo uso solo internamente
060:   int persone[m];
061: 
062:   // li inizializzo assegnando numero da 1 a m
063:   for(int i=0; i < m; ++i)
064:     persone[i] = i + 1;
065: 
066:   // uso variabile per tener traccia di quante persone rimangono nel ciclo
067:   int rimasti = m;
068: 
069:   // variabile per tener traccia di dove sono a contare (inizialmente il primo elemento)
070:   int indice = 0;
071: 
072:   // ciclo che termina solo quando sono "rimasti" n persone
073:   // per "eliminare" chi viene scelto pongo a 0 il relativo valore nell'array
074:   // va da se' che per "contare" devo saltare gli elementi gia' eliminati ovvero quelli posti a 0
075:   while(rimasti > n)
076:   {
077:     // conto k elementi (ma attenzione sono gia' sul primo elemento quindi mi devo spostare di k-1)
078:     for(int i = 1; i < k; ++i)
079:     {
080:       // incremento indice con cui tengo conto di come mi sposto nell'array
081:       // uso il % per fare in modo che quando vado oltre alla fine dell'array torno indietro all'inizio
082:       // ripeto ogni volta che incontro uno 0
083:       do
084:       {
085:   indice = (indice + 1) % m;
086:       } while(persone[indice] == 0);
087:     }
088: 
089:     // azzero elemento dove sono arrivato a contare
090:     persone[indice] = 0;
091: 
092:     // aggiorno conto persone rimaste
093:     --rimasti;
094: 
095:     // incremento nuovamente indice in quanto ripartiro' a contare dall'elemento successivo ancora rimanente
096:     // stesso approccio di prima
097:     do
098:     {
099:       indice = (indice + 1) % m;
100:     } while(persone[indice] == 0);
101: 
102:   }
103: 
104:   // alloco array da restituire (qui non posso usare VLA)
105:   int *eletti = malloc(sizeof(int) * n);
106: 
107:   // trasferisco in eletti[]  gli elementi non nulli di persone[]
108:   for(int i=0, j = 0; i < m; ++i)
109:     if(persone[i])
110:       eletti[j++] = persone[i]; // j lo uso come indice array di destinazione
111: 
112:   return eletti;
113: 
114: }
115: 
116: