Bonjour, supposons que j'ai un programme qui tire un nombre au hasard qu'on doit deviner, et qui nous dit "plus" si le nombre donné est inférieur et "moins" si il est supérieur. La meilleur méthode pour trouver le nombre semble être de diviser à chaque fois l'intervalle par 2 (par exemple si je donne 50 et que l'ordi nous dit "plus", je test avec 75). cet algo semble être assez rapide, mais je me demandais si il existait un algorithme qui convergeait plus vite (ce qui m'étonnerait) ?
Tu veux donc dire que le programme tire un nombre au hasard entre 0 et 100, non ? Sinon, tenter d'abord 50 puis 75 me semble un pari risqué...Envoyé par Linkounet
Oui pour l'exemple j'ai pris 100, ça peut aussi être n'importe quel borne minimale ou maximale.
ça s'appelle la recherche dichotomique, et c'est la méthode la plus efficace. C'est assez facile à démontrer (mais j'ai la flemme) en comparant avec une méthode qui "partagerait" les solutions restantes en deux parties inégales.
On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !
