Introduction


Les points abordés dans ce TP sont :

• l'utilisation de tableaux
• les algorithmes associés aux tableaux
• les tableaux à plusieurs dimensions
• les fonctions graphiques
• les automates cellulaires

Ce qui est à faire :

• Triangle de Pascal :

  1   1
  1   2   1
  1   3   3   1
  1   4   6   4   1
  1   5  10  10   5   1
  1   6  15  20  15   6   1
  ...
  

  La n-ième ligne de ce triangle contient les n+1 coefficients C(n,p) (0<=p<=n) du binôme (a+b)^n.
  

  Ecrire un programme C qui affiche les N premières lignes du Triangle de Pascal
  où N est une constante définie dans le programme.
  Pour le calcul de la ligne courante, on s'appuiera sur la ligne précédente
  en remarquant que C(n,p) = C(n-1,p-1) + C(n-1,p).

• Cribble d'Erathostène :
  

  Erathostène (un contemporain d'Archimède) a imaginé la méthode suivante
  pour trouver tous les nombres premiers inférieurs à un entier n donné :
  

  écrire à la suite tous les nombres de 2 à n :

  2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25 ...  
  

  barrer tous les multiples du premier nombre (2) :

  2   3   X   5   X   7   X   9   X   11  X   13  X   15  X   17  X   19  X   21   X  23   X  25 ...  
  |
  

  barrer tous les multiples du nombre suivant (3) :

  2   3   X   5   X   7   X   X   X   11  X   13  X   X   X   17  X   19  X   X    X  23   X  25 ...  
      |
  

  barrer tous les multiples du nombre suivant (5) :

  2   3   X   5   X   7   X   X   X   11  X   13  X   X   X   17  X   19  X   X    X  23   X   X ...  
              |
  

  etc. jusqu'au dernier nombre.
  A la fin, les nombres qui ne sont pas barrés sont premiers.

  Ecrire un programme C qui affiche les nombres premiers inférieurs à N où N est une constante définie dans le programme.
  On utilisera la méthode d'Erathostène pour trouver ces nombres.
  

• Drapeau hollandais :
  

  Le problème du drapeau hollandais est de trier un tableau dont les éléments ne prennent que 3 valeurs
  représentant les couleurs bleu, blanc et rouge. Dans le tableau triè :
  tous les éléments au début du tableau ont pour valeur celle qui représente bleu,
  tous les éléments au milieu du tableau ont pour valeur celle qui représente blanc, et
  tous les éléments à la fin du tableau ont pour valeur celle qui représente rouge.
  Il s'agit de réaliser ce tri en permutant les valeurs des éléments et en parcourant une seule fois le tableau.

  Proposer une solution pour ce problème et la programmer en C.

• Josephus Flavius :
  

  Le problème à résoudre est inspiré d'une histoire attribuée à Josephus Flavius :

  "Josephus Flavius était un historien juif célèbre du premier siècle.
  Pendant la guerre juive-romaine il a été pris au piège dans une caverne
  avec un groupe de 40 soldats cernés par des Romains. La légende dît que,
  préférant la mort à la capture, les Juifs décidèrent de former un cercle et
  de tuer la troisième personne vivante rencontrée en suivant le parcours
  autour du cercle; ceci jusqu'à ce qu'il ne reste qu'une personne :
  cette personne devant se suicider. Josephus, pas très enthousiaste
  à l'idée de mourir, trouva rapidement la bonne place dans le cercle
  afin de rester en vie."

  Ecrire un programme C qui implante le processus décrit ci-dessus et détermine la place de Josephus.
  On définira les constantes N pour le nombre de soldats dans le cercle, et K, pour le nombre
  tel que chaque K-ième soldat vivant dans le parcours circulaire est tué.
  Dans l'histoire ci-dessus, N est 40 et K est 3. On numérotera les places dans le cercle de 1 à N

Le Jeu de la vie est l'exemple le plus connu d'automate cellulaire.
Sous une forme simple, un automate cellulaire est un espace à deux dimensions divisé en « cellules »,
donc une sorte de feuille quadrillée. Chacune des cellules peut avoir deux états : allumée ou éteinte.
Partant d'une configuration donnée, la configuration suivante est déterminée par des règles de voisinage.
Un exemple de telle règle est "si une cellule donnée est en contact avec deux cellules allumées, alors elle s'allume sinon elle s'éteint".

Le Jeu de la vie cherche à modéliser l'évolution d'organismes vivants. Les états des cellules sont interprétés de cette façon :
si une cellule est allumée, alors on dît aussi qu'elle est vivante,
si une cellule est éteinte, on dît que la cellule est morte ou vide.
De plus, est considérée comme voisine toute cellule contigüe, y compris les cellules sur les diagonales
(une cellule qui n'est pas au bord a donc exactement 8 cellules voisines).


Les règles du Jeu de la vie sont les suivantes :


1. Règle de la survie :
   
   Une cellule vivante ayant 2 ou 3 cellules voisines vivantes, reste vivante.
   
   
2. Règle de la mort :
   
   Une cellule vivante ayant plus de 3 cellules voisines vivantes, meurt (mort par étouffement ou surpopulation).
   Une cellule vivante ayant moins de 2 cellules voisines vivantes, meurt (mort par isolement).
   
   
3. Règle des naissances :
   
   Une cellule vide qui a exactement 3 cellules voisines vivantes, devient vivante ("naît").

Ecrire un programme C qui simule le Jeu de la vie à partir d'une configuration choisie au hasard.
On réprésentera l'ensemble de cellules par un tableau à 2 dimensions
et on utilisera les fonctions graphiques pour dessiner les configurations successives de l'automate.