applicationmatrice.py

Created on December 15, 2024
2.33 KB
# question 1
# D'après la définition des 
matrices triées, a[x][y] <= 
v pour tout entier x 
tel que 0 <= x <= m // 2
# et tout entier y tel que 
0 <= y <= n //2.
# Ainsi si l'élément 
recherché est supérieur à 
v, on peut éliminer le quadrant 
supérieur gauche.

# question 2
# D'après la définition
des matrices triées, a[x][y] 
>= v pour tout entier x 
tel que m // 2 <= x <= m
# et tout entier y tel que 
n //2 <= y <= n.
# Ainsi si l'élément 
recherché est inférieur à v, 
on peut éliminer le quadrant 
inférieur droit.

On cherche a : 
Écrire une fonction 
dicho_matrice 

def dicho_matrice(a : list, e : int, i :int, j : int, k : int, l :int) :
''' Si e est présent dans a[i..j][k..l], cette fonction renvoie un couple (lg,cl)
tel que a[lg][cl] soit égale à e, sinon elle renvoie None.
'''
if i < 0 or j >= len(a) or i > j or k < 0 or l >= len(a[0]) or k > l :
return None
else :
vx, vy = i + (j-i)//2, k + (l-k)//2
v = a[vx][vy]
if v < e :
# L'élement recherché est supérieur à v, on peut éliminer le quadrant supérieur gauche.
candidat = dicho_matrice(a, e, vx+1, j, vy+1, l) # recherche dans le quadrant inférieur droit
if candidat is None :  candidat = dicho_matrice(a, e, vx+1, j, k, vy) # recherche dans le quadrant inférieur gauche
if candidat is None :  candidat = dicho_matrice(a, e, i, vx, vy+1, l) # recherche dans le quadrant supérieur droit
return candidat
elif v > e :
# L'élement recherché est inférieur à v, on peut éliminer le quadrant inférieur droit.
candidat = dicho_matrice(a, e, i, vx-1, k, vy-1) # recherche dans le quadrant supérieur gauche
if candidat is None :
  candidat = dicho_matrice(a, e, i, vx-1, vy, l) # recherche dans le quadrant supérieur droit
if candidat is None :  
  candidat = dicho_matrice(a, e, vx, j, k, vy-1) # recherche dans le quadrant inférieur gauche
return candidat
else : return vx, vy



Les Asserts : 

a=[ [12 ,19 , 21 , 26], 
[17 ,20 , 24 ,29], 
[25 , 26 , 26 , 31]]
assert dicho_matrice
(a, 15, 0, 5, 0, 3) is None   # recherche avec des bornes supérieures à la taille de la matrice
assert dicho_matrice
(a, 15, 0, 0, 0, 3) is None   # recherche d'une valeur absente
assert dicho_matrice
( [], 15, 0, 2, 0, 3) is None   # recherche dans une matrice vide
assert dicho_matrice
(a, 17, 0, 2, 0, 3) == (1,0)
assert dicho_matrice
(a, 21, 0, 2, 0, 3) == (0,2)