L’anniversaire : je gagne toujours !
9 invités et la personne qui fête son anniversaire : 10 personnes. Elle a 12 ans, donc K = 12. Reconstruisons la place qui la laissera seule à la fin.
Algorithmes
Laboratoire des algorithmes à rebours
Choisissez le résultat et reconstruisez le départ : un paquet de cartes ou un cercle de Josephus. Observez, arrêtez et annulez chaque mouvement.
Lire l’explication et les deux problèmesLe paquet de cartes
En avant : prendre sous le paquet, poser dessus ; prendre dessous, poser sur la table. À rebours : reprendre sur la table, placer dessous ; prendre dessus, placer dessous.
Le duo : deux gagnants choisis
20 amis, 2 gagnants et K = 11. Trouvons les deux places à donner au duo avant de commencer.
Le cercle de Josephus
Réunissons les gagnants. Le prochain perdant entre comme nombre provisoire suivi de ?, recule à chaque compte et est confirmé à son point d’arrivée. Le tour suivant repart du dernier perdant inséré. Ce n’est qu’à la fin qu’on trouve la place 1 et numérote les places.
La préférence de mouvement réduit est activée. Pour voir le déplacement, cochez cette case.
Paquet en main
DessusCarte en mouvement
Pile sur la table
DessusSorties souhaitées, de la première à la dernière
Sorties observées, de la première à la dernière
Paquet préparé, du dessus au dessous
Comparer simulation et permutation
Les positions sont étiquetées depuis le dessous : simulons le jeu, puis attribuons à chaque position la valeur souhaitée lors de sa sortie.
| Position sortie (depuis le dessous) | Valeur à attribuer |
|---|
Gagnants en cercle, perdants à insérer
Nombre avec ? → déplacement à chaque compte → confirmation au même endroit → départ du dernier perdant inséré. Les nombres sans ? restent fixes.
Cercle en construction · personnes confirmées
▼ Repère initial : la personne 1 reste en haut
Seul le nombre provisoire avec ? se déplace. Le cercle ne tourne qu’à la fin.
S’il y a beaucoup de nombres, faites défiler l’intérieur du cercle pour tous les voir.
Groupe des perdants · encore à insérer
Comment lire le comptage
Le nombre suivi de ? entre provisoirement et recule d’un intervalle à chaque compte ; les autres nombres restent fixes. Au compte K, le ? disparaît et le perdant est confirmé exactement là. Le départ suivant est le dernier perdant inséré. Pour conserver toutes les identités du tableau PHP, le premier emplacement provisoire est préparé : avec 15 gagnants et K = 9, il part avant le 9 et arrive avant le 1. Après la dernière insertion, un comptage séparé depuis le dernier perdant trouve la place 1 ; ce n’est qu’alors que tout le cercle est tourné et numéroté. L’ordre final correspond à la boucle PHP.
Rangée finale des places
Les nombres désignent maintenant les places : vert = gagnante, bleu = perdante. La place 1 est le point de départ du comptage pour éliminer ; ce n’est pas le numéro identifiant la personne 1.
Vert : gagnantBleu : perdant
Afficher aussi le cercle
Reconstruction du cercle
Les places sont numérotées dans le sens horaire. Le comptage d’élimination part de la place 1 et suit le sens choisi ; après chaque élimination, il recommence avec la personne suivante.
Compter 1 ici
File dans le sens du comptage, depuis le prochain 1
Places à donner aux gagnants
Places éliminées dans l’ordre