Reprises

Certains exercices ont été résolus avec des copies de tranche, cette méthode étant lente, nous allons les reprendre avec une méthode plus efficace.

Maximum d'une liste non vide

Écrire une fonction récursive maximum telle que maximum(nombres, i, j) renvoie le maximum des éléments de la liste nombres dont les indices k sont tels que i <= k < j. On garantit que i < j.

###

LancerTéléchargerTéléverser RechargerSauvegarder

def maximum(nombres, i, j):bksl-nl """Renvoie le maximum de nombres[i:j]bksl-nl sans utiliser de tranchebksl-nl """bksl-nl ...bksl-nlbksl-nldef maxi(nombres):bksl-nl return maximum(nombres, 0, len(nombres))bksl-nlbksl-nlbksl-nlassert maxi([7]) == 7bksl-nlassert maxi([7, 13]) == 13bksl-nlassert maxi([13, 7]) == 13bksl-nlassert maxi([-19, -13, -19]) == -13bksl-nlbksl-nl

Réponse

🐍 Script Python

def maximum(nombres, i, j):
    ip1 = i + 1
    if ip1 == j:
        return nombres[i]
    else:
        maxi_fin = maximum(nombres, ip1, j)
        if maxi_fin > nombres[i]:
            return maxi_fin
        else:
            return nombres[i]

On peut alors utiliser cette fonction

🐍 Script Python

def maxi(nombres):
    return maximum(nombres, 0, len(nombres))

assert maxi([7]) == 7
assert maxi([7, 13]) == 13
assert maxi([13, 7]) == 13
assert maxi([-19, -13, -19]) == -13

Test de palindrome

Écrire une fonction récursive telle que est_palindrome(mot, i, j) renvoie un booléen qui détermine si la chaine mot est un palindrome entre les indices i inclus et j exclu. On garantit i <= j.

###

LancerTéléchargerTéléverser RechargerSauvegarder

def estpy-undpal(mot, i, j):bksl-nl ...bksl-nl bksl-nlbksl-nldef estpy-undpalindrome(mot):bksl-nl return estpy-undpal(mot, 0, len(mot))bksl-nlbksl-nlassert estpy-undpalindrome('mot') == Falsebksl-nlassert estpy-undpalindrome('tot') == Truebksl-nlassert estpy-undpalindrome('esse') == Truebksl-nlbksl-nl

Réponse

🐍 Script Python

def est_pal(mot, i, j):
    "Détermine si mot[i:j] est un palindrome"

    if i + 1 > j - 1:
        # mot vide ou bien une lettre
        return True
    else:
        return (mot[i] == mot[j - 1]) and est_pal(mot, i + 1, j - 1)
        # dans ce cas on a i + 1 <= j - 1

Compte d'occurrences

Écrire une fonction récursive telle que nb_occurrences(lettre, mot, i) renvoie le nombre d'occurrences de la lettre dans le mot à partir de l'indice i.

###

LancerTéléchargerTéléverser RechargerSauvegarder

# fonction récursivebksl-nldef nbpy-undocc(lettre, mot, i):bksl-nl ...bksl-nlbksl-nl# fonction qui appelle nbpy-undocc une foisbksl-nldef nbpy-undoccurrences(lettre, mot):bksl-nl ...bksl-nlbksl-nl# testsbksl-nlassert nbpy-undoccurrences("o", "bonjour") == 2bksl-nlassert nbpy-undoccurrences("i", "salut") == 0bksl-nlassert nbpy-undoccurrences("t", "tttt") == 4bksl-nlbksl-nl

Réponse

🐍 Script Python

def nb_occ(lettre, mot, i):
    "Renvoie le nombre d'occurrences de la lettre dans mot[i:]"
    if i == len(mot):
        return 0
    else:
        resultat = nb_occ(lettre, mot, i + 1)
        if lettre == mot[i]:
            resultat += 1
        return resultat

def nb_occurrences(lettre, mot):
    "Renvoie le nombre d'occurrences de la lettre dans mot"
    # on part de 0
    return nb_occ(lettre, mot, 0)


assert nb_occurrences("o", "bonjour") == 2
assert nb_occurrences("i", "salut") == 0
assert nb_occurrences("t", "tttt") == 4

On peut aussi proposer une solution sans fonction intermédiaire grâce à un paramètre par défaut.

🐍 Script Python

def nb_occurrences(lettre, mot, i=None):
    "Renvoie le nombre d'occurrences de la lettre dans mot[i:]"
    if i is None:
        i = 0
    if i == len(mot):
        return 0
    else:
        resultat = nb_occ(lettre, mot, i + 1)
        if lettre == mot[i]:
            resultat += 1
        return resultat

Cette technique est aussi valable pour les exercices précédents.