Modélisation en binaire d'une représentation
⏰ : une série de trois exercices utiles et très simples à faire en quelques minutes.
Représentations de Zeckendorf
À un entier positif n
, on peut associer un tableau de bits qui indique si le nombre de Fibonacci est présent dans la somme issue du théorème de Zeckendorf.
Exemple :
# Nombres de Fibonacci 1 2 3 5 8 13 21 34 55 89 (144 ...
assert zeckendorf_repr(100) == [0, 0, 1, 0, 1, 0, 0, 0, 0, 1]
Cette représentation de Zeckendorf de
- ou sous forme de tableau de bits
[0, 0, 1, 0, 1, 0, 0, 0, 0, 1]
Il en existe d'autres, comme
- ou sous forme de tableau de bits
[1, 1, 0, 0, 1, 0, 0, 1, 1]
Le cadre
On souhaite compresser une représentation sous la forme d'un unique entier dont la représentation binaire est le tableau de bits
renversée.
- Exemples
-
- le tableau
[0, 0, 1, 0, 1, 0, 0, 0, 0, 1]
correspond à l'entier'0b1000010100'
qui vaut - le tableau
[1, 1, 0, 0, 1, 0, 0, 1, 1]
correspond à l'entier'0b110010011'
qui vaut
- le tableau
L'objectif étant d'obtenir un représentant immuable compressé pour chaque représentation. Le choix du binaire est naturel.
On souhaite également la fonction réciproque.
On souhaite aussi une fonction qui renvoie une chaine de caractères associée à une représentation de Zeckendorf.
- Exemples
-
# Nb Fib 1 2 3 5 8 13 21 34 55 89 ...
tableau = [0, 0, 1, 0, 1, 0, 0, 0, 0, 1]
correspond à la chaine"3 + 8 + 89"
tableau = [1, 1, 0, 0, 1, 0, 0, 1, 1]
correspond à la chaine"1 + 2 + 8 + 34 + 55"
Exercice 1
Coder une fonction zeckendorf_bin
qui prend en paramètre un tableau de bits
et qui renvoie l'entier dont l'écriture binaire correspond au tableau renversé.
- Contraintes
-
- La longueur de la liste
bits
est inférieure à . - Fonction récursive interdite
- Modules
math
etfunctools
interdits - Code source limité à 2000 caractères
- La longueur de la liste
La fonction acceptera les représentations minimale, maximale ou toute autre valide.
Aide
C'est très simple, il n'y a pas à construire les nombres de Fibonacci. Uniquement les puissances de deux.
On peut faire une boucle sans indice et construire la nouvelle puissance_deux
en fonction de la précédente.
Guide
def zeckendorf_bin(bits):
"""
Renvoie l'entier en binaire associé à
la représentation de Zeckendorf donnée avec le tableau bits
"""
somme = ...
puissance_deux = ...
for b in bits:
if ...:
somme = ...
puissance_deux = ...
return somme
Exercice 2
Coder une fonction zeckendorf_list
qui prend en paramètre un entier positif n
et qui renvoie un tableau de bits
dont le renversement correspond à l'entier n
écrit en binaire.
- Contraintes
-
- Fonction récursive interdite
- Modules
math
etfunctools
interdits - Code source limité à 2000 caractères
Exemple : '0b10100'
la liste de bits attendus est donc [0, 0, 1, 0, 1]
Sinon, on attend que zeckendorf_bin(zeckendorf_list(n)) == n
pour tout entier n
, puisqu'il s'agit de la fonction réciproque.
Aide
Il suffit de faire une boucle Tant que,
- de récupérer le bit de poids faible avec
n % 2
- de décaler tous les autres dans le nombre
n
, en le divisant par deux.
Guide
def zeckendorf_list(n):
"""
Renvoie la liste de bits associée à l'entier n
"""
bits = ...
while ...:
bits.append(...)
n = ...
return ...
# Tests
(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
Exercice 3
Coder une fonction zeckendorf_txt
qui prend un tableau de bits
en paramètre et qui renvoie la chaine de caractères associée à la représentation de Zeckendorf décrite avec bits
.
- Exemples
-
# Fibonacci 1 2 3 5 8 13 21 34 55 89 ...
assert zeckendorf_txt([0, 0, 1, 0, 1, 0, 0, 0, 0, 1]) == "3 + 8 + 89"
assert zeckendorf_txt([1, 1, 0, 0, 1, 0, 0, 1, 1]) == "1 + 2 + 8 + 34 + 55"
- Contraintes
-
- La longueur de la liste
bits
est inférieure à . - Fonction récursive interdite
- Modules
math
etfunctools
interdits - Code source limité à 2000 caractères
- La longueur de la liste
La fonction acceptera les représentations minimale, maximale ou toute autre valide.
Aide
- On construit le nombres de Fibonacci tout en faisant un parcours sur les bits
- Si le bit est marqué, on ajoute
' + '
à lachaine
puis le nombre en texte.Si c'est le
premier
nombre ajouté,- on ne place pas le
' + '
- un booléen
premier
permet de marquer cet état qui change.
- on ne place pas le
Guide
def zeckendorf_txt(bits):
"""
Renvoie la chaine de caractères associée à
la représentation de Zeckendorf donnée avec le tableau bits
"""
a, b = ..., ... # Fib(i) et Fib(i + 1)
chaine = ...
premier = True
for bit in bits:
if ...:
if premier:
...
else:
chaine = ...
chaine = ...
a, b = b, a + b
return chaine
# Tests
(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
# Tests
(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)