Aller au contenu

Exercices d'entraînement☘

Ces exercices doivent être utilisés pour vous entraîner à programmer. Ils sont généralement accompagnés d'aide et de leur solution pour vous permettre de progresser.

Avant de vous précipiter sur ces solutions dès la première difficulté, n'oubliez pas les conseils suivants :

  • Avez-vous bien fait un schéma au brouillon pour visualiser le problème posé ?
  • Avez-vous essayé de rédiger un algorithme en français, avec vos propres mots, avant de vous lancer dans la programmation sur machine ?
  • Avez-vous utilisé des affichages intermédiaires, des print(), pour visualiser au fur et à mesure le contenu des variables ?
  • Avez-vous testé le programme avec les propositions de tests donnés dans l'exercice ?
  • Avez-vous testé le programme avec de nouveaux tests, différents de ceux proposés ?
Rappels
  • Chaque programme Python doit être sauvegardé sous forme de fichier texte avec l'extension .py.
    Enregistrez ce fichier dans le dossier [G04_Dichotomie] avec le nom donné à l'exercice : ProgG04.51.py, ProgG04.52.py, etc...
  • Pour exécuter ce programme, il suffit de le sauvegarder puis d'appuyer sur la touche [F5].
  • Le programme principal doit contenir un appel au module doctest : 
    ##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()

ProgG04.51 - Décompter le nombre d'étapes☘

Reprendre le code développé en TP et le modifier pour que la fonction nb_tours_par_dichotomie(), prenant pour paramètre un tableau d'entiers tab trié par ordre croissant et un entier val, renvoie le nombre de tours de boucles effectués durant la recherche.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def nb_tours_par_dichotomie(val, tab):
    """
    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.

    >>> tab = [-10, -7, -7, -4, -2, 0, 4, 4, 6, 6]
    >>> nb_tours_par_dichotomie(8, tab)
    4
    >>> tab = [-10, -10, -8, -7, -5, -4, -4, 6, 6, 8]
    >>> nb_tours_par_dichotomie(8, tab)
    4
    >>> tab = []
    >>> nb_tours_par_dichotomie(8, tab)
    0
    """
Une piste

Utilisez un compteur pour dénombrer le nombre de tours de boucle.

Une solution
 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
40
41
42
43
44
45
46
47
48
def nb_tours_par_dichotomie(val, tab):
    """
    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.

    >>> tab = [-10, -7, -7, -4, -2, 0, 4, 4, 6, 6]
    >>> nb_tours_par_dichotomie(8, tab)
    4
    >>> tab = [-10, -10, -8, -7, -5, -4, -4, 6, 6, 8]
    >>> nb_tours_par_dichotomie(8, tab)
    4
    >>> tab = []
    >>> nb_tours_par_dichotomie(8, tab)
    0
    """
    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


##----- Programme Principal & Tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()

    # Tests supplémentaires
    from random import randint
    L = [randint(-10, 10) for i in range(10)]
    L.sort()
    print(L)

    # verif avec nb_tours_par_dichotomie()
    print( nb_tours_par_dichotomie(8, L) )

ProgG04.52 - Nombre de bits d'un entier☘

Compléter la définition de la fonction nb_tours() qui, pour un tableau tab de longueur n renvoie le plus petit entier k tel que 2^k > n, c'est-à-dire le nombre maximal d'itérations dans une recherche dichotomique pour un tableau trié de taille n.

1
2
3
4
5
6
7
8
9
def nb_tours(n):
    """
    n - int, entier positif
    Sortie: int - le plus petit entier k tel que 2**k > n.
    >>> nb_tours(100)
    7
    >>> nb_tours(1000000)
    20
    """
Une première solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def nb_tours(n):
    """
    n - int, entier positif
    Sortie: int - le plus petit entier k tel que 2**k > n.
    >>> nb_tours(100)
    7
    >>> nb_tours(1000000)
    20
    """
    k = 0
    while 2**k <= n:
        k = k+1
    return k


##----- Programme Principal & Tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()
Une deuxième solution

On effectue des divisions successives de n (puis des quotients obtenus) par 2 en comptabilisant le nombre de tours de boucle jusqu'à obtenir 0.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def nb_tours(n):
    """
    n - int, entier positif
    Sortie: int - le plus petit entier k tel que 2**k > n.
    >>> nb_tours(100)
    7
    >>> nb_tours(1000000)
    20
    """
    k = 0
    while n > 0:
        k = k+1
        n = n//2
    return k


##----- Programme de test -----##
if __name__ == "__main__":
    import doctest
    doctest.testmod()
Une troisième solution

La fonction bin() renvoie l'écriture binaire de l'entier n sous la forme d'une chaîne de caractères précédée dont les deux premiers caractères sont 0 et b. Il ne faut donc pas « compter &r&quo; ces caractères... 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def nb_tours(n):
    """
    n - int, entier positif
    Sortie: int - le plus petit entier k tel que 2**k > n.
    >>> nb_tours(100)
    7
    >>> nb_tours(1000000)
    20
    """
    bits = len( bin(n) ) - 2
    return bits


##----- Programme de test -----##
if __name__ == "__main__":
    import doctest
    doctest.testmod()