Nous allons dans les exercices qui suivent reprendre les algorithmes de recherche et les modifier plus ou moins.
Reprenons l’algorithme de recherche séquentielle et adaptons le au cas d’une grille, autrement dit d’un tableau à deux dimensions (colonnes/lignes).
a) Proposer une fonction
rechercheSeq()qui prend comme paramètres untableau(à deux dimensions) et unelementet qui retourne la position de cet élément(colonne, ligne)s’il est présent dans ce tableau etNonesinon.
b) Y inclure un jeu de tests.
On pourra chercher deux versions: une première avec une double boucle for et une seconde avec une unique boucle while.
def rechercheSeq(tableau, element):
"""
Retourne la première position trouvée lors de la recherche séquentielle
de l'élèment dans le tableau à deux dimensions données
:param tableau: (list) tableau à deux dimensions
:param element: élèment recherché
:return: (tuple) or (NoneType) la position (colonne, ligne) or None
>>> grille = [[0, 1], [2, 3], [4, 5]] # tableau à 3 lignes et 2 colonnes
>>> rechercheSeq(grille, 4)
(0, 2)
>>> rechercheSeq(grille, 6)
"""
colonnes, lignes = len(tableau[0]), len(tableau)
for lig in range(lignes):
for col in range(colonnes):
if tableau[lig][col] == element:
return (col, lig)
# On peut ajouter "return None" mais bon à savoir s'il n'y a pas de \
# retour par défaut la fonction ne retourne rien (None)
#autre méthode: avec une seule boucle while (méthode vue dans le chapitre 1.5)
def rechercheSeq2(tableau, element):
"""
Retourne la première position trouvée lors de la recherche séquentielle
de l'élèment dans le tableau à deux dimensions données
:param tableau: (list) tableau à deux dimensions
:param element: élèment recherché
:return: (tuple) or (NoneType) la position (colonne, ligne) or None
>>> grille = [[0, 1], [2, 3], [4, 5]] # tableau à 3 lignes et 2 colonnes
>>> rechercheSeq2(grille, 4) == (0, 2)
True
>>> rechercheSeq2(grille, 6) == None
True
"""
colonnes, lignes = len(tableau[0]), len(tableau)
lig, col = 0, 0
while lig < lignes:
if tableau[lig][col] == element:
return (col, lig)
col = col + 1
if col == colonnes:
lig, col = lig + 1, 0
Reprenons cette fois l’algorithme de recherche dichotomique.
a) Proposer une fonction
rechercheDicho()inspiré de l’algorithme vu dans le (3.6) qui prend toujours en paramètres unesequenceet unelementà rechercher et qu retourne cette fois la position de celui-ci s’il est présent etNonesinon.
b) Y inclure un jeu de tests.
def rechercheDicho(sequence, element):
"""
Recherche par la méthode dichotomique la position éventuelle d'un
élément dans une séquence triée
:param sequence: (list) or (tuple) or (str) une séquence donnée triée
:param element: élement recherché
:return: (tuple) or None la position de l'élèment recherché
>>> seq = [2, 5, 6, 9, 12, 23]
>>> rechercheDicho(seq, 9) == 3
True
>>> rechercheDicho(seq, 10) == None
True
"""
g, d = 0, len(sequence)-1
while g <= d:
milieu = (g+d)//2
if sequence[milieu] == element:
return milieu
elif element > sequence[milieu]:
g = milieu + 1
else:
d = milieu - 1