Représentation maximale de Zeckendorf (Performance)
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 (performance)
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_repr sont disponibles pour les petits tests, mais impraticables avec les nouvelles contraintes. À ne pas utiliser dans le code !
- Contraintes
-
- La longueur de la liste
bitsest inférieure à \(10^6\) - Fonction récursive interdite
- Modules
mathetfunctoolsinterdits - Code source limité à 2000 caractères
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)