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
.
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
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
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
.
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
def est_pal(mot, i, j):
"Détermine si mot[i:j] est un palindrome"
if i + 2 < j:
return True
else:
return (mot[i] == mot[j - 1]) and est_pal(mot, 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
.
# 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
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.
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.