Aller au contenu

Dichotomie

Chaque exercice est fourni avec un fichier Python à compléter et un énoncé « papier » distribué à l'élève et reproduit ci-dessous.

Remarques importantes

  1. Les exercices de cette page ne sont pas classés par ordre de « difficulté », cette notion de difficulté étant subjective et dépendante de chaque élève.

  2. Les solutions proposées ne sont que des propositions !
    Il existe d'autres codes valables pour répondre à chaque problème que ceux proposés ici : il ne faut pas hésiter à les soumettre à votre enseignant pour qu'il vous donne son avis sur les idées mises en oeuvre.

Recherche dichotomique☘

Écrire le code d'une fonction recherche() qui prend en paramètres un tableau tab non vide de nombres entiers triés par ordre croissant et un nombre entier val. Cette fonction doit effectuer une recherche par dichotomie du nombre entier val dans le tableau tab puis renvoyer un indice correspondant au nombre cherché val s’il est dans le tableau, -1 sinon.

Exemples

>>> recherche([2, 3, 4, 5, 6], 5) 
3

>>> recherche([2, 3, 4, 6, 7], 5) 
-1

>>> recherche([], 5) 
AssertionError : tableau vide !

  1. Compléter la définition de la fonction recherche(), sans oublier d'ajouter l'assertion signalée dans l'exemple précédent.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
    def recherche(tab, val):
    """
    tab - 
    val - 
    Sortie: 

    >>> recherche([2, 3, 4, 5, 6], 5) 
    3
    >>> recherche([2, 3, 4, 6, 7], 5) 
    -1
    """
    pass



if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def recherche(tab, val):
    """
    tab - list, tableau non vide d'entiers
    val - int, un entier quelconque
    Sortie: int - indice de val dans tab s'il est présent,
            -1 sinon (recherche par dichotomie !)
    >>> recherche([2, 3, 4, 5, 6], 5) 
    3
    >>> recherche([2, 3, 4, 6, 7], 5) 
    -1
    """
    assert len(tab) != 0, "tableau vide !"
    i_debut = 0
    i_fin = len(tab)-1
    while i_debut <= i_fin:
        i_milieu = (i_debut+i_fin)//2
        if tab[i_milieu] == val:
            return i_milieu
        elif tab[i_milieu] < val:
            i_debut = i_milieu+1
        else:
            i_fin = i_milieu-1
    return -1


if __name__ == '__main__':
    import doctest
    doctest.testmod()

    print(recherche([2, 3, 4, 5, 6], 6) == 4)
    print(recherche([2, 3, 4, 5, 6], 2) == 0)
    print(recherche([2, 3, 4, 5, 6], 4) == 2)
    print(recherche([2, 3, 4, 5, 6, 7], 5) == 3)
    print(recherche([2, 3, 4, 5, 6, 7], 0) == -1)

Nombre d'étapes par dichotomie☘

Écrire le code d'une fonction nb_etapes_par_dichotomie() qui prend en paramètres un tableau tab non vide de nombres entiers triés par ordre croissant et un nombre entier val. Cette fonction doit effectuer une recherche par dichotomie du nombre entier val dans le tableau tab puis renvoyer le nombre de tours de boucles effectués durant la recherche.

Dans les tests, le nombre cherché sera forcément présent dans le tableau.

Exemples

>>> nb_etapes_par_dichotomie([-10, -7, -7, -4, -2, 0, 4, 5, 6, 8], -7) 
2

>>> nb_etapes_par_dichotomie([-10, -10, -8, -7, -5, -4, -3, 6, 6, 8], -3) 
4

>>> nb_etapes_par_dichotomie([], 5) 
AssertionError : Le tableau est vide !

  1. Compléter la définition de la fonction nb_etapes_par_dichotomie(), sans oublier d'ajouter l'assertion signalée dans l'exemple précédent.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
    def nb_etapes_par_dichotomie(tab, val):
    """
    tab - 
    val - 
    Sortie: 

    >>> nb_etapes_par_dichotomie([-10, -7, -7, -4, -2, 0, 4, 5, 6, 8], -7) 
    2
    >>> nb_etapes_par_dichotomie([-10, -10, -8, -7, -5, -4, -3, 6, 6, 8], -3) 
    4
    """
    pass



if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def nb_etapes_par_dichotomie(tab, val):
    """
    tab - list, tableau d'entiers, trié en ordre croissant
    val - int, entier
    Sortie: int - Nombre de tours de boucle nécessaires pour
            déterminer si val est présent dans tab selon une
            recherche effectuée suivant le principe de dichotomie.

    >>> nb_etapes_par_dichotomie([-10, -7, -7, -4, -2, 0, 4, 5, 6, 8], -7) 
    2
    >>> nb_etapes_par_dichotomie([-10, -10, -8, -7, -5, -4, -3, 6, 6, 8], -3) 
    4
    """
    assert len(tab) != 0, "Le tableau est vide !"
    i_debut = 0
    i_fin = len(tab)-1
    compteur = 0

    while i_debut <= i_fin:
        compteur = compteur+1
        i_milieu = (i_debut + i_fin)//2
        if tab[i_milieu] == val :
            return compteur
        elif tab[i_milieu] < val :
            i_debut = i_milieu+1
        else:
            i_fin = i_milieu-1

    return compteur


if __name__ == '__main__':
    import doctest
    doctest.testmod()

    print(nb_etapes_par_dichotomie([2, 3, 4, 5, 6], 6) == 3)
    print(nb_etapes_par_dichotomie([2, 3, 4, 5, 6], 2) == 2)
    print(nb_etapes_par_dichotomie([2, 3, 4, 5, 6], 4) == 1)
    print(nb_etapes_par_dichotomie([2, 3, 4, 5, 6, 7, 8, 9], 9) == 4)