Le jeu du plus ou moins est un jeu consistant à choisir un nombre entre 1 et 100 et à le faire deviner à une tierce personne. Penchons-nous sur son implémentation en Python.
Jeu du plus ou moins: les règles
Les règles
Le maître du jeu choisit un nombre entier compris entre 1 et 100: c’est le nombre mystère. Il y a donc 100 nombres possibles.
Le joueur propose un nombre: si le nombre mystère est plus grand que la proposition, le maître du jeu répond : “plus”, sinon, il répond “moins”.
Le but du jeu est de deviner le nombre mystère en un minimum de coups.
Un exemple d’implémentation en Python
Voici une proposition de programme:
from random import randint
def jeu():
x = randint(1,100)
n = 0
coups = 0
while x != n:
n = int( input('Votre proposition: ') )
coups += 1
if x < n: print("\033[92m C'est moins.\033[0m")
elif x > n: print("\033[93m C'est plus.\033[0m")
else: print(f"\033[91m Gagné en {coups} coups.\033[0m")
Jeu du plus ou moins: une stratégie mathématique
La stratégie: la dichotomie
Il existe une manière de minimiser le nombres de propositions quand on joue à ce jeu.
En effet, si on propose au hasard, sans stratégie, n’importe quels nombres, cela risque d’être long. C’est pourquoi avoir une stratégie s’impose. Ici, nous allons raisonner par dichotomie.
Cela consiste, à chaque étape, à choisir le milieu de l’intervalle où se trouve le nombre.
Un exemple
Supposons que le maître du jeu choisisse le nombre 23.
- On commence par le milieu de l’intervalle [1;100] : 50. Le maître du jeu répond alors : “moins” car 23 < 50.
- On sait maintenant que le nombre mystère est dans l’intervalle [1 ; 50[; on choisit donc son milieu: 25. Le maître du jeu réponds “moins”.
- Le nombre doit donc être dans [1 ; 25[; on choisit le “milieu”, tout du moins la partie entière du milieu, soit 12. Le maître du jeu réponds: “plus”.
- Maintenant, on sait que le nombre à deviner est dans ]12 ; 25[; on choisit la partie entière du milieu, soit \(E\left(\frac{12+25}{2}\right)=18\) . Le maître du jeu répond alors : “plus”.
- On choisit alors la partie entière du milieu de ]18;25[, à savoir \(E\left(\frac{18+25}{2}\right)=21\). “c’est plus”.
- Le nombre mystère est donc dans ]21;25[; on propose alors 23, le milieu de cet intervalle… et on gagne!
Implémentation en Python
Nous allons demander à l’ordinateur de choisir un nombre compris entre 1 et 100; nous allons le stocker dans la variable x et nous allons créer une variable “coups” pour compter le nombre de propositions.
from random import randint x = randint(1,100) coups = 0
Nous allons maintenant demander à l’ordinateur de simuler les propositions.
n = 0
a, b = 1, 100
while n != x:
coups += 1
n = (a+b)//2
if x > n: a = n
if x < n: b = n
print( n )Cette proposition n’est pas encore optimale car si x = 100, le programme bloque sur “99”… et pour cause: \( E\left(\frac{99+100}{2}\right)=99.\)
Il faut donc distinguer le cas où n = a et celui où n est différent de a.
n = 0
a, b = 1, 100
while n != x:
coups += 1
n = (a+b)//2
if x > n:
if n != a: a = n
else: n = b
elif x < n: b = n
print( f'a={a}, b={b}, n={n}, coups = {coups}' )a=1, b=50, n=50, coups = 1
a=1, b=25, n=25, coups = 2
a=1, b=13, n=13, coups = 3
a=7, b=13, n=7, coups = 4
a=10, b=13, n=10, coups = 5
a=10, b=13, n=11, coups = 6Aller plus loin
J’ai implémenter une fonction game(a,b) qui retourne le nombre de coups nécessaires pour trouver le nombre aléatoirement choisi entre deux entiers a et b en utilisant la dichotomie. Ensuite, j’ai effectué 10000 simulations, puis ai calculé la moyenne des coups nécessaires. J’ai fait cela pour a = 1 et pour \(b = 10^n\), avec n variant de 1 à 10. Voici les résultats:
| Valeurs de n avec \(b = 10^n\) | Nombre moyens de coups nécessaires |
|---|---|
| 1 | 3.03 |
| 2 | 5.82 |
| 3 | 8.99 |
| 4 | 12.35 |
| 5 | 15.69 |
| 6 | 18.95 |
| 7 | 22.33 |
| 8 | 25.66 |
| 9 | 28.93 |
| 10 | 32.27 |
Une belle corrélation linéaire s’offre à nous.
from random import randint
from matplotlib.pyplot import axes, scatter, show, plot, legend, xlabel, ylabel, title
def jeu():
x = randint(1,100)
n = 0
coups = 0
while x != n:
n = int( input('Votre proposition: ') )
coups += 1
if x < n: print("\033[92m C'est moins.\033[0m")
elif x > n: print("\033[93m C'est plus.\033[0m")
else: print(f"\033[91m Gagné en {coups} coups.\033[0m")
def game(a,b):
x = randint(a,b)
coups = 0
n = 0
while n != x:
coups += 1
n = (a+b)//2
if x > n:
if n != a: a = n
else: n = b
elif x < n: b = n
return coups
x, y = [],[]
for e in range(1,11):
S = 0
for _ in range(10000):
S += game(1,10**e)
x.append(e)
y.append(S/10000)
print( f'e = {e} , moyenne = {S / 10000}' )
repere = axes()
repere.grid() # dessiner une grille pour une meilleur lisibilité du graphe
scatter(x,y)
show()Calculs mathématiques
Notons X la variable aléatoire représentant le nombre de coups nécessaires pour gagner avec la stratégie de la dichotomie.
Alors, X = {1;2;3;4;5;6;7;8}.
- \( P(X = 1) = \frac{1}{100}\) : c’est le cas où le nombre mystère est 50; il y a bien 1 chance sur 100 de le choisir.
- \( P(X = 2) = \frac{2}{100}\) : c’est le cas où le nombre mystère est 25 ou 75.
- \( P(X = 3) = \frac{4}{100}\) : c’est le cas si x = 12 ou 37 ou 62 ou 87.
- \( P(X = 4) = \frac{8}{100}\): c’est le cas si x = 6, 18, 31, 43, 56, 68, 81 ou 93.
- \( P(X = 5) = \frac{16}{100}: c’est le cas pour x = 3, 9, 15, 21, 28, 34, 40, 46, 53, 59, 65, 71, 78, 84, 90, 96.
- \( P(X = 6) = \frac{32}{100}\): c’est le cas pour x = 1, 4, 7, 10, 13, 16, 19, 23, 26, 29, 32, 35, 38, 41, 44, 48, 51, 54, 57, 60, 63, 66, 69, 73, 76, 79, 82, 85, 88, 91, 94, 98.
- \( P(X = 7) = \frac{36}{100} \): c’est le cas pour x = 2, 5, 8, 11, 14, 17, 20, 22, 24, 27, 30, 33, 36, 39, 42, 45, 47, 49, 52, 55, 58, 61, 64, 67, 70, 72, 74, 77, 80, 83, 86, 89, 92, 95, 97, 99.
- \(P(X = 8) = \frac{1}{100}\) pour x = 100.
On peut donc établir la loi de probabilité de X:
| \(X=k\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| \(P(X=k)\) | 0,01 | 0,02 | 0,04 | 0,08 | 0,16 | 0,32 | 0,36 | 0,01 |
L’espérance mathématique de X est donc:$$E(X)=0,01+2\times0,02+3\times0,04+\cdots+8\times0,01=5,81.$$Cette valeur correspond bien à notre simulation.
Voici ce que produit l’impressionnant Chat GPT sur demande “Peux-tu programmer le jeu du “plus ou moins” en python où il faut trouver un nombre aléatoire compris entre 1 et 100, où l’utilisateur saisi une proposition et le système dit à chaque étape si le nombre proposé est plus grand ou plus petit que le nombre à trouver jusqu’à ce que l’utilisateur trouve le bon nombre ?”
import random # Choisir un nombre aléatoire compris entre 1 et 100 number_to_guess = random.randint(1, 100) # Initialiser le nombre de tentatives à 0 tries = 0 # Boucle jusqu'à ce que le nombre soit deviné while True: # Demander à l'utilisateur de saisir un nombre guess = int(input("Devinez un nombre entre 1 et 100 : ")) tries += 1 # Vérifier si le nombre deviné est plus grand, plus petit ou égal au nombre à trouver if guess < number_to_guess: print("Le nombre à deviner est plus grand.") elif guess > number_to_guess: print("Le nombre à deviner est plus petit.") else: # Si le nombre est deviné, afficher le nombre de tentatives print("Félicitations! Vous avez deviné le nombre en", tries, "tentatives.") break