Programmation Python et récursivité

On considère la fonction suivante, qui prend en paramètre un entier naturel n.

def somme_chiffres(n):

    if n < 10:

        return n

    else:

        return n % 10 + somme_chiffres(n // 10)

1. Donner la valeur de 2 548 % 10 et celle de 2 548 // 10.

2. Détailler les appels successifs effectués par somme_chiffres(2548), puis donner la valeur renvoyée.

3. Justifier que l'exécution de somme_chiffres(n) se termine pour tout entier naturel n.

On considère la fonction récursive suivante.

def puissance(x, n):

    if n == 0:

        return 1

    else:

        return x * puissance(x, n - 1)

1. Donner la valeur renvoyée par puissance(3, 4).

2. Indiquer le nombre total d'appels de la fonction puissance effectués lors de l'exécution de puissance(3, 4), appel initial compris.

3. Expliquer ce qui se produit lors de l'exécution de puissance(2, -1).

4. Écrire une assertion à placer au début de la fonction pour se prémunir contre ce problème.

On considère la fonction suivante, qui prend en paramètre une chaîne de caractères s.

def est_palindrome(s):

    if len(s) <= 1:

        return True

    elif s[0] != s[-1]:

        return False

    else:

        return est_palindrome(s[1:-1])

1. Donner la valeur renvoyée par est_palindrome("radar") et préciser le nombre d'appels de la fonction effectués, appel initial compris.

2. Donner la valeur renvoyée par est_palindrome("lycee") et préciser le nombre d'appels effectués.

3. Identifier le cas de base et le cas récursif, puis justifier la terminaison en précisant la quantité qui décroît strictement à chaque appel.

4. Écrire une fonction récursive compte(s, c) qui renvoie le nombre d'occurrences du caractère c dans la chaîne s.

On considère la fonction de Fibonacci définie par $F_0 = 0$, $F_1 = 1$ et $F_n = F_{n-1} + F_{n-2}$ pour $n \geqslant 2$.

def fib(n):

    if n <= 1:

        return n

    else:

        return fib(n - 1) + fib(n - 2)

On note $C(n)$ le nombre total d'appels de la fonction fib (appel initial compris) lors de l'exécution de fib(n).

1. Donner $C(0)$, $C(1)$, puis justifier que $C(n) = 1 + C(n-1) + C(n-2)$ pour $n \geqslant 2$.

2. Calculer $C(2)$, $C(3)$, $C(4)$ et $C(5)$.

3. Montrer par récurrence que, pour tout entier $n \geqslant 0$, $C(n) = 2F_{n+1} - 1$.

4. On propose la version suivante.

def fib_memo(n, memo=None):

    if memo is None:

        memo = {}

    if n in memo:

        return memo[n]

    if n <= 1:

        resultat = n

    else:

        resultat = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)

    memo[n] = resultat

    return resultat

a) Expliquer le rôle du dictionnaire `memo`.

b) Expliquer pourquoi le nombre de calculs effectifs de la valeur $F_k$ est au plus égal à 1 pour chaque $k$ compris entre 0 et $n$.

On souhaite écrire une fonction maximum(tab) qui renvoie le plus grand élément d'une liste non vide tab de nombres entiers. Un élève propose le code suivant.

def maximum(tab):

    m = 0

    for x in tab:

        if x > m:

            m = x

    return m

1. Donner la valeur renvoyée par maximum([3, 8, 2]).

2. Donner la valeur renvoyée par maximum([-5, -2, -9]). Expliquer pourquoi cette valeur ne correspond pas à la spécification de la fonction.

3. Corriger la fonction pour qu'elle soit conforme à sa spécification.

4. Proposer un jeu de trois tests, dont un avec uniquement des nombres négatifs, qui permet de détecter l'erreur initiale.

On étudie le tri fusion d'une liste de nombres selon le principe « diviser pour régner ». On rappelle que la fonction fusion prend en paramètres deux listes triées par ordre croissant et renvoie une liste triée contenant tous leurs éléments.

def tri_fusion(tab):

    if len(tab) <= 1:

        return tab

    milieu = len(tab) // 2

    gauche = tri_fusion(tab[:milieu])

    droite = tri_fusion(tab[milieu:])

    return fusion(gauche, droite)

1. Donner le résultat de fusion([1, 4, 7], [2, 3, 9]).

2. Écrire la fonction fusion(l1, l2), sans utiliser de fonction de tri prédéfinie.

3. Représenter les découpages successifs effectués par tri_fusion([6, 2, 9, 4, 1, 7, 3, 8]). Donner le nombre de niveaux de découpage jusqu'aux listes de longueur 1.

4. Pour une liste de longueur $n = 1\,024$, donner le nombre de niveaux de découpage, puis l'ordre de grandeur $n \log_2 n$ du nombre total d'opérations élémentaires (comparaisons) effectuées lors des fusions.

Un automate de rendu de monnaie dispose de pièces de valeurs 1, 3 et 4 (en centimes d'euro), en quantité illimitée. On cherche à rendre une somme s avec un nombre minimal de pièces.

On considère l'algorithme glouton suivant.

def rendu_glouton(s, pieces):

    #pieces est triée par ordre décroissant

    nb = 0

    for p in pieces:

        nb = nb + s // p

        s = s % p

    return nb

1. Donner la valeur de rendu_glouton(6, [4, 3, 1]). Montrer que ce résultat n'est pas optimal.

2. On note $m(s)$ le nombre minimal de pièces nécessaires pour rendre la somme $s$. On a $m(0) = 0$ et, pour $s \geqslant 1$, $m(s) = 1 + \min m(s - p)$, le minimum étant pris sur les pièces $p$ telles que $p \leqslant s$. Calculer $m(s)$ pour $s$ allant de 0 à 6.

3. Écrire une fonction rendu_dyn(s, pieces) qui renvoie le nombre minimal de pièces en construisant une liste m telle que m[i] contienne $m(i)$ pour $0 \leqslant i \leqslant s$.

4. Expliquer en quoi cette méthode relève de la programmation dynamique.

On suppose qu'il existe une fonction arrete(f, x) qui prend en paramètres une fonction Python f et une donnée x, et qui renvoie True si l'appel f(x) se termine, et False s'il ne se termine jamais. On suppose que arrete se termine toujours.

On définit la fonction suivante.

def paradoxe(f):

    if arrete(f, f):

        while True:

            pass

    else:

        return 0

1. Expliquer ce que fait paradoxe(f) lorsque arrete(f, f) vaut True, puis lorsqu'elle vaut False.

2. On considère l'appel paradoxe(paradoxe).

   a) Supposer que arrete(paradoxe, paradoxe) renvoie True et aboutir à une contradiction.

   b) Supposer que arrete(paradoxe, paradoxe) renvoie False et aboutir à une contradiction.

3. En déduire que la fonction arrete ne peut pas exister. Énoncer le résultat de décidabilité ainsi établi.

4. Expliquer en quoi cette démonstration utilise le fait qu'un programme peut être donné en argument d'un autre programme.

Le problème des tours de Hanoï consiste à déplacer $n$ disques de tailles différentes d'une tige de départ vers une tige d'arrivée, en utilisant une tige auxiliaire. On déplace un seul disque à la fois et on ne pose jamais un disque sur un disque plus petit. Les disques sont initialement empilés par taille décroissante sur la tige de départ.

def hanoi(n, dep, arr, aux):

    if n > 0:

        hanoi(n - 1, dep, aux, arr)

        print(dep, "->", arr)

        hanoi(n - 1, aux, arr, dep)

1. Donner les affichages successifs produits par l'appel hanoi(2, "A", "C", "B").

2. On note $h(n)$ le nombre de déplacements de disques effectués par hanoi(n, ...). Justifier que $h(0) = 0$ et que $h(n) = 2\,h(n-1) + 1$ pour $n \geqslant 1$.

3. Montrer par récurrence que $h(n) = 2^n - 1$ pour tout entier $n \geqslant 0$.

4. Calculer $h(3)$ et $h(10)$.

5. Un affichage prend 1 ms. Calculer, en secondes, la durée nécessaire pour $n = 20$ disques, puis la comparer à la durée nécessaire pour $n = 10$. Conclure sur la croissance du coût de cet algorithme.