Découpages⚓︎
Le « Plus grand, plus petit » est un classique des jeux d'enfants :
- le premier joueur pense à un nombre entier compris dans un certain intervalle,
- le second essaie de le deviner,
- à chaque proposition, le premier joueur répond par « Mon nombre est plus grand », « Mon nombre est plus petit » ou « Tu as trouvé ! ».
Mettons-nous à la place du second joueur : quelle méthode adopter ?
Il est possible de tester tous les nombres de l'intervalle dans l'ordre croissant mais cela risque d'être long si le nombre secret est à la fin... Cette méthode est de coût linéaire.
Une autre approche est de débuter au milieu de l'intervalle et de modifier la zone de recherche en fonction de la réponse du premier joueur :
- s'il répond « Mon nombre est plus petit », on cherche désormais dans la partie gauche de la zone,
- s'il répond « Mon nombre est plus grand », on cherche désormais dans la partie droite de la zone.
Exprimée en Python, cette méthode devient :
reponse = ""
while reponse != "Tu as trouvé !" :
milieu = (fin + debut) // 2
reponse = input(f"Je propose {milieu}. Qu'en pensez-vous ?")
if reponse == "Mon nombre est plus petit" :
fin = milieu - 1
elif reponse == "Mon nombre est plus grand" :
debut = milieu + 1
Appliquons cet algorithme. On joue sur l'intervalle \([0,\,100]\) et le nombre cherché est \(43\).
debut |
fin |
milieu |
reponse |
|---|---|---|---|
0 |
100 |
50 |
"Mon nombre est plus petit" |
0 |
49 |
24 |
"Mon nombre est plus grand" |
25 |
49 |
37 |
"Mon nombre est plus grand" |
38 |
49 |
43 |
"Tu as trouvé !" |
Il a fallu 4 propositions.
Combien d'étapes ?
On joue à nouveau dans l'intervalle \([0,\,100]\).
- Si le nombre à trouver est \(62\), il faut 3 étapes
- Si l'on cherche \(12\), après 3 propositions, la zone de recherche est \([11,\,23]\)
- \(1\) est plus long à trouver que \(0\)
- Cette méthode donne la bonne réponse en moins de 7 propositions
Les zones de recherche sont \([0,\,100]\) (on propose \(50\)), \([51,\,100]\) (on propose \(75\)), \([51,\,74]\) (on propose \(62\))
Les zones de recherche sont \([0,\,100]\) (on propose \(50\)), \([0,\,49]\) (on propose \(24\)), \([0,\,23]\) (on propose \(11\)) et on cherche ensuite dans \([12,\,23]\)- En effet. Pour trouver \(1\), il faut passer par les étapes \([0,\,100]\), \([0,\,49]\), \([0,\,24]\), \([0,\,11]\), \([0,\,4]\), \([0,\,1]\), \([1,\,1]\). Il aurait fallu une étape de moins pour trouver \(0\)
- Dans le cas présent, \(1\) est un des nombres les plus longs à déterminer. La réponse précédente montre qu'il faut 7 propositions
Combien d'étapes pour trouver \(0\) ?
Dans toutes les propositions, on cherche \(0\). Par contre, l'intervalle change.
- Si l'intervalle est \([0,\,9]\), il faut 3 propositions
- Si l'intervalle est \([0,\,19]\), il faut 4 propositions
- Si l'intervalle est \([0,\,39]\), il faut 5 propositions
- Si l'intervalle est \([0,\,79]\), il faut 6 propositions
- Les zones de recherche sont \([0,\,9]\) (on propose \(4\)), \([0,\,3]\) (on propose \(1\)) et on cherche ensuite dans \([0,\,0]\)
- Les zones de recherche sont \([0,\,19]\) (on propose \(9\)), \([0,\,8]\) (on propose \(4\)), \([0,\,3]\) (on propose \(1\)) et on cherche ensuite dans \([0,\,0]\)
- Les zones de recherche sont \([0,\,39]\) (on propose \(19\)), \([0,\,18]\) (on propose \(9\)), \([0,\,8]\) (on propose \(4\)), \([0,\,3]\) (on propose \(1\)) et on cherche ensuite dans \([0,\,0]\)
- Les zones de recherche sont \([0,\,79]\) (on propose \(39\)), \([0,\,38]\) (on propose \(19\)), \([0,\,18]\) (on propose \(9\)), \([0,\,8]\) (on propose \(4\)), \([0,\,3]\) (on propose \(1\)) et on cherche ensuite dans \([0,\,0]\)
Combien d'étapes sont nécessaires ? La question précédente nous donne une piste.
Dans chaque cas, l'intervalle de départ contient deux fois plus de valeurs (10 pour \([0,\,9]\), 20 pour \([0,19]\), etc.). On se rend compte que le nombre d'étapes augmente de 1 à chaque fois.
Le coût de cet algorithme est donc lié à la largeur de l'intervalle (on s'en doutait) mais plus précisément au nombre de fois où l'on peut la diviser par deux avant que l'intervalle ne soit réduit à une seule valeur.
On dit dans ce cas que l'algorithme est de coût logarthmique.
Cette relation est illustrée sur le graphique ci-dessous liant la largeur de l'intervalle au nombre de propositions faites avant de proposer \(0\). On observe bien qu'il faut une proposition de plus à chaque fois que le nombre de valeurs dans l'intervalle double.
Remarque
L'algorithme étudié dans cette page est appelé « Recherche dichotomique ». Il fonctionne sur des tableaux triés dans l'ordre croissant et est très efficace.
« dichotomie » signifie « partager en deux parts égales »
En appliquant cette méthode, trouver un nombre compris entre \(0\) et \(1\,000\,000\) demande moins de \(20\) étapes !
De manière générale, le nombre d'étapes maximal est environ le nombre de bits dans l'écriture binaire de la largeur de l'intervalle de recherche.
C'est une définition approximative du logarithme en base \(2\), d'où le terme coût logarithmique.