Aller au contenu

Programmation de cette recherche en Python☘

Dans le dossier [NSI], créez le dossier [G04_Dichotomie].

Téléchargez le fichier « à trous » TPG04.10.py (clic droit -> [Enregistrer la cible du lien sous]) et enregistrez-le dans ce dossier.

Consignes communes à chaque partie

Le programme principal contient un appel au module doctest : 

##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()
Chacune des fonctions devra passer les tests proposés.
Il faudra aussi ajouter vos propres tests dans le « main » afin de vous entraîner à en réaliser.

Partie 1 - Algorithme de recherche dichotomique☘

Rappel de l'algorithme

On considère l'algorithme suivant dans lequel :

  • tab est un tableau dont les éléments sont triés par ordre croissant et numérotés de 0 à n-1 (donc ayant n éléments).
  • val est une variable dont la valeur est de même type que les éléments du tableau tab.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
i_debut ← 0
i_fin ← longueur(tab)-1

Tant que i_debut ≤ i_fin :
    i_milieu ← (i_debut + i_fin)//2         # indice de l'élément "central"
    Si tab[i_milieu] = val Alors
        Renvoyer Vrai
    Sinon Si tab[i_milieu] < val Alors
        i_debut ← i_milieu+1
    Sinon 
        i_fin ← i_milieu-1

Renvoyer Faux

Complétez la définition de la fonction recherche_dicho() qui implémente l'algorithme de recherche par dichotomie en Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def recherche_dicho(val, tab):
    """
    tab - list, tableau d'entiers, trié en ordre croissant
    val - int, entier
    Sortie: bool - True si val est dans tab, False sinon.
            La recherche est faite suivant le principe de dichotomie.

    >>> tab = [-10, -7, -7, -4, -2, 0, 4, 4, 6, 6]
    >>> recherche_dicho(8, tab)
    False
    >>> tab = [-10, -10, -8, -7, -5, -4, -4, 6, 6, 8]
    >>> recherche_dicho(8, tab)
    True
    >>> tab = []
    >>> recherche_dicho(8, tab)
    False
    """

Partie 2 - Renvoyer l'indice de présence☘

Reprendre le code précédent et le modifier pour que la fonction indice_par_dichotomie() prenant pour paramètre un tableau d'entiers tab trié par ordre croissant et un entier val renvoie l'indice de val si val est présent dans tab et renvoie -1 dans le cas contraire.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def indice_par_dichotomie(val, tab):
    """
    tab - list, tableau d'entiers, trié en ordre croissant
    val - int, entier
    Sortie: int - indice de val si val est dans tab, -1 sinon.
            La recherche est faite suivant le principe de dichotomie.

    >>> tab = [-10, -7, -7, -4, -2, 0, 4, 4, 6, 6]
    >>> indice_par_dichotomie(8, tab)
    -1
    >>> tab = [-10, -10, -8, -7, -5, -4, -4, 6, 6, 8]
    >>> indice_par_dichotomie(8, tab)
    9
    >>> tab = []
    >>> indice_par_dichotomie(8, tab)
    -1
    """