Ctrl+K

Exercices

Exercices#

Exercice 1#

On donne l’algorithme suivant:

1def occurence(tableau, valeur):
2    n = 0
3    for v in tableau:
4        if v == valeur:
5            n = n + 1
6    return n

  1. Combien de fois le test est-il exécuté dans l’appel : occurence([1,2,1,2,2,1,2,1,1,1,2],1) ?

  2. Combien de fois le test est-il exécuté dans l’appel : occurence([i*2 for i in range(50)],50) ?

  3. Quelle est la complexité de cette recherche d’occurence dans un tableau de dimension \(n\) ?

Exercice 2#

La recherche d’une valeur minimale ou maximale dans un tableau de nombres peut se faire en Python avec les fonctions min et max.

Ici, on s’intéresse à la recherche de ces valeurs particulières sans utiliser les fonctions min et max de python.

  1. Soit t un tableau de nombres trié dans l’ordre croissant.

    1. Comment obtient-on la valeur minimale du tableau ? La valeur maximale ?

    2. Quelles est la complexité de chacune de ces recherches ?

  2. On suppose maintenant que le tableau t n’est pas trié. Donner un algorithme de recherche de la valeur minimale de ce tableau.

  3. Écrire la fonction Python recherche_min qui prend en paramètre un tableau non trié et qui renvoie la valeur minimale du tableau.

  4. Tester votre fonction avec le tableau t tel que:

    1. t = [7,2,9,8,6,4,9,1,5,6]

    2. t = [ i % 37 for i in range(5,100,7)]

  5. Quelle est la complexité de l’algorithme de recherche de la valeur minimale ?

Exercice 3#

Une image composée de pixel noir ou blanc se représente par un tableau à 2 dimensions. Voici un exemple d’image.

../_images/image_5x8.png

L’image se représente par le tableau suivant où chaque 0 représente un pixel blanc et chaque 1 représente un pixel noir.

img = [
        [0,0,1,0,0,1,0,0],
        [0,1,0,1,1,0,1,0],
        [0,0,0,1,1,0,0,0],
        [0,0,1,1,1,1,0,0],
        [0,1,1,0,0,1,1,0]
]

  1. Écrire une fonction recherche(pixel) qui renvoie le nombre de pixels dont la couleur est indiquée par le paramètre pixel.

  2. Combien de fois le test de vérification de la couleur du pixel est-il exécuté pour l’image représentée ci-dessus ?

  3. Combien de fois ce test est est-il exécuté dans le cas d’une image carrée composée de n lignes et n colonnes ? En déduire la complexité de la fonction recherche.

Contenu