L'ordinateur devine ton nombre
Dans le jeu du « plus ou moins », c'est toi qui devines le nombre de l'ordinateur. Inversons les rôles : tu penses à un nombre entre 1 et 100, et l'ordinateur le trouve. Il lui faut au maximum... 7 questions. Voyons comment.
La stratégie : couper en deux
Si l'ordinateur proposait 1, puis 2, puis 3..., il lui faudrait jusqu'à 100 questions. La bonne idée : proposer toujours le milieu de ce qui reste possible.
- Le nombre est entre 1 et 100 : il propose 50.
- Tu réponds « c'est plus » : le nombre est entre 51 et 100. Il propose 75.
- Tu réponds « c'est moins » : le nombre est entre 51 et 74. Il propose 62.
Chaque réponse élimine la moitié des possibilités. C'est la recherche dichotomique.
Le programme
L'ordinateur retient deux bornes : mini et maxi. Le nombre secret est toujours entre les deux.
affiche 'Pense à un nombre entre 1 et 100. Je vais le deviner !'
mini est un nombre vaut 1
maxi est un nombre vaut 100
proposition est un nombre
reponse est un nombre
questions est un nombre vaut 0
gagne est un booléen vaut faux
tant que non gagne
proposition vaut arrondi_inferieur((mini + maxi) / 2)
questions ajoute 1
affiche 'Question ' + questions + ' : est-ce ' + proposition + ' ?'
choisir ['C’est plus', 'C’est moins', 'Gagné !'] dans reponse
si reponse = 1 alors
mini vaut proposition + 1
sinon si reponse = 2 alors
maxi vaut proposition - 1
sinon
gagne vaut vrai
fin si
fin tant que
affiche 'Trouvé en ' + questions + ' questions !'
(mini + maxi) / 2 est le milieu ; arrondi_inferieur en fait un nombre entier.- « C'est plus » : le nombre est au-dessus de la proposition, donc
mini monte à proposition + 1. - « C'est moins » : c'est
maxi qui descend à proposition - 1.
Essaie avec 37 : l'ordinateur propose 50, puis 25, puis 37. Trois questions !
Question : L'ordinateur propose 50 et tu réponds « C'est plus ». Quelle est sa proposition suivante ? — 75. Le nombre est maintenant entre 51 et 100. Le milieu : (51 + 100) / 2 = 75,5, arrondi à 75.
Et si le joueur triche ?
Si tu changes de nombre en cours de route, ou si tu te trompes dans une réponse, les bornes finissent par se croiser : mini dépasse maxi. L'ordinateur peut le détecter :
affiche 'Pense à un nombre entre 1 et 100.'
mini est un nombre vaut 1
maxi est un nombre vaut 100
proposition est un nombre
reponse est un nombre
questions est un nombre vaut 0
etat est un texte vaut 'cherche'
tant que etat = 'cherche'
si mini > maxi alors
etat vaut 'triche'
sinon
proposition vaut arrondi_inferieur((mini + maxi) / 2)
questions ajoute 1
affiche 'Question ' + questions + ' : est-ce ' + proposition + ' ?'
choisir ['C’est plus', 'C’est moins', 'Gagné !'] dans reponse
si reponse = 1 alors
mini vaut proposition + 1
sinon si reponse = 2 alors
maxi vaut proposition - 1
sinon
etat vaut 'gagne'
fin si
fin si
fin tant que
si etat = 'gagne' alors
affiche 'Trouvé en ' + questions + ' questions !'
sinon
affiche 'Hé ! Aucun nombre ne correspond à tes réponses...'
fin si
La variable etat peut prendre trois valeurs : 'cherche', 'gagne' ou 'triche'. C'est plus clair que plusieurs booléens.
Pourquoi 7 questions suffisent
À chaque question, le nombre de possibilités est divisé par deux :
100 → 50 → 25 → 12 → 6 → 3 → 1
Après six questions, il ne reste plus qu'une possibilité : la septième est forcément la bonne. Cette fonction compte les questions nécessaires dans le pire des cas :
fonction questionsMax(possibilites)
compteur est un nombre vaut 0
restant est un nombre vaut possibilites
tant que restant >= 1
restant vaut arrondi_inferieur(restant / 2)
compteur ajoute 1
fin tant que
retourne compteur
fin fonction
affiche 'Entre 1 et 100 : ' + questionsMax(100) + ' questions' // 7
affiche 'Entre 1 et 1000 : ' + questionsMax(1000) + ' questions' // 10
affiche 'Entre 1 et 1 million : ' + questionsMax(1000000) + ' questions' // 20
Vingt questions pour trouver un nombre parmi un million ! Et il n'en faut que 30 pour un milliard. C'est toute la puissance de la dichotomie : multiplier les possibilités par deux ne coûte qu'une question de plus.
L'ordinateur joue contre lui-même
Pour vérifier, faisons jouer l'ordinateur 100 parties, une pour chaque nombre secret :
fonction questionsPour(secret)
mini est un nombre vaut 1
maxi est un nombre vaut 100
proposition est un nombre
compteur est un nombre vaut 0
tant que mini <= maxi
proposition vaut arrondi_inferieur((mini + maxi) / 2)
compteur ajoute 1
si proposition = secret alors
retourne compteur
sinon si proposition < secret alors
mini vaut proposition + 1
sinon
maxi vaut proposition - 1
fin si
fin tant que
retourne compteur
fin fonction
total est un nombre vaut 0
pire est un nombre vaut 0
pour n de 1 à 100
total ajoute questionsPour(n)
pire vaut maximum(pire, questionsPour(n))
fin pour
affiche 'Pire cas : ' + pire + ' questions' // 7
affiche 'En moyenne : ' + (total / 100) + ' questions' // 5,8
Jamais plus de 7 questions, et 5,8 en moyenne.
En résumé
- Proposer le milieu élimine la moitié des possibilités à chaque question.
- Deux bornes,
mini et maxi, encadrent ce qui reste possible. - Si les bornes se croisent, les réponses étaient incohérentes.
- 7 questions pour 100 nombres, 10 pour 1000, 20 pour un million.
