Exercices - série 2
Exercice 1 : recherche dichotomique⚓︎
Recherche dichotomique
Bob a voulu écrire une version récursive de la recherche par dichotomie.
Malheureusement son code ne fonctionne pas. Corrigez-le.
###
# Testsbksl-nlassert recherche([1, 2, 3, 4, 5, 6], 1) is Truebksl-nlassert recherche([1, 2, 3, 4, 5, 6], 6) is Truebksl-nlassert recherche([1, 2, 3, 4, 5, 6], 8) is Falsebksl-nlassert recherche([1, 2, 3, 4, 5, 6], 0) is Falsebksl-nlassert recherche([1, 2, 3, 4, 5, 8], 7) is Falsebksl-nlbksl-nlbksl-nl 5/5 👉 Il manquait les return ...
Exercice 2 : parité⚓︎
Parité
Compléter la fonction suivante qui doit être une fonction récursive.
⚠️ Il est interdit d'utiliser %
###
# Testsbksl-nlassert estpy-undpair(0) is Truebksl-nlassert estpy-undpair(1) is Falsebksl-nlassert estpy-undpair(12) is Truebksl-nlassert estpy-undpair(13) is Falsebksl-nlbksl-nl# Autres testsbksl-nlbksl-nlassert estpy-undpair(38) is Truebksl-nlassert estpy-undpair(17) is Falsebksl-nlassert estpy-undpair(16) is Truebksl-nlassert estpy-undpair(27) is Falsebksl-nl 5/5 Indice pour la parité
n et n - 2 ont la même parité (tous les deux pairs, ou tous les deux impairs)
Exercice 3 : longueur d'une liste⚓︎
Longueur de liste
Compléter la fonction suivante qui doit être une fonction récursive.
⚠️ Il est interdit d'utiliser len
###
# Testsbksl-nlassert longueur([]) == 0bksl-nlassert longueur([1]) == 1bksl-nlassert longueur([1, 2]) == 2bksl-nlassert longueur([1, 2, 3]) == 3bksl-nlbksl-nl# Autres testsbksl-nlbksl-nlassert longueur([i for i in range(20)]) == 20bksl-nlassert longueur([0 for i in range(30)]) == 30bksl-nlbksl-nl 5/5 Indice pour la longueur d'une liste
Vous pouvez utiliser .pop()
Exercice 4 : bégaiement⚓︎
bégaiement
Ecrire une fonction récursive repeat qui prendra en argument un entier n et une chaine de caractère txt, et qui renvoie une chaine de caractères qui contient n fois la chaine de caractères txt juxtaposées.
Exemple: repeat(5, "bla") renvoie blablablablabla
###
# Testsbksl-nlassert repeat(3,"bla") == "blablabla"bksl-nlassert repeat(3,"") == ""bksl-nlbksl-nl# Autres testsbksl-nlassert repeat(0,"bla") == ""bksl-nlassert repeat(4,"azertyuiop") == 4py-str"azertyuiop"bksl-nl 5/5 Exercice 5 : La tête à Toto⚓︎
La tête à Toto
Compléter la fonction récursive toto telle que :
toto(0)renvoie'0'toto(1)renvoie'(0 + 0)'toto(2)renvoie'((0 + 0) + (0 + 0))'- etc sur le même principe
On garantit que n est un entier positif ou nul.
Compléter ci-dessous
###
# Testsbksl-nlbksl-nlassert toto(0) == '0'bksl-nlassert toto(1) == '(0 + 0)'bksl-nlassert toto(2) == '((0 + 0) + (0 + 0))'bksl-nlbksl-nlbksl-nl# Autres testsbksl-nlbksl-nlassert toto(6) == ('((((((0 + 0) + (0 + 0)) + ((0 + 0) + (0 + 0))) + (((0 + 0) + (0 + 0)) + ((0 'bksl-nl '+ 0) + (0 + 0)))) + ((((0 + 0) + (0 + 0)) + ((0 + 0) + (0 + 0))) + (((0 + 0) 'bksl-nl '+ (0 + 0)) + ((0 + 0) + (0 + 0))))) + (((((0 + 0) + (0 + 0)) + ((0 + 0) + (0 'bksl-nl '+ 0))) + (((0 + 0) + (0 + 0)) + ((0 + 0) + (0 + 0)))) + ((((0 + 0) + (0 + 'bksl-nl '0)) + ((0 + 0) + (0 + 0))) + (((0 + 0) + (0 + 0)) + ((0 + 0) + (0 + 0))))))')bksl-nl 5/5 toto(0) renvoie '0'bksl-nl - toto(1) renvoie '(0 + 0)'bksl-nl - toto(2) renvoie '((0 + 0) + (0 + 0))'bksl-nl - etc sur le même principebksl-nlbksl-nl n est un entier positifbksl-nl """bksl-nlbksl-nl if n == 0:bksl-nl return '0'bksl-nl else:bksl-nl motif = toto(n - 1)bksl-nl return '(' + motif + ' + ' + motif + ')'bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl
Exercice 6 : Test de palindrome⚓︎
Palindrome
Un mot est un palindrome s'il se lit de la même façon de droite à gauche comme de gauche à droite.
Exercice
Écrire une fonction récursive est_palindrome qui prend en paramètre une chaine de caractères mot et renvoie le booléen True si mot est un palindrome ou False sinon.
Premiers indices
- Le premier caractère de la chaine
motestmot[0] - Le dernier caractère de la chaine
motestmot[-1] - Pour une copie d'une tranche ("slice" en anglais) du second jusqu'à l'avant-dernier caractère d'une chaine
mot, on peut écriremot[1:-1]
Derniers indices
- Si la chaine fait zéro ou un caractère, c'est un palindrome.
- Sinon on peut comparer le premier et le dernier caractère.
- Enfin, un appel récursif permet de répondre sur le reste de la chaine.
Palindrome
Compléter ci-dessous
###
# Testsbksl-nlassert estpy-undpalindrome("") is Truebksl-nlassert estpy-undpalindrome("a") is Truebksl-nlassert estpy-undpalindrome("mot") is Falsebksl-nlassert estpy-undpalindrome("tot") is Truebksl-nlassert estpy-undpalindrome("elle") is Truebksl-nlassert estpy-undpalindrome("toto") is Falsebksl-nlassert estpy-undpalindrome("canar") is Falsebksl-nlbksl-nl# Autres testsbksl-nlassert estpy-undpalindrome("azertyuiopzpoiuytreza") is Truebksl-nlassert estpy-undpalindrome("bzertyuiopzpoiuytreza") is Falsebksl-nlassert estpy-undpalindrome("azertyuiopzpoiuytrezb") is Falsebksl-nlassert estpy-undpalindrome("azertyuiopzaoiuytreza") is Falsebksl-nlassert estpy-undpalindrome("azertyuiobzpoiuytreza") is Falsebksl-nlassert estpy-undpalindrome("azertyuioppoiuytreza") is Truebksl-nlassert estpy-undpalindrome("bzertyuioppoiuytreza") is Falsebksl-nlassert estpy-undpalindrome("azertyuioppoiuytrezb") is Falsebksl-nlassert estpy-undpalindrome("azertyuiobpoiuytreza") is Falsebksl-nlbksl-nlbksl-nl 5/5 Autre correction possible
🐍 Script Python
def est_palindrome(mot):
"Détermine si mot est un palindrome"
if len(mot) < 2:
return True
else:
return mot[0] == mot[-1] and est_palindrome(mot[1:-1])
Remarquons que la deuxième partie du and (est_palindrome(mot[1:-1])) ne sera évaluée en Python que si mot[0] == mot[-1] est évalué à True (évaluation paresseuse).
Remarque
⚠ Cette solution à base de copie de "slices" (tranches en français) n'est pas efficace, nous verrons plus tard une méthode plus efficace avec les indices.
Exercice 7 : triangles⚓︎
A faire
Écrire deux fonctions (procédures) récursives triangle_bas, puis triangle_haut prenant un entier n non nul en paramètre et qui affichent un triangle. Ces fonctions ne renvoient rien.
🐍 Console Python
>>> triangle_bas(4) # affiche un triangle tête en bas
####
###
##
#
🐍 Console Python
>>> triangle_haut(4) # affiche un triangle tête en haut
#
##
###
####
Triangles
Compléter ci-dessous
###
Solution
Attention
L'ordre des instructions est bien sûr important !
🐍 Script Python
def triangle_bas(n):
"""Affiche un triangle tête en bas"""
if n > 0:
print("#" * n)
triangle_bas(n - 1)
def triangle_haut(n):
"""Affiche un triangle tête en haut"""
if n > 0:
triangle_haut(n - 1)
print("#" * n)
Exercice 8 : Si vous avez du temps ... problème de la grenouille⚓︎
🐸
Une grenouille doit monter un escalier. Quand elle saute pour monter, elle monte de 1 ou 2 marches.
Combien de chemins différents existent-ils pour un escalier de n marches ?
Vous êtes en complète autonomie pour cet exercice facultatif.
👉 Montrer au professeur votre solution, ou vos tentatives.
La fonction nbre_chemins prend en paramètre un entier n que l'on garantit strictement supérieur à zéro.
Compléter ci-dessous
###
# Testsbksl-nlassert nbrepy-undchemins(1) == 1bksl-nlassert nbrepy-undchemins(2) == 2bksl-nlassert nbrepy-undchemins(3) == 3bksl-nlassert nbrepy-undchemins(4) == 5bksl-nlassert nbrepy-undchemins(11) == 144bksl-nlbksl-nl# Autres testsbksl-nlassert nbrepy-undchemins(10) == 89bksl-nlbksl-nlbksl-nl 20/20 Attention
Cette solution récursive produit un très grand nombre d'appels qui n'est pas du tout efficace, car des calculs identiques sont réalisés récursivement plusieurs fois. Si vous testez cette solution pour un grand nombre de marches, cela prendra beaucoup de temps, ou fera "planter" Python.
Nous étudierons plus tard la programmation dynamique.
Crédits⚓︎
Franck Chambon