C7 : Exercices

Assertions

C7.E1 : Vérification de préconditions

On s'intéresse à une fonction f(liste) qui prend une liste triée d'entiers en paramètre.

Écrire les assertions qui permettent, en début de fonction de vérifier les préconditions suivantes sur la liste passée en paramètre :

Validation d'une fonction

C7.E11 : Doctests

1) Écrire la fonction sans_doubon(liste:list) -> list qui prend une liste d'entiers positifs en paramètres et renvoie une liste contenant les mêmes valeurs sans doublons.

2) Proposer un jeu de tests pertinent pour cette fonction sous la forme de doctests.

Afficher la correction 
def sans_doubon(liste:list) -> list:
    """
    Renvoie la liste passée en paramètre sans doublons

    Param:    
        liste (list): liste
    Return
        (list) : liste sans doublons

    Exemples:
    >>> sans_doubon([1])
    [1]
    >>> sans_doubon([1, 5])
    [1, 5]
    >>> sans_doubon([1, 1])
    [1]
    >>> sans_doubon([1, 1, 5, 5])
    [1, 5]
    >>> sans_doubon([1, 1, 1, 5])
    [1, 5]
    """
    li = []
    for val in liste:
        if val not in li:
            li.append(val)
    return li

# Programme principal
import doctest
doctest.testmod(verbose = True)

C7.E12 : Tests avec des assertions

1) Écrire la fonction miroir(chaine:str) -> str qui prend une chaine de caractères en paramètres et renvoie une chaine avec les caractères dans l'ordre inverse.

2) Proposer un jeu de tests pertinent pour cette fonction en utilisant des assertions dans le programme principal.

C7.E13 : Invalider une fonction avec des tests

On considère la fonction suivante qui est censée tester l'appartenance d'une valeur à un tableau.

def appartient(val, tab):
    for i in range(len(t)):
        if t[i] == v:
            trouvee = True
        else:
            trouvee = False
    return trouvee

Proposer des tests pour cette fonction, et en particulier des tests montrant les différentes raisons pour lesquelles elle est incorrecte.

Complexité

C7.E21

Sur feuille

Dans cet exercice on s'intéresse aux algorithmes qui permettent de transformer des listes d'effectifs en des liste d'effectifs cumulés.

Par exemple ces algorithmes doivent transformer [2, 7, 8, 5, 6] en [2, 9, 17, 22, 28].

1) On s'intéresse à l'algorithme codé dans la fonction suivante : 

def eff_cumul_v1(l:list)->list:
    n = len(l)
    liste_cumul = []
    for i in range(n):
        cumul = 0
        for j in range(i+1):
            cumul = cumul + l[j]
        liste_cumul.append(cumul)
    return liste_cumul

# Programme principal
assert eff_cumul_v1([2]) == [2]
assert eff_cumul_v1([2, 10]) == [2, 12]
print("les tests sont ok")

1.a. Déterminer le nombre d'additions effectuées par la fonction avec une liste de longueur 1, puis 2, puis 3 et enfin 4.

1.b. Déterminer le nombre d'addition effectuées par la fonction avec une liste de longueur n.

2) Une version plus optimale

2.a. Proposer une version plus optimale de cette fonction de façon à ce que son coût soit linéaire.

2.b. Déterminer le nombre d'additions effectuées par votre fonction avec une liste de longueur 1, puis 2, puis 3 et enfin 4.

Afficher la correction

1)

1.a.

• Pour une liste de longueur 1, la fonction effectue 0 additions.

• Pour une liste de longueur 2, la fonction effectue 1 additions.

• Pour une liste de longueur 3, la fonction effectue 3 additions.

• Pour une liste de longueur 4, la fonction effectue 6 additions.

1.b.

Pour une liste de longueur n, la fonction effectue 1 + 2 + 3 + ... + (n-1) additions.

Soit, n×(n-1)/2 additions.

2)

2.a.

def eff_cumul_v1(l:list)->list:
    n = len(l)
    liste_cumul = []
    cumul = 0
    for i in range(n):
        cumul = cumul + l[i]
        liste_cumul.append(cumul)
    return liste_cumul

# Programme principal
assert eff_cumul_v1([2]) == [2]
assert eff_cumul_v1([2, 10]) == [2, 12]
print("les tests sont ok")

2.b.

• Pour une liste de longueur 1, la fonction effectue 0 additions.

• Pour une liste de longueur 2, la fonction effectue 1 additions.

• Pour une liste de longueur 3, la fonction effectue 2 additions.

• Pour une liste de longueur 4, la fonction effectue 3 additions.

C7.E22 Fonction search

Sur feuille

On s'intéresse à la fonction ci-dessous.

def search(x:int, l:list)->int:
    # x est la valeur à chercher
    # l est une liste de valeurs
    for i in range(len(l)):
        if x == l[i]:
            return i
    return None

1) Écrire la docstring de cette fonction.

2) Déterminer la coût de l'algorithme utilisé en fonction de la longueur de la liste passée en paramètre.

C7.E23(**) : Recherche dans une grille triée

Sur feuille

D'après e-nsi.gitlab.io/pratique/N3/540-grille_triee/sujet/

On considère une grille triée, c'est-à-dire une grille de \(n\) lignes et \(m\) colonnes, d'éléments distincts, dont chaque ligne et chaque colonne est triée dans l'ordre croissant.

Exemple de grille triée :

11 33 42 63
20 52 67 80
25 61 88 95

Les grilles seront implémentés par une classe Grille dont les seules méthodes sont :

Pour la suite de l'exercice, il n'est pas nécessaire de connaitre le détail du code de l'implémentation de la classe Grille.

Travail à faire :

On souhaite savoir si un élément est présent dans une grille.

1) Fonction pour rechercher un élément dans la grille

Écrire une fonction recherche(elt, grille) qui renvoie None si elt est absent de grille, ou le tuple (i, j) correspondant à la position de elt si elt est présent dans grille.

2) Aptimisation de la fonction

Pour cet exercice, on définit le cout de la recherche comme étant le nombre d'appels à la méthode donne_valeur.

2.a) Déterminer le cout de votre algorithme en fonction de \(n\) et \(m\).

2.b, question difficile) Il est possible de coder une fonction avec un cout en \(n+m\) dans le pire cas.

Si le cout de votre algorithme est moins bon qu'un cout en \(n+m\), essayer d'optimiser votre fonction.

Afficher l'aide

L'algorithme par de la case en haut à droite.

A partir de cette case :

  • • si la valeur courante est égale à la elt → trouvé ;
  • • si la valeur courante est plus petite que elt → on se déplace vers la gauche (toute la colonne est trop grande) ;
  • • si la valeur courante est plus grande que elt → on se déplace vers le bas (toute la ligne est trop petite).
Afficher la correction 
class Grille:
    def __init__(self, lili):
        self.__donnees = lili


    def nb_lignes(self):
        """
        Renvoie le nombre de lignes de la grille.
        """
        return len(self.__donnees)
    
    def nb_colonnes(self):
        """
        Renvoie le nombre de colonnes de la grille.
        """
        return len(self.__donnees[0])

    def get_valeur(self, i, j):
        """
        Renvoie la valeur de la colonne i et de la ligne j
        """
        return self.__donnees[j][i]

def recherche_v1(elt, grille):
    """
    Cout en n×m
    """
    for i in range(grille.nb_colonnes()):
        for j in range(grille.nb_lignes()):
            if grille.get_valeur(i, j) == elt:
                return (i, j)

def recherche_v2(elt, grille):
    """
    Cout en n+m
    """
    nb_col = grille.nb_colonnes()
    nb_lig = grille.nb_lignes()
    i = nb_col - 1
    j = 0
    while i >= 0 and j < nb_lig:
        if elt == grille.get_valeur(i, j):
            return (i, j)
        elif elt > grille.get_valeur(i, j):
            j = j + 1
        else:
            i = i - 1
    return None


liliTest = [[11, 33, 42, 63],
            [20, 52, 67, 80],
            [25, 61, 88, 95]]

grilleTest = Grille(liliTest)



assert recherche_v1(10, grilleTest) == None
assert recherche_v1(11, grilleTest) == (0, 0)
assert recherche_v1(53, grilleTest) == None
assert recherche_v1(67, grilleTest) == (2, 1)
assert recherche_v1(100, grilleTest) == None

assert recherche_v2(10, grilleTest) == None
assert recherche_v2(11, grilleTest) == (0, 0)
assert recherche_v2(53, grilleTest) == None
assert recherche_v2(67, grilleTest) == (2, 1)
assert recherche_v2(100, grilleTest) == None

print('Les tests sont ok')

Preuve d'un algorithme

C7.E31 : Une boucle infinie

Sur feuille

On s'intéresse à la fonction suivante.

from random import randint
def fct()->list:
    val = 0
    li = [val]
    while val < 1:
        val = val + randint(0,1) * 2 - 1
        li.append(val)
    return li

1) Donner deux exemples de listes que cette fonction peut renvoyer.

2) Justifier qu'il est possible que l'exécution de cette fonction ne se terminer jamais.

3) Indiquer, en justifiant, la dernière valeur de la liste renvoyée par la fonction lorsqu'elle se termine.

Afficher la correction

1)

Exemple n° 1 : [0, 1]

Exemple n° 2 : [0, -1, 0, 1]

2)

A la ligne 6, val peut être augmenté

  • • de 1 dans le cas ou randint renvoie 1 ;
  • • de -1 dans le cas ou randint renvoie 0.

Si randint renvoie systématiquement 0, alors val va décroitre indéfiniment. La boucle ne se terminera jamais.

3)

La dernière valeur de la liste est toujours 1 (et l'avant dernière valeur toujours 0).

En effet, la boucle se terminer lorsque val égal 1. Cette valeur a été ajoutée en fin de liste lors de l'itération précédente.