Pour coder un entier X :
- Créer un tableau avec 2 lignes.
- Dans la 1re, mettre les éléments de la suite de Fibonacci (1, 2, 3, 5, 8...) inférieurs ou égaux à X.
- Décomposer l'entier X en une somme d'entiers correspondant aux éléments de la 1re ligne du tableau, en employant les plus grands possibles.
- Dans la 2e ligne du tableau, mettre des « 1 » en dessous des éléments qui ont permis de décomposer X, « 0 » sinon.
- Écrire la 2e ligne du tableau en rajoutant un « 1 » pour terminer.
- Exemple
- décomposition de 50.
Les éléments de la 1re ligne du tableau (ou poids) sont : 1 2 3 5 8 13 21 34
50 = 34 + 13 + 3 (50 = 34 + 8 + 5 + 3 est incorrect car le 13 n'a pas été utilisé)
D'où le tableau :
| Suite de Fibonacci | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |
|---|---|---|---|---|---|---|---|---|
| Présence dans la décomposition | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
Il reste à écrire le codage du nombre 50 en ajoutant le terminateur : 001001011
normalisation d'une décomposition exacte non conforme
la décomposition 50 = 21+13+8+5+3, donnerait une représentation brute 00111110 qu'on peut normaliser en considérant que, tout poids étant la somme des deux précédents,
110 = 001 au sein de la représentation.
Donc 001'111'10 = 001'110'01 = 001'001'01, représentation correcte au sens de Zeckendorf.
En ajoutant maintenant le "1" terminateur, on obtient encore 001001011
Aucun commentaire:
Enregistrer un commentaire