INGIniousAttention
Ce dernier exercice peut sembler un peu plus difficile. Il est néanmoins recommandé à chaque étudiant de le faire jusqu'au bout car les équations de récurrence sont un des thèmes revenant très régulièrement à l'examen...
De plus, les concepteurs de cette exercice ont veillé à vous fournir un feedback détaillé pour expliquer chaque réponse. Des informations importantes vous seront donc souvent données, même en cas de mauvaise réponse (lorsque ce n'est pas le cas, c'est parce que le choix d'une telle réponse est jugé mauvais de façon "évidente"...). En cas de bonne réponse, un feedback est aussi généralement prévu afin de justifier en détails pourquoi la réponse est bonne. C'est ce genre de justification qui constitue une preuve de compréhension de la matière.
L'algorithme suivant permet de créer une chaîne de caractères représentant une montagne (ou un sapin, selon votre point de vue...) en ASCII.
def mountain(n):
"""
pre: n >= 0
post: renvoie un str représentant une montagne de hauteur `n`
"""
def mountain_aux(n, m):
"""
pre: n >= 0, m >= 0
"""
line = (n * " ") + "/" + ("+" * m) + "\\" + (n * " ")
if n == 0:
return line
return line + "\n" + mountain_aux(n - 1, m + 2)
return mountain_aux(n, 0)
Le résultat de l'appel mountain(4) est :
/\
/++\
/++++\
/++++++\
/++++++++\
On vous demande de calculer les complexités temporelle et spatiale de l'implémentation proposée ci-dessus. À cette fin, commencez par écrire les équations de récurrence de l'algorithme. Pensez en termes de cas de base et de cas récursif. Utilisez ensuite la méthode de substitution vue au cours pour en déduire la complexité.
Note :