Trouver un nombre entre 0 et 10 par dichotomie

 Bonjour,

Plutot qu'une photo il faut nous donner le source, avec l'icone idoine + le langage, et aussi les messages d'anomalie éventuels. Ce qui donne :

reponse=""
while reponse not in ("oui","non"):
    reponse=input("question oui/non : ").lower()
print(reponse)

Bonjour,

Pour calculer la valeur moyenne de a et de b, il faut calculer |a - b| / 2, notamment car tu n'as pas parenthésé ton calcul. Or ce n'est pas ce que tu calcules dans la variable milieu.

Attention à bien tester les cas aux bornes (si le nombre choisi est 0 ou 10 dans ton cas).

Cette page devrait t'aider dans tes recherches.

Bonne chance

Je fais personnellement le calcul:
milieu = (debut + fin) // 2
Et on a les variantes pour lesquelles fin = len(tableau) et fin = len(tableau) - 1
Et pour tester si on a fini ne sera pas le même et l'ajustement de fin ne le sera pas non plus.

Ça se fait avec un while et un if suivi d'un if ... else

Bonjour,

Afin de t'aider voici un squelette de code. J'ai volontairement laisser à deux endroits "..." qu'il faut remplacer par ce qu'il faut, mais si tu as compris le principe d'une dichotomie, tu arriver facilement à mettre ce qu'il faut à la place.

class IsLowerOrEqual:
    def __init__(self, expected: int):
        self.expected = expected 
        self.num_tries = 0
    def __call__(self, i: int): 
        self.num_tries += 1
        ret = self.expected <= i
        print(f"try {self.num_tries}: trying {i} --> {ret}")
        return ret

def dichotomie(is_lower_or_equal: callable, lb: int = 0, ub: int = 10):
    if lb > ub: raise ValueError()
    if not isinstance(lb, int): raise TypeError()
    if not isinstance(ub, int): raise TypeError()
    while ub != lb:
        mid = (lb + ub) // 2
        #print(f"lb = {lb} mid = {mid} ub = {ub}")
        if is_lower_or_equal(mid):
            ub = ... # A COMPLETER
        else:    
            lb = ... # A COMPLETER
    return lb

lb = 0
ub = 10
for expected in range(lb, ub + 1): 
    print("-" * 20, f"expected = {expected}", "-" * 20)
    oracle = IsLowerOrEqual(expected)
    obtained = dichotomie(oracle, lb, ub)
    assert obtained == expected, (obtained, expected)
    assert oracle.num_tries <= 4, oracle.num_tries
    print(f"The answer is {obtained}, found in {oracle.num_tries} tries")

Ce programme challenge chacune des valeurs attendues (expected) dans {0, 1, ..., 10}, lance la dichotomie qui retourne la valeur obtained. Il maintient pour cela deux bornes (lb = lower bound = borne inférieure ; ub == up bound = borne supérieure) qui vérifient la propriété lb <= obtained <= ub. Une fois la dichotomie terminée, on vérifie que obtained et expected coïncident. Enfin on vérifie que le nombre d'essais effectués est inférieur ou égal à 4. Si l'une de ces deux vérifications échoue, la trace te permet de comprendre ce qui s'est passé.

La seule chose qui n'est pas faite, c'est la mise à jour de ub et lb. J'ai laissé des pointillés aux deux endroits concerné, mais c'est vraiment quelque chose de très simple dans les deux cas. Si tu parviens à trouver comment les remplir tu obtiendras cette trace :

-------------------- expected = 0 --------------------
try 1: trying 5 --> True
try 2: trying 2 --> True
try 3: trying 1 --> True
try 4: trying 0 --> True
The answer is 0, found in 4 tries
-------------------- expected = 1 --------------------
try 1: trying 5 --> True
try 2: trying 2 --> True
try 3: trying 1 --> True
try 4: trying 0 --> False
The answer is 1, found in 4 tries
-------------------- expected = 2 --------------------
try 1: trying 5 --> True
try 2: trying 2 --> True
try 3: trying 1 --> False
The answer is 2, found in 3 tries
-------------------- expected = 3 --------------------
try 1: trying 5 --> True
try 2: trying 2 --> False
try 3: trying 4 --> True
try 4: trying 3 --> True
The answer is 3, found in 4 tries
-------------------- expected = 4 --------------------
try 1: trying 5 --> True
try 2: trying 2 --> False
try 3: trying 4 --> True
try 4: trying 3 --> False
The answer is 4, found in 4 tries
-------------------- expected = 5 --------------------
try 1: trying 5 --> True
try 2: trying 2 --> False
try 3: trying 4 --> False
The answer is 5, found in 3 tries
-------------------- expected = 6 --------------------
try 1: trying 5 --> False
try 2: trying 8 --> True
try 3: trying 7 --> True
try 4: trying 6 --> True
The answer is 6, found in 4 tries
-------------------- expected = 7 --------------------
try 1: trying 5 --> False
try 2: trying 8 --> True
try 3: trying 7 --> True
try 4: trying 6 --> False
The answer is 7, found in 4 tries
-------------------- expected = 8 --------------------
try 1: trying 5 --> False
try 2: trying 8 --> True
try 3: trying 7 --> False
The answer is 8, found in 3 tries
-------------------- expected = 9 --------------------
try 1: trying 5 --> False
try 2: trying 8 --> False
try 3: trying 9 --> True
The answer is 9, found in 3 tries
-------------------- expected = 10 --------------------
try 1: trying 5 --> False
try 2: trying 8 --> False
try 3: trying 9 --> False
The answer is 10, found in 3 tries

Derniers indices :

• la mise à jour de ub est assez naturelle ;
• la mise à jour de lb comporte une petite subtilité pour que le programme ne boucle pas indéfiniment et trouve le résultat en 4 essais ou moins ;
• si le programme boucle à l'infini, ce la vaut le coup de décommenter le print pour voir les valeurs prises par lb, ub et mid: utilise ctrl+c pour l'interrompre.

Pour aller plus loin

En temps normal, tu peux utiliser la fonction dichotomie directement comme suit :

from random import randint

# Copie colle ici la fichier dichotomie

lb = 0
ub = 10
r = randint(lb, ub + 1)
x = dichotomie(lambda i: r <= i, lb, ub)
print(r) # Affiche une valeur
print(x) # Affiche la même valeur

Bonne chance