Exercice 4 - Mélange récursif de Fischer-Yates · Bac Numérique et Sciences Informatiques Métropole Candidat libre 2021 (sujet 2)
Thème : Récursivité · Tiré du sujet Métropole Candidat libre 2 (2021)
Énoncé
EXERCICE 4 (4 points)
Cet exercice porte sur la programmation en général et la récursivité en particulier.
On s'intéresse dans cet exercice à un algorithme de mélange des éléments d'une liste.
3. Le mélange de Fischer Yates est un algorithme permettant de permuter aléatoirement les éléments d'une liste. On donne ci-dessous une mise en œuvre récursive de cet algorithme en Python.
from random import randint
def melange(lst, ind):
print(lst)
if ind > 0:
j = randint(0, ind)
echange(lst, ind, j)
melange(lst, ind-1)
a.
Expliquer pourquoi la fonction melange se termine toujours.
b.
Lors de l'appel de la fonction melange, la valeur du paramètre ind doit être égal au plus grand indice possible de la liste lst.
Pour une liste de longueur , quel est le nombre d'appels récursifs de la fonction melange effectués, sans compter l'appel initial ?
c.
On considère le script ci-dessous:
lst = [v for v in range(5)]
melange(lst, 4)
On suppose que les valeurs successivement renvoyées par la fonction randint sont 2, 1, 2 et 0.
Les deux premiers affichages produits par l'instruction print(lst) de la fonction melange sont:
[0, 1, 2, 3, 4]
[0, 1, 4, 3, 2]
Donner les affichages suivants produits par la fonction melange.
d.
Proposer une version itérative du mélange de Fischer Yates.
Corrigé
Corrigé proposé par AprenAI (non officiel)
3.a. Expliquer pourquoi la fonction melange se termine toujours.
Réponse : À chaque appel récursif, le paramètre ind est décrémenté de 1 (appel melange(lst, ind - 1)). Comme ind est initialement un entier positif et qu'il décroît strictement à chaque étape, il finit nécessairement par atteindre 0 (ou une valeur négative), ce qui rend la condition ind > 0 fausse et met fin aux appels récursifs.
3.b. Pour une liste de longueur n, quel est le nombre d'appels récursifs de la fonction melange effectués, sans compter l'appel initial ?
Réponse :
3.c. Troisième affichage produit par l'instruction print(lst)
Réponse : [0, 3, 4, 1, 2]
Les réponses des 3 questions restantes et l’explication pas à pas sont réservées aux membres Premium. Premium
Résous-le ici : correction automatique, indices et corrigé détaillé.
‹ Exercice 5 - Question 4 · Métropole 2 remplacement 2022 · Exercice 2 - Récursivité · Métropole 1 remplacement 2021 ›