Problème 3 (VIRUS)

Une population de virus évolue dans un lieu assimilé à un tableau carré nxn. Un virus occupe une seule case et une case contient au plus un virus. Deux cases sont dites voisines si elles ont un sommet ou un côté communs. Deux virus sont dits voisins s'ils occupent deux cellules voisines. On appelle génération toute répartition d'un nombre de virus dans ce tableau. L'évolution d'une génération à une autre se fait selon les règles suivantes :

1 – un virus qui a au plus deux voisins (inférieur ou égal à 2), meurt de solitude.

2 – un virus qui a au moins 5 voisins (supérieur ou égal à 5), meurt asphyxié.

3 – une cellule vide ayant exactement trois cellules voisines occupées par des virus donne naissance à un nouveau virus.

On se propose d'écrire un programme qui saisit un entier n (5<n<20). Cet entier sera le côté du tableau carré où va évoluer la population des virus. Ensuite, il saisit une génération initiale de la population de ces virus. Cette entrée est composée d'une suite de couples (i, j) où 1£i£n et 1£j£n  représentant les coordonnées des cellules qui vont contenir des virus.

Le programme demande ensuite l'ordre m (1<m) de la génération qu'on voudra trouver en partant de la génération initiale.

On pourra envisager la saisie à partir d'un fichier de données (GEN_INIT.TXT)  organisé ainsi :

·        1^ère ligne contient n.

·        2^ème ligne contient m.

·        une suite de lignes comportant chacune un couple d'entiers séparés par un espace. Chaque couple d'entiers représente les deux coordonnées de la cellule où il y aura un virus.

La génération cherchée sera affichée à l'écran sous forme d'un tableau où un virus est représenté par une étoile.

Le jeu de tests pour l'évaluation

/*Ce programme permet de simuler l'évolution d'une population de virus
Cette évolution suit un certain nombre de règles telles que:
1- Un virus qui a au plus deux voinsins meurt par solitude
2- Un virus qui a plus de 4 voinsins meurt par asphyxie
3- Une cellule vide entourée par trois virus, dans les cellules voisines, donne naissance à un nouveau virus

En exécution le programme nécessite deux paramètres :

-         Le nom du fichier contenant la population initiale de virus
-         Le nom du fichier qui va contenir le résultat

Exemple: c:>virus gen_init1.txt genout1.txt

*/

/*Ce programme permet de simuler l'évolution d'une population de virus
Cette évolution suit un certain nombre de règles telles que:
1- Un virus qui a au plus deux voinsins meurt par solitude
2- Un virus qui a plus de 4 voinsins meurt par asphyxie
3- Une cellule vide entourée par trois virus, dans les cellules voisines, donne naissance à un nouveau virus

*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxn 20
#define minn 5
int tvirus[maxn][maxn];//tableau de virus
FILE *fvirus;//fichier source de virus
FILE *fresultat;//fichier source de virus
int m;//ordre de génération
/* Programme Principal*/
int main(int argc, char *argv[])

{
int Remplir_tvirus(char *);
void Afficher_tvirus(int);
void Evolution(int, int[maxn][maxn]);
void Sortir_resultat(char *,int,int);
int ordre;//compteur ordre génération
int i,j,n;
if(argc != 3)

{
fprintf(stderr,"\nErreur parametres à la commande: nomprog fichiervirus fichieresultat\n");
return(1);
}

fvirus=fopen(argv[1],"r");
/*Initialisation du tableau tvirus à zéro*/
for (i=0;i<maxn;i++)
for (j=0;j<maxn;j++) tvirus[i][j]=0;
n=Remplir_tvirus(argv[1]);
fclose(fvirus);
Afficher_tvirus(n);

//Evolution de la génération
printf("Donner l'ordre d\'évolution:");
scanf("%d",&m);
for(ordre=1;ordre<=m;ordre++)

{
Evolution(n,tvirus);
Afficher_tvirus(n);
}

printf("Tapez une touche pour quitter...");
getchar();

//Affichage et Sortie du résultat
printf("\nEcriture du résultat dans le fichier %s",argv[2]);
Afficher_tvirus(n);
Sortir_resultat(argv[2],n,m);
printf("\nFin Programme Virus");
printf("Tapez une touche pour quitter...");
getchar();
return(0);
}

// Les fonctions du programme

//Ecriture du résultat dans un fichier

void Sortir_resultat(char *nomfresult,int ns,int ms)

{
int is,js;
fresultat=fopen(nomfresult,"w+");
fprintf(fresultat, "%d\n",ms);
          for (is=0;is<ns;is++)
          for (js=0;js<ns;js++)
          if(tvirus[is][js]==1)
          fprintf(fresultat,"%d %d\n",is+1,js+1);
fclose(fresultat);
}

//Evolution d'une génération à une autre
void Evolution(int ne,int tviruse[maxn][maxn])

{
int nvirusvois;//nombre de virus voisins
int ie,je,i1,j1;
//evolution
for(ie=0;ie<ne;ie++)
for(je=0;je<ne;je++)
{
          nvirusvois=0;
          for(i1=ie-1;i1<=ie+1;i1++)
          for(j1=je-1;j1<=je+1;j1++)
                   {
                   if((i1>=0)&&(i1<ne)&&(j1>=0)&&(j1<ne)) //Eviter débordement*
                   {

                             //Exclure le centre et incrémenter
                             if((tviruse[i1][j1]==1)&& !((i1==ie)&&(j1==je)))
                                                                                                                                                nvirusvois++;
                   }

                   }

          if(tviruse[ie][je]==0)
          {
                   if(nvirusvois==3) tviruse[ie][je]=1;
          }
          else
          {
                   if ((nvirusvois<=2)||(nvirusvois>=5))
                             if (tviruse[ie][je]==1) tviruse[ie][je]=0;
          }

}

}

//Afffichage de la matrice de virus
void Afficher_tvirus(int na)
{int ia,ja;
getchar();
printf("Affichage tvirus");
printf("\n n=%d\n",na);
getchar();
          for (ia=0;ia<na;ia++)
          {
          for (ja=0;ja<na;ja++)
                   if(tvirus[ia][ja]==0)
                   printf(". ");
                   else    printf("* ");
                   printf("\n");
          }

}
//Chargement du tableau à partir du fichier source
int Remplir_tvirus(char *nomfichier)
{

int x,y,nr;
printf("\nPopulation des Virus\n");
fvirus=fopen(nomfichier,"r");
          if (fvirus != NULL)
                   {
                             fscanf(fvirus,"%d\n",&nr);
                             printf("\n n=%d\n",nr);
                             while(!feof(fvirus))
                             { fscanf(fvirus,"%d",&x);
                               fscanf(fvirus,"%d\n",&y);
                               tvirus[x-1][y-1]=1;
                               printf("\ntvirus(%d,%d)=%d",x,y,tvirus[x-1][y-1]);
                             }
                   }

fclose(fvirus);
return(nr);

}

Les 5 tests pour le programmes W_ORDERED (20 points par test)

Remarque : Ce programme est également connu sous le nom : je de la vie ou encore automate cellulaire, et il s'agit d'un problème très classique.