Correction du TD n°11
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 dit que, préférant la mort à la capture, les Juifs décidèrent de former un cercle et de tuer la troisième personne 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.
Le début du processus, avec N = 11 et K = 3
On veut écrire un algorithme qui implémente le processus décrit ci-dessus et détermine la place de Josephus. Il prend en entrée les paramètres 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.
001 fonction josephusFlavius(n,k) : entier
002 Données n : entier
003 k : entier
004 Locales i : entier { Indice de boucle pour }
005 pos : entier { Indice de parcours }
006 cpt : entier { Compteur de soldats non elimines }
007 t : Tableau [n] de booléen { Tableau de gestion du parcours }
008 { et des eliminations }
009 { Initialisation du tableau t }
010 { Le soldat 0 est elimine }
011 t[0] := vrai
012 { Les autres soldats ne le sont pas }
013 pour i de 1 à n-1 faire
014 t[0] := faux
015 fait
016 { Le parcours a la recherche du prochain }
017 { soldat a eliminer commence a l'indice 0 }
018 pos := 0
019 { Il reste n-1 soldats a eliminer }
020 pour i de 1 à n-1 faire
021 { Initialisation du compteur de soldats }
022 { non elimines a parcourir }
023 cpt := 0
024 { Parcours jusqu'a avoir trouve le kieme soldat non elimine }
025 faire
026 { On avance de 1 soldat en revenant a l'indice 0 }
027 { quand on avance depuis l'indice n-1 }
028 pos := (pos+1) modulo n
029 { Si le soldat en position pos n'est pas elimine }
030 si t[pos] = faux alors
031 { Le compteur de soldats non elimines est incremente de 1 }
032 cpt := cpt+1
033 fsi
034 tant que cpt != k
035 { pos est sur le kieme soldat non elimine }
036 { -> on l'elimine }
037 t[pos] := vrai
038 fait
039 { Resultat fonction : Dernier soldat elimine }
040 Resultat : pos
041 fin fonction
Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr
