Générer dans l'ordre du code de Gray

Fonctions récursives · niveau 3 (difficile)

Énoncé

Écrire la fonction gray(n) qui engendre par réflexion les $2^{n}$ mots binaires de longueur $n$ 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.

Énoncé

Corrigé

Exercices semblables