Aller au contenu

TP - Les tableaux en récursif

La fonction étudiée en préambule est nécessaire pour réussir l'ensemble des parties qui suivront. Ces parties sont ensuite globalement indépendantes. Elles ont pour objectif de vous faire travailler de manière récursive les algorithmes sur les tableaux étudiés en classe de 1ère.

Téléchargez le fichier « à trous » TPD03.21.py (clic droit -> [Enregistrer sous]) et enregistrez-le dans le dossier [D03-Recursivite].

Préambule - Une fonction très utile

  1. Complétez le corps de la fonction coupe_tableau() en respectant ses spécifications.
    Attention, seule la méthode .append() est autorisée.

     4
     5
     6
     7
     8
     9
    10
    def coupe_tableau(tab):
        """
        tab - list, un tableau d'entiers
        Sortie: tuple - le premier élément du tableau,
                puis le tableau des éléments de tab sans le premier
        """
        pass
    

  2. Vérifiez votre travail en copiant/collant les lignes suivantes dans le programme principal, à la place du commentaire # A compléter ici :

    90
    91
    92
    93
    94
        tab = [randint(0, 20) for x in range(8)]
        print(tab)
        elt, tab = coupe_tableau(tab)
        print(elt)
        print(tab)
    

    L'exécution de ces lignes doit produire un tableau aléatoire de 8 éléments puis un couple constitué du premier élément de ce tableau et d'un tableau des éléments restant.

    >>> (executing file "TPD03.21.py")
    [7, 4, 9, 4, 3, 4, 8, 13]
    7
    [4, 9, 4, 3, 4, 8, 13]
    

Partie 1 - Somme des éléments d'un tableau

  1. Complétez le corps de la fonction récursive somme_elt() en respectant ses spécifications. Cette fonction doit faire appel à la fonction coupe_tableau().

    17
    18
    19
    20
    21
    22
    def somme_elt(tab):
        """
        tab - list, un tableau d'entiers
        Sortie: int - La somme des éléments du tableau tab
        """
        pass
    

    Une piste
    • Identifiez le cas de base.
    • Identifiez la récursivité : la somme des éléments d'un tableau est la somme entre ... et ...
  2. Vérifiez votre travail en exécutant votre programme puis en testant les commandes suivantes dans la console :

    >>> somme_elt([])
    0
    
    >>> somme_elt([3])
    3
    
    >>> somme_elt([1, 2, 3, 4])
    10
    

  3. Sur votre cahier, prouvez que cette fonction termine en exhibant un variant de boucle.

Partie 2 - Appartenance à un tableau

  1. Complétez le corps de la fonction récursive appartient() en respectant ses spécifications. Cette fonction doit faire appel à la fonction coupe_tableau().

    32
    33
    34
    35
    36
    37
    38
    def appartient(tab, valeur):
        """
        tab - list, un tableau d'entiers
        valeur - int
        Sortie: bool - True si valeur est dans tab, False sinon
        """
        pass
    

  2. Vérifiez votre travail en exécutant votre programme puis en testant les commandes suivantes dans la console :

    >>> appartient([], 3)
    False
    
    >>> appartient([3], 3)
    True
    
    >>> appartient([1, 2, 3, 4], 3)
    True
    
    >>> appartient([1, 2], 3)
    False
    

Partie 3 - Produit des éléments d'un tableau

  1. Complétez le corps de la fonction récursive produit_elt() en respectant ses spécifications. Cette fonction doit faire appel à la fonction coupe_tableau().

    48
    49
    50
    51
    52
    53
    def produit_elt(tab):
        """
        tab - list, un tableau d'entiers
        Sortie: int - Le produit des éléments du tableau tab
        """
        pass
    

    Une piste
    • Identifiez le cas de base.
    • Identifiez la récursivité : le produit des éléments d'un tableau est le produit entre ... et ...
  2. Vérifiez votre travail en exécutant votre programme puis en testant les commandes suivantes dans la console :

    >>> produit_elt([3])
    3
    
    >>> produit_elt([1, 2, 3, 4])
    24
    

Partie 4 - Plus petit élément d'un tableau

  1. Complétez le corps de la fonction récursive minimum() en respectant ses spécifications. Cette fonction doit faire appel à la fonction coupe_tableau().

    43
    44
    45
    46
    47
    48
    def minimum(tab):
        """
        tab - list, un tableau NON VIDE d'entiers
        Sortie: int - Le plus petit élément du tableau tab
        """
        pass
    

    Une piste

    Il peut être utile de définir une fonction auxiliaire...

  2. Vérifiez votre travail en exécutant votre programme puis en testant les commandes suivantes dans la console :

    >>> minimum([3])
    3
    
    >>> minimum([4, 1, 2, 3, 4])
    1
    
    >>> minimum([4, 1, 2, 0, 4])
    0
    

Partie 5 - Un tableau est-il trié ?

  1. Complétez le corps de la fonction récursive est_croissant() en respectant ses spécifications. Cette fonction doit faire appel à la fonction coupe_tableau().

    52
    53
    54
    55
    56
    57
    58
    def est_croissant(tab):
        """
        tab - list, un tableau d'entiers
        Sortie: bool - True si les éléments de tab sont rangés par ordre croissant,
                False sinon
        """
        pass
    
  2. Vérifiez votre travail en exécutant votre programme puis en testant les commandes suivantes dans la console :

    >>> est_croissant([3])
    True
    
    >>> est_croissant([4, 1, 2, 3, 4])
    False
    
    >>> est_croissant([1, 2, 3, 4])
    True
    

Partie 6 - Nombre d'occurence d'un élément dans un tableau

  1. Complétez le corps de la fonction récursive nb_occurrences() en respectant ses spécifications. Cette fonction doit faire appel à la fonction coupe_tableau().

    62
    63
    64
    65
    66
    67
    68
    def nb_occurrences(tab, valeur):
        """
        tab - list, un tableau d'entiers
        valeur - int
        Sortie: int - Le nombre d'occurences de valeur dans tab
        """
        pass
    

  2. Vérifiez votre travail en exécutant votre programme puis en testant les commandes suivantes dans la console :

    >>> nb_occurrences([5, 1, 2, 3, 5], 5)
    2
    
    >>> nb_occurrences([1, 2, 3, 4], 5)
    0
    

Partie 7 - Comprendre le rôle d'une fonction

  1. Effectuez différents tests afin de comprendre le rôle de la fonction ci-dessous :

    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    def mystere(tab, acc = []):
        """
        tab - list
        acc - list, ce tableau est vide par défaut
        Sortie: 
        """
        if tab == [] :
            return acc
        else :
            elt, tab = coupe_tableau(tab)
            if elt not in acc:
                acc.append(elt)
            return mystere(tab, acc)
    

  2. Complétez le docstring de cette fonction puis renommez cette fonction en lui donnant un nom plus explicite (attention à l'appel récursif).