Représentation maximale de Zeckendorf
Représentation minimale de Zeckendorf
À un entier positif n, on peut associer plusieurs tableaux de bits qui indiquent les nombres de Fibonacci présents dans une représentation de Zeckendorf de n.
Exemple de représentation minimale : \(100 = 3 + 8 + 89\)
# 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]
La représentation de Zeckendorf de \(100\) est \(3+8+89\), ou sous forme de tableau de bits [0, 0, 1, 0, 1, 0, 0, 0, 0, 1]
- La liste ne peut pas se terminer avec un
0 - La liste ne contient pas deux
1consécutifs.
On dit que c'est la représentation minimale de Zeckendorf. Il n'y en a pas d'autre avec moins de termes.
Représentation maximale de Zeckendorf
On peut démontrer que pour un entier \(n\), il existe une unique représentation de Zeckendorf, comme somme de nombres de Fibonacci distincts, mais avec une liste de bits qui a comme contraintes :
- La liste ne peut pas se terminer avec un
0 - La liste ne contient pas deux
0consécutifs.
On dit alors que c'est la représentation maximale de Zeckendorf. Il n'y en a pas d'autre avec plus de termes.
- Exemple
- La représentation maximale de Zeckendorf de \(100\) est : \(1 + 2 + 3 + 5 + 13 + 21 + 55\)
# Nombres de Fibonacci 1 2 3 5 8 13 21 34 55 89 (144 ...
assert zeckendorf_eval([1, 1, 1, 1, 0, 1, 1, 0, 1]) == 1 + 2 + 3 + 5 + 13 + 21 + 55 == 100
# n = 100
assert zeckendorf_max([0, 0, 1, 0, 1, 0, 0, 0, 0, 1]) == [1, 1, 1, 1, 0, 1, 1, 0, 1]
Exercice
Coder une fonction zeckendorf_max qui prend en paramètre une liste bits, une représentation quelconque de Zeckendorf et qui renvoie sa représentation maximale.
Les fonctions zeckendorf_eval et zeckendorf sont disponibles.
- Contraintes
-
- la longueur de la liste
bitsest inférieure à \(10^4\) - Fonction récursive interdite
- Modules
mathetfunctoolsinterdits - Code source limité à 2000 caractères
- la longueur de la liste
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)