Générer dans l'ordre du code de Gray
Exercice · informatique (tronc commun des prépas scientifiques), chapitre 6 — Fonctions récursives
Énoncé
Écrire la fonction gray(n) qui engendre par réflexion les mots binaires de longueur de telle sorte que deux mots consécutifs ne diffèrent que d'un unique bit.
Corrigé
def gray(n: int) -> list:
if n == 0:
return [""]
g = gray(n - 1)
return ["0" + m for m in g] + ["1" + m for m in reversed(g)]Preuve de correction : Par récurrence. Les mots de la première moitié (commençant par 0) et ceux de la seconde moitié (commençant par 1) diffèrent au plus d'un bit consécutivement par hypothèse de récurrence sur gray(n-1). Au point de bascule entre les deux parties, le dernier mot de la première moitié est 0 + m (où m est le dernier mot de gray(n-1)) et le premier mot de la seconde moitié est 1 + m (puisque la liste est inversée). Ces deux mots ne diffèrent que par leur premier bit (0 vs 1), la transition est donc valide.
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.