Bonjour, besoin d'aide nsi Dichotomie: Soit TAB = [0 ; 2 ; 4 ; 6 ; 8 ; 10 ; 12 ; 14 ; 16 ; 18 ; 20 ; 22] un tableau d'entiers. On utilise un algorithme de reche
Informatique
silvasclm
Question
Bonjour, besoin d'aide nsi
Dichotomie:
Soit TAB = [0 ; 2 ; 4 ; 6 ; 8 ; 10 ; 12 ; 14 ; 16 ; 18 ; 20 ; 22] un tableau d'entiers.
On utilise un algorithme de recherche dichotomique pour chercher si le nombre 11 est
présent dans le tableau.
a. Quels sont les sous-tableaux qui sont parcourus lors de cette recherche ?
b. Même question avec le nombre 20.
Dichotomie:
Soit TAB = [0 ; 2 ; 4 ; 6 ; 8 ; 10 ; 12 ; 14 ; 16 ; 18 ; 20 ; 22] un tableau d'entiers.
On utilise un algorithme de recherche dichotomique pour chercher si le nombre 11 est
présent dans le tableau.
a. Quels sont les sous-tableaux qui sont parcourus lors de cette recherche ?
b. Même question avec le nombre 20.
1 Réponse
-
1. Réponse caylus
Réponse :
Bonjour,
Explications :
#on suppose que min(table)<=x<max(table)
def dicho(x,table):
a = 0
b = len(table)-1
m = (a+b)//2
while a < b :
print ("a=",a,"m=",m,"b=",b)
if table[m] == x:
return True
elif table[m] > x :
b = m-1
else :
a = m+1
m = (a+b)//2
return False
TAB = [0 , 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 , 22]
print (dicho(11,TAB))
print (dicho(20,TAB))
"""
a= 0 m= 5 b= 11
a= 6 m= 8 b= 11
a= 6 m= 6 b= 7
False
a= 0 m= 5 b= 11
a= 6 m= 8 b= 11
a= 9 m= 10 b= 11
True
"""