Le jeu de la ronde⚓︎

Règle du jeu⚓︎

Soit \(n\) un entier strictement positif.

\(n\) enfants jouent dans une cour de récréation : ils se placent en rond et choisissent au hasard l’un d’entre eux.

A partir de là, la règle est simple :

Le premier enfant tape sur l’épaule de son voisin de gauche : celui-ci est éliminé. Au début l’enfant 1 élimine donc l’enfant 2
On passe à l’enfant restant suivant et l’on recommence : il élimine celui situé à sa gauche. Dans l’exemple, l’enfant 3 élimine le 4
On continue encore et encore jusqu’à ce qu’il ne reste plus qu’un seul enfant : c’est le gagnant !

Le jeu de la ronde

Dans le cas où \(n=13\) (comme sur la figure), le gagnant est l’enfant \(11\).

Le but du jeu est simple : où se placer pour gagner ?

Méthode⚓︎

Dans cet exercice nous allons utiliser un tableau de booléen nommé joueurs dans lequel chaque valeur indique que le joueur concerné est encore en jeu (True) ou a déjà été éliminé (False).

Attention

Les indices des liste Python étant comptabilisés à partir de 0, avoir joueurs[2] égal à False signifie que le joueur n°3 a été éliminé.

Ce tableau sera initialisé avec autant de valeurs True qu'il y a de joueurs.

La partie se déroulera ainsi :

On garde trace de l'indice du joueur qui doit jouer
On cherche dans le tableau l'indice du prochain joueur encore en jeu
On "élimine" ce joueur
On cherche l'indice du prochain joueur encore en jeu : ce sera à lui de jouer

Ces différentes étapes continuent jusqu'à ce qu'il ne reste plus qu'un seul joueur encore en jeu.

Au travail !⚓︎

Vous devez écrire deux fonctions :

indice_prochain_True prend en argument une liste de booléens ainsi qu'un indice et renvoie l'indice de la prochaine valeur de la liste égale à True. On prendra soin de "boucler" les indices : si celui-ci dépasse la longueur de la liste, on le ramène à 0.

On garantit que la liste booleens contient au moins une valeur True.

Exemples

🐍 Console Python

>>> booleens = [True, True, False, True, False]
>>> indice_prochain_True(booleens, 0)
1
>>> indice_prochain_True(booleens, 1)
3
>>> indice_prochain_True(booleens, 3)
0

gagnant prend en argument le nombre de joueurs au début de la partie et renvoie la position du joueur gagnant

Exemples

🐍 Console Python

>>> gagnant(1)
1
>>> gagnant(5)
3
>>> gagnant(13)
11

∞/∞

def indicepy-undprochainpy-undTrue(booleens, indice):bksl-nl taille = len(booleens)bksl-nlbksl-nl while True:bksl-nl indice += ...bksl-nl if indice == taille:bksl-nl ...bksl-nl if booleens[...]:bksl-nl return ...bksl-nlbksl-nlbksl-nldef gagnant(nbpy-undjoueurs):bksl-nl joueurs = [True for py-und in range(nbpy-undjoueurs)]bksl-nl indicepy-undjoueur = ...bksl-nl while ...:bksl-nl prochain = ...bksl-nl joueurs[prochain] = Falsebksl-nl indicepy-undjoueur = ...bksl-nl nbpy-undjoueurs = ...bksl-nlbksl-nl return ...bksl-nlbksl-nlbksl-nl# Testsbksl-nl# Tests de la fonction indicepy-undprochainpy-undTruebksl-nlbooleens = [True, True, False, True, False]bksl-nlassert indicepy-undprochainpy-undTrue(booleens, 0) == 1bksl-nlassert indicepy-undprochainpy-undTrue(booleens, 1) == 3bksl-nlassert indicepy-undprochainpy-undTrue(booleens, 3) == 0bksl-nlbksl-nl# Tests de la fonction gagnantbksl-nlassert gagnant(1) == 1bksl-nlassert gagnant(5) == 3bksl-nlassert gagnant(13) == 11bksl-nlbksl-nldef indicepy-undprochainpy-undTrue(booleens, indice):bksl-nl taille = len(booleens)bksl-nl while True:bksl-nl indice += 1bksl-nl if indice == taille:bksl-nl indice = 0bksl-nl if booleens[indice]:bksl-nl return indicebksl-nlbksl-nlbksl-nldef gagnant(nbpy-undjoueurs):bksl-nl joueurs = [True for py-und in range(nbpy-undjoueurs)]bksl-nl indicepy-undjoueur = 0bksl-nl while nbpy-undjoueurs > 1:bksl-nl prochain = indicepy-undprochainpy-undTrue(joueurs, indicepy-undjoueur)bksl-nl joueurs[prochain] = Falsebksl-nl indicepy-undjoueur = indicepy-undprochainpy-undTrue(joueurs, prochain)bksl-nl nbpy-undjoueurs -= 1bksl-nlbksl-nl return indicepy-undjoueur+1bksl-nlbksl-nlbksl-nl# Testsbksl-nl# Tests de la fonction indicepy-undprochainpy-undTruebksl-nlbooleens = [True, True, False, True, False]bksl-nlassert indicepy-undprochainpy-undTrue(booleens, 0) == 1bksl-nlassert indicepy-undprochainpy-undTrue(booleens, 1) == 3bksl-nlassert indicepy-undprochainpy-undTrue(booleens, 3) == 0bksl-nlbksl-nl# Tests de la fonction gagnantbksl-nlassert gagnant(1) == 1bksl-nlassert gagnant(5) == 3bksl-nlassert gagnant(13) == 11bksl-nlbksl-nl

Commentaires⚓︎

Comme on est sûr que la liste booleens contient au moins une valeur True, on peut construire la fonction autour de while True: tout en ayant la certitude de sortir de la boucle.

Dans la boucle :

on incrément indice et l'on vérifie qu'il ne dépasse pas la taille de la liste (si oui, on lui donne la valeur 0)
on teste si booleens[indice] est égal à True. Si c'est le cas on renvoie la valeur de indice

Dans la fonction gagnant, on commence par créer la liste de booléens, tous égaux à True (tous les joueurs sont encore en jeu).

On désigne le joueur dont c'est le tour avec indice_joueur (à 0 au début pour le joueur 1).

On lance ensuite la partie qui continue jusqu'à ce que le nombre de joueurs soit égal à 1.

A chaque étape :

on cherche l'indice du prochain joueur encore en jeu
on l'élimine
on passe au joueur suivant en effectuant une nouvelle recherche

A la fin de la fonction, on renvoie indice_joueur+1 afin de tenir compte du décalage entre les indices dans la liste et les numéros des joueurs.