Mini projet en langage C : les signaux de fumée

By: kyle on 03:49:00

vous savez sûrement que les indiens communiquent à l'aide de petits nuages de fumée. Les nuages de fumée se voient de loin (surtout dans les grandes plaines américaines), et en utilisant plusieurs faiseurs de nuages qui reproduisent les signaux qu'ils observent, un message peut parcourir des dizaines de kilomètres en très peu de temps. Quand on y pense, c'était un moyen de communication plutôt efficace (du temps où il fallait choisir entre de la fumée ou des pigeons).
En fait, le seul vrai problème avec les signaux de fumée, c'est le mauvais temps, qui réduit considérablement la visibilité des signaux.



 
1.Cahier de charge :

Vous êtes le chef de la tribu, et vous souhaitez prévoir précisement le nombre de membres de votre tribu que vous ne pourrez pas joindre les jours de mauvais temps.
Vous disposez d'un plan de la région (une carte 2D) qui indique la position exacte de tous les faiseurs de nuages de votre tribu, dont celui qui se trouve à côté de vous dans le camp principal, et à qui vous dictez les messages à transmettre.
Lorsqu'un faiseur de nuages voit un signal de fumée, il le réémet immédiatement, afin de transmettre le message à d'autres camps.
Grâce aux pouvoirs du grand Chamane de votre tribu, vous disposez de prédictions météo pour les jours qui viennent. Chaque prédiction est donnée sous la forme d'un nombre entier : la distance maximale à laquelle un signal de fumée pourra être vu ce jour là.
Votre objectif est de déterminer, pour chaque jour pour lequel vous disposez de ces prédictions, le nombre de faiseurs de nuages qui ne recevront pas vos messages ce jour là (directement ou indirectement).

Remarque :

 le faiseur de fumée correspondant au camp principal est le premier des faiseurs de fumée que l'on vous donne sur l'entrée standard.

un faiseur de fumée se trouvant exactement à la distance maximale d'un deuxième, voit les signaux de celui-ci (et réciproquement).

LIMITES DE TEMPS ET DE MEMOIRE:

• Temps     : 1 s sur une machine à 1Ghz.
• Mémoire : 32000 Ko. 

2. Partie Analyse :                                                              

2.1.Les explications:

L'image ci-dessous représente les positions des 6 faiseurs de nuages de l'exemple, numérotés de 1 à 6,et chaque faiseur il a des coordonnées  X et Y .

2 . 1 .1 .Exemple 1:   (le ciel est dégagé)

le ciel est dégagé, et la distance à laquel un signal peut être vu est de 17km. Le message émis par le faiseur de fumée 1 peut être vu directement par les numéros 2 et 3. Le numéro 4 peut voir le message retransmis par le numéro 2. Le numéro 5 voit alors le message retransmis par le 4. Le 3 et le 5 retransmettent aussi leur message, mais ce n'est pas suffisant pour qu'il soit vu par le faiseur de fumée 6. C'est le seul faiseur de nuages qui ne reçoit pas le message.

2 . 1 .2. Exemple 2:  (le ciel est assez nuageux)

 

le ciel est assez nuageux, et les signaux ne peuvent être vus que jusqu'à une distance de 10km. le numéro 2 et 3 reçoivent le message. Ils le réémet, mais personne d'autre que le 1 ne peut voir ses signaux. Il reste donc 3 faiseurs de nuages qui ne reçoivent rien.

2.2.Analyse du probleme :

2.2.1 .Les objets d'entrées :

N           : le nombre de faiseur de fumée  (2 <= N <= 1 000)                         

X et Y   : se  sont les coordonnées entières ( -65 000 <= X,Y <= 65 000)

M    : est le nombre de jours pour lesquels nous disposons de     prédictions  météorologiques. (0<= M <=10000)                    

D_i          : la distance de visibilité pour chaque jour i  ( 0 <= D <= 200000)

 

2.2.2. Les objets de sorties :

Nous devons  afficher le nombre de faiseurs de nuages injoignables  s pour chaque jour i dans l'ordre de l'entrée.

2.2.3. Les objets intermédiares :

T: tableau de taille N pour memorise les faiseur qui ont vus les signaux de fumées.

2.2.4. Les formules :

L'equation d'une cercle de centre (x_i , y_i) et de rayon r :

(x_i – x₀)² + (y_i – y₀)² ≤ r ²

2.3. Commentaire : 

Pour chaque jour i :

On va initialiser un tableau de taille N a 0 sauf  le premier element qu'on va initialiser a 1, car toujours le premier faiseur c'est celui qui va transmettre le premier signal, ce tableau sert a memorise les faiseur qui ont vu les fumées, on affecte la valeur 1 au faiseur qui a recu le message et la valeur 0 au faiseur qui n'a pas vu les fumées.

Apres  on  declanche une boucle repeter – jusqu'à allant de i=0 jusqu'à n et pour chaque element i en va tester est ce que l'element t[i]=1  c-a –dire est ce qu il a déjà recu le message si oui  on  va declencher une autre boucle  repeter-tantque qui va chercher les faiseur qui n'ont pas recu le message et on  teste est ce que leurs coordonnées (X[j],Y[j]) appartiennent au cercle de centre (X[i],Y[i]) et de rayon D[r] on utilise l'equation du cercle qui definie comme suit :

Un point (X[j],Y[j]) appartienne au cercle de centre (X[i],Y[i]) et de rayon D[r] seulement si :

(X[J]- X[i])² + (Y[j] -Y[i])² <=D[r],

si les coordonnées verifie cette equation on va affecter a t[j] la valeur 1   c-a-dire il a recu le message parce qu'il est se trouve au long d'une distance qui le permet de voir les fumées ; et en méme temps en mémorise la position de j la plus petite qu'on a trouver dans une autre variable qui s'appelle  trouve , apres la fin de la boucle repeter –tantque si trouve <i on va revenir a cette position car peut etre que ce faiseur pouvra transmettre leur message a des autres faiseurs qu'on a deppassé dans la boucle repeter-jusqu'à  si tous ces cas ne sont pas verifiés  on va incrimenter le i .

2.4. L'algorithme:

algorithme faiseur_fumee;

var

 

  X,Y,t: tableaux [1 .. 1000] d'entiers long;

  i,j,h,N,r,s,trouve : entiers;

  M    : long entier;

  D    : tableau [1..10000] d'entier long;

  auxi : double;

debut

   repeter

    lire(N);

   jusqu'a(N>=2 et N<=1000);

   pour i<-- 0 a N-1 faire

    repeter

    ecrire('entrez x',i,':');

    lire(X[i]);

    ecrire('entrez y',i,':');

    lire(Y[i]);

    jusqu'a(X[i]>-65000 et X[i]<65000 et Y[i]>-65000 Y[i]< 65000);

   fin pour i

  répéter  

  {

    Ecrire('entrez le nombre de jour pour laquelle vous

       voulez mettre des prédictions météorologiques :');

              

    lire(M);

  }

  jusqu'a(M>=0 et M=<10000);

 

  pour i<-- 0 a M faire

   répéter

    Lire (D[i]);

   jusqu'a (D[i]>=0 et D[i]<= 200000);

  Fin pour i

  Pour r<-- 0 a M-1 faire

   h <--  0;

   auxi<--  (D[r])^2;

    pour i=0 a N faire

     t[i]<-- 0;

    fin pour i

   t[0]<--  1;

   s <--  0;

  

   répéter

    trouve <-- s;                                     

    Si (t[s]=1)             

     Pour j<-- 1 a N

      Si (t[j]=0)                                           

       si (((X[j]-X[s])^2+(Y[j]-Y[s])^2)<=auxi)

         t[j] <--  1;

          Si (trouve>j)

            trouve <--  j;

          Finsi

   

       finsi

      finsi   

     fin pour j

    finsi

 

    Si (s=trouve)

     s <--  s+1;

    Sinon

      s <--  trouve;

    finsi

 

  jusqu'a (s>=N)

 

  pour i<-- 0 a N faire

    si(t[i]=0)

    h <--  h+1;

  fin pour i

 

  ecrire('le nombre de faiseur qui n'ont pas recus le'

           'message est :',h);

 jusqu'a (r>N)

  

Fin

 

3. Partie pratique :

3.1.Declarations des bibliothéques: 

     On va utiliser quatre  bibliothéque :

  <stdio.h>: pour les entrées et les sorties (scanf,printf….).

  <conio.h> : pour la fonction clrscr() qui permet d'effacer  l'ecran.        

 <string.h>: la fonction memset qui remplit  un nombre d' octet avec une   

                      valeur  donner.  

    <math.h>: pour la fonction mathematique  pow qui calcule la  

                       puissance.

 3.2.Declaration des variables:

Les variables	type	L'equivalent en c
X[],Y[],D[],M	Long entier	Long int (%ld)
i,j,h,N,r,s, t[],trouve	entier	int (%d)
auxi	double	Double (%lf)

3.3.Lecture des données:

En fait,il y'a deux façon pour lire les données en langage c soit avec l'entrée standard c-a-dire le clavier ou avec des fichiers.

3.3.1.Lecture a partir du clavier:

   

do

  {

    printf("entrez le nombre de faiseur (2<= n <= 1000) :");

    scanf("%d",&N);

  }

 while(N<2 || N>1000);

   for(i=0;i<N;i++)

  {

    do

    {

    printf("x%d=",i+1);

    scanf("%ld",&X[i]);

    printf("y%d=",i+1);

    scanf("%ld",&Y[i]);

    }

    while(X[i]<-65000 || X[i]>65000 || Y[i]<-65000 || Y[i]>65000);

 do

  {

    printf("entrez le nombre de jour pour lesquels vous disposez"

          " de predictions \nmeteorologiques (0<= m <=10000) :");    

    scanf("%ld",&M);

  }

 while(M<0 || M>10000);

 for(i=0;i<M;i++)

    {

    do

     {

     printf("entrez la distance de visibilite pour jour %d"

             :",i+1); 

     scanf("%ld",&D[i]);

     }

    while(D[i]<0 || D[i]>200000);}

    

3.3.2.Lecture a partir d'un fichier:

On suppose que le fichier est déjà créer et toutes les variable sont declaré au debut du programme, donc la lecture des  données a partir de ce fichier  va être comme suit :

   do

    {

     printf("Nom du fichier : ");

     scanf("%s",nom_fichier);

     f1 = fopen(nom_fichier, "r");

     if (!f1)

         printf("\aERREUR: Impossible d'ouvrir "

                "le fichier: %s.\n",nom_fichier);

    }

   while (!f1);

   fscanf(f1,"%d",&N);

   i=0;

   while (i<N)

    {

     fscanf(f1,"%d %d\n",&X[i],&Y[i]);

     i=i+1;

    }

   fscanf(f1,"%d",&M)

   while (!feof(f1))

    {

     fscanf(f1,"%d",&D[i]);

     i=i+1;

    }

   fclose(f1);

3.4.Le programme:

#include <stdio.h>

#include <conio.h>

#include<math.h>

#include<string.h>

int main()

{ long int X[1000],Y[1000],D[10000];

   int i,j,h,N,r,trouve=0,M,t[1000],;

    double auxi;

 

 do

  {

    printf("entrez le nombre de faiseur (2<= n <= 1000) :");

    scanf("%d",&N);

  }

 while(N<2 || N>1000);

   for(i=0;i<N;i++)

  {

    do

    {

    printf("x%d=",i+1);scanf("%ld",&X[i]);

    printf("y%d=",i+1);scanf("%ld",&Y[i]);

    }

    while(X[i]<-65000 || X[i]>65000 || Y[i]<-65000 || Y[i]>65000);

 do

  {

    printf("entrez le nombre de jour pour lesquels vous disposez"

          " de predictions \nmeteorologiques (0<= m <=10000) :");    

    scanf("%ld",&M);

  }

 while(M<0 || M>10000);

 for(i=0;i<M;i++)

    {   

    do

     {

     printf("entrez la distance de visibilite pour jour %d"

             :",i+1); 

     scanf("%ld",&D[i]);

     }

    while(D[i]<0 || D[i]>200000);}

 for(r=0;r<M;r++)

 {h=0;

 auxi=pow(D[r],2);

memset(t,0,N*sizeof(int));

   t[0]=1;

 s=0;

 do

 {

 trouve=s;                                                  

  if(t[s]==1)

  {              

  for(j=1;j<N;j++)

  {

    if(t[j]==0)

    {                                           

    if((pow((X[j]-X[s]),2)+pow((Y[j]-Y[s]),2))<=auxi)

    {

  t[j]=1;

  if(trouve>j)

    trouve=j;

    }

   

   }

  }

 }

 if(s==trouve)

 s++;

 else

 s=trouve;

}

 while(s<N);

  for(i=0;i<N;i++)

  {

    if(t[i]==0)

    h++;

  }

  printf("\n%d",h);

  printf("\n");

  }

  

  return 0;

  }

3.5.Exemple d'execution: