Exercice 1

Écrire une fonction indices_maxi qui prend en paramètre un tableau non vide de nombre entiers tab, représenté par une liste Python et qui renvoie un tuple (maxi, indices) où :

• maxi est le plus grand élément du tableau tab ;
• indices est une liste Python contenant les indices du tableau tab où apparaît ce plus grand élément.

Exemple :

>>> indices_maxi([1, 5, 6, 9, 1, 2, 3, 7, 9, 8])
(9, [3, 8])
>>> indices_maxi([7])
(7, [0])

Exercice 2

Cet exercice utilise des piles qui seront représentées par des listes Python.

Si pile est une pile, alors pile == [] indique si la pile est vide, pile.pop() retire et renvoie le sommet de la pile et pile.append(v) ajoute la valeur v au sommet de la pile.

Si on considère qu’une fonction manipule une pile, elle ne peut pas utiliser d’autres opérations que celles décrites ci-dessus.

On cherche à écrire une fonction positifs qui prend une pile de nombres entiers en paramètre et qui renvoie une nouvelle pile contenant les entiers positifs de la pile initiale, dans le même ordre, quitte à modifier la pile initiale.

Pour cela, on va également écrire une fonction renverse qui prend une pile en paramètre et qui renvoie une nouvelle pile contenant les mêmes éléments que la pile initiale, mais dans l’ordre inverse. Cette fonction sera également amenée à modifier la pile passée en paramètre.

Compléter le code Python des fonctions renverse et positifs ci-après.

def renverse(pile):
    '''renvoie une pile contenant les mêmes éléments que pile,
    mais dans l'ordre inverse.
    Cette fonction détruit pile.'''
    pile_inverse = ...
    while pile != []:
        ... .append(...)
    return ...


def positifs(pile):
    '''renvoie une pile contenant les éléments positifs de pile,
    dans le même ordre. Cette fonction détruit pile.'''
    pile_positifs = ...
    while pile != []:
        ... = pile.pop()
        if ... >= 0:
            ...
    return ...

Exemples :

>>> renverse([1, 2, 3, 4, 5])
[5, 4, 3, 2, 1]
>>> positifs([-1, 0, 5, -3, 4, -6, 10, 9, -8])
[0, 5, 4, 10, 9]
>>> positifs([-2])
[]

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

• tab est une liste Python d’entiers, non vide
• 1 <= len(tab) <= 10^4
• -10^9 <= tab[i] <= 10^9
• la valeur renvoyée est un tuple (maxi, indices) où indices est une liste d’indices rangés dans l’ordre croissant

Exercice 2

Contraintes :

• pile est une liste Python d’entiers, le sommet de la pile étant le dernier élément de la liste
• 0 <= len(pile) <= 10^4
• -10^9 <= pile[i] <= 10^9
• les entiers positifs incluent 0 (test ... >= 0 du code fourni)
• seule la pile renvoyée est évaluée : la pile passée en paramètre peut être détruite
• renverse et positifs renvoient chacune une nouvelle pile, représentée elle aussi par une liste Python

Corrigé

Exercice 1 - les indices du maximum

L’idée. On veut deux choses en même temps : la plus grande valeur, et la liste de toutes les positions où elle apparaît. On parcourt le tableau une seule fois en gardant le maximum vu jusque-là et la liste de ses positions. À chaque case, trois situations : soit la valeur est plus grande que le maximum actuel, et alors l’ancien maximum ne compte plus du tout (on repart avec la nouvelle valeur et une liste qui ne contient que cette position) ; soit elle est égale au maximum, et on ajoute simplement sa position à la liste ; soit elle est plus petite, et on ne fait rien.

Un petit exemple. Sur [1, 5, 6, 9, 1, 2, 3, 7, 9, 8] : on démarre avec maxi = 1 et indices = [0]. Le 5 est plus grand, donc maxi = 5 et indices = [1]. Puis 6, puis 9 remplacent à leur tour : maxi = 9, indices = [3]. Plus loin, le second 9 est égal au maximum, donc on ajoute sa position : indices = [3, 8]. Résultat : (9, [3, 8]).

def indices_maxi(tab):
    maxi = tab[0]
    indices = [0]
    for i in range(1, len(tab)):
        # Un nouveau maximum rend caducs tous les indices deja retenus
        if tab[i] > maxi:
            maxi = tab[i]
            indices = [i]
        elif tab[i] == maxi:
            indices.append(i)
    return (maxi, indices)

Explications. Comme le tableau est non vide, on peut partir de sa première case : maxi vaut tab[0] et indices vaut [0]. La boucle commence donc à l’indice 1, la case 0 étant déjà traitée. Le point délicat est la différence entre > et == : avec > on a trouvé strictement mieux, donc on remplace la liste d’indices ; avec == on a trouvé un ex aequo, donc on ajoute. Écrire >= dans le premier test effacerait les positions des ex aequo et on ne renverrait que la dernière. Comme on avance de la gauche vers la droite, les indices sont naturellement rangés dans l’ordre croissant.

Exercice 2 - piles : renverse et positifs

L’idée. Sur une pile, on ne peut prendre que le sommet, c’est-à-dire le dernier élément empilé. Donc si on dépile complètement une pile en empilant au fur et à mesure dans une seconde pile, cette seconde pile contient les mêmes éléments mais dans l’ordre inverse : c’est exactement renverse.

Pour positifs, on fait la même chose en ne gardant que les valeurs supérieures ou égales à 0. Mais attention : ce simple parcours retourne l’ordre, comme dans renverse. Or l’énoncé demande les positifs dans le même ordre qu’au départ. Il suffit donc de renverser une dernière fois le résultat, avec la fonction qu’on vient d’écrire. C’est pour cela que le sujet fait écrire renverse en premier.

Un petit exemple. Avec [-1, 0, 5, -3, 4, -6, 10, 9, -8], on dépile en partant du sommet : -8 (rejeté), 9, 10, -6 (rejeté), 4, 5, -3 (rejeté), 0, -1 (rejeté). La pile construite est donc [9, 10, 4, 5, 0], qui est bien à l’envers. On la renverse et on obtient [0, 5, 4, 10, 9].

def renverse(pile):
    '''renvoie une pile contenant les mêmes éléments que pile,
    mais dans l'ordre inverse.
    Cette fonction détruit pile.'''
    pile_inverse = []
    while pile != []:
        pile_inverse.append(pile.pop())
    return pile_inverse


def positifs(pile):
    '''renvoie une pile contenant les éléments positifs de pile,
    dans le même ordre. Cette fonction détruit pile.'''
    pile_positifs = []
    while pile != []:
        element = pile.pop()
        if element >= 0:
            pile_positifs.append(element)
    # On a empile les positifs en partant du sommet : l'ordre est inverse
    return renverse(pile_positifs)

Explications. Les deux fonctions commencent par créer une pile vide [], qui va recevoir le résultat. La boucle while pile != [] s’arrête quand la pile de départ est complètement vidée : c’est ce que veut dire « cette fonction détruit pile » dans les docstrings. Dans positifs, element retient la valeur qu’on vient de dépiler, pour pouvoir la tester avant de décider de l’empiler ou non. Le test est >= 0 et non > 0 : ici 0 est considéré comme positif, ce que confirme l’exemple du sujet où le 0 figure bien dans le résultat.

On n’utilise que les trois opérations autorisées sur les piles : == [] pour tester si elle est vide, .pop() pour retirer le sommet et .append(v) pour empiler. Aucun len, aucun indice, aucune tranche.

Enfin, si aucune valeur n’est positive, pile_positifs reste vide et renverse([]) renvoie [] : le cas positifs([-2]) donne bien [] sans traitement particulier.