/*----------------------------------------------------------*/
/*                                                          */
/*         AUTHOR : Eric VIOLARD                            */
/*         E-MAIL : violard@icps.u-strasbg.fr               */
/*         ORGANISM : Université Louis Pasteur (Strasbourg) */
/*         CREATION : 28/12/02                              */
/*                                                          */
/* ---------------------------------------------------------*/
  
/*    
      Programme qui résoud le problème de Josephus Flavius.

*/

#include <stdlib.h>
#include <stdio.h>

#define N 40 /* nombre de soldats dans le cercle */ 
#define K 3  /* nombre tel que chaque K-ième soldat vivant dans le parcours circulaire est tué */


/* --- Définition du type des booléens --- */

typedef int bool;

#define true 1
#define false 0 


main()
{
  bool cercle[N]; /* tableau représentant le cercle de soldats : 
                     cercle[n] représente l'état du soldat placé à la place numéro (n+1) dans le cercle 
                     (les places sont numérotées de 1 à N)  */
  int i; /* pour parcourir le cercle */
  int k=1; /* compteur de 1 à K (permet de désigner la K-ième personne)  */ 
  int nb_tues=0; /* nombre de tués (initialement 0) */

  /* --- initialisation du cercle --- */

  for(i=0;i<N;i++)
    cercle[i]=true;


  /* --- déroulement de la cérémonie --- */
 
  i=0;
  while(nb_tues<N-1) /* on parcours le cercle jusqu'à ce qu'il ne reste qu'une seule personne */
    {
    if(cercle[i]) /* si le soldat est vivant */ 
      {
	if(k==K) /* si c'est le K-ième, alors aïe pour lui */
          {
	  printf("Le prochain à être tué est celui en place numéro %d\n",(i+1)); 
          cercle[i]=false; /* on le tue */
          nb_tues++; /* on met à jour le nombre de tués */ 
          k=1; /* et on remet le compteur à 1 pour le prochain soldat vivant */
          }
        else /* si ce n'est pas le K-ième, alors ouf pour lui */
          k++; /* on incrémente simplement le compteur */
      }

    i=(i+1)%N; /* on passe au suivant dans le cercle */
    }

  /* --- affichage du numéro de place de la personne qui a survécu --- */

  for(i=0;i<N;i++)
    if(cercle[i]) printf("Josephus Flavius doit choisir la place numéro %d\n",(i+1));


}