DS 2 — Autour de la décomposition de Zeckendorf¶
MPSI option informatique, année scolaire 2021-2022 — durée totale 2h.
Consignes
Tout document et dispositif électronique interdit.
I. Nombres de Fibonacci¶
On rappelle la définition de la suite de Fibonacci \((F_n)_{n \ge 0}\) :
Question 1. Écrire une fonction fibonacci : int -> int telle que l'appel
fibonacci n renvoie la valeur de \(F_n\).
Cette fonction ne devra pas être récursive mais elle devra utiliser des boucles et des références.
Corrigé
let fibonacci n =
let f = ref 0 in
let f' = ref 1 in
for i = 1 to n do
let t = !f' in
f' := !f + !f';
f := t
done;
!f
Question 2. Justifier la correction de cette fonction.
Corrigé
On a l'invariant de boucle \(I(i) := f = F_{i-1} \wedge f' = F_{i}\).
On suppose, comme on l'a fait en classe, que la valeur de \(i\) change en fin
d'itération (équivalent à un while).
- Initialisation : au départ, on suppose \(i = 1\) et on a bien \(f = F_0= 0\) et \(f' = 1 = F_1\).
- Hérédité : si \(I(i)\) est vérifié au début d'une itération, on a en fin d'itération \(f = F_i\) et \(f' = F_{i-1} + F_i = F_{i+1}\). On a donc bien \(I(i+1)\) en sortie d'itération.
En sortie de boucle, on a donc \(I(n+1)\) et ainsi \(f = F_n\).
Question 3. Déterminer la complexité de cette fonction en fonction de \(n\).
Corrigé
Cette fonction effectue \(n\) itérations effectuant un nombre constant d'opérations, elle est donc en \(O(n)\).
Question 4. Écrire une fonction sous_fibonacci : int -> int telle que
sous_fibonacci n renvoie l'unique \(F_p\) tel que
Corrigé
Rien n'était demandé sur la complexité, mais il semble préférable de repartir de la question précédente :
let sous_fibonacci n =
let f = ref 0 in
let f' = ref 1 in
while !f' <= n do
let t = !f' in
f' := !f + !f';
f := t
done;
!f
II. Arbres de Fibonacci¶
On considère le type Caml suivant pour représenter des arbres binaires stricts :
type arbre =
| Feuille
| Noeud of arbre * arbre
Question 5. Écrire une fonction nb_feuilles : arbre -> int qui renvoie le
nombre de feuilles d'un arbre.
Corrigé
let rec nb_feuilles a =
match a with
| Feuille -> 1
| Noeud (g, d) -> nb_feuilles g + nb_feuilles d
On définit les arbres de Fibonacci \((A_n)_{n\in\N}\) de la manière récursive suivante :
- \(A_0\) et \(A_1\) sont des feuilles ;
- si \(n \ge 2\), \(A_n\) est un nœud comportant \(A_{n-1}\) comme fils gauche et \(A_{n-2}\) comme fils droit.
Question 6. Dessiner les arbres \(A_2\), \(A_3\), \(A_4\) et \(A_5\).
Corrigé
Les nœuds sont représentés par des disques et les feuilles par des carrés.
Question 7. Écrire en Caml une fonction arbre_fibonacci : int -> arbre
telle que l'appel arbre_fibonacci n renvoie l'arbre \(A_n\).
Corrigé
let rec arbre_fibonacci n =
if n <= 1
then Feuille
else Noeud (arbre_fibonacci (n-1), arbre_fibonacci (n-2))
Question 8. Montrer que la complexité de cette fonction est en \(O(2^n)\).
On pourra remarquer qu'en dehors des appels récursifs tout se fait en temps constant et chercher à majorer le nombre d'appels récursifs.
Corrigé
On procède comme l'explication et on note \(C_n\) le nombre d'appels récursifs pour calculer le \(n\)-ième arbre. On a \(C_0 = C_1 = 0\) et \(C_n = 2 + C_{n-1} + C_{n-2}\).
Comme l'appel pour \(n\) nécessite de résoudre l'appel pour \(n-1\), on a nécessairement \(C_n\) croissante et \(C_n \le 2 (1 + C_{n-1})\) donc \(C_n + 2 \le 2 (C_{n-1} + 2)\) et par une récurrence rapide \(C_n + 2 \le 2^n\) donc \(C_n \le 2^n - 2 = O(2^n)\).
Question 9. Quelle est, pour \(n \in \N\), la hauteur de l'arbre \(A_n\) ? Justifier rigoureusement.
Corrigé
On a \(h(A_0) = h(A_1) = 0\) et pour \(n \ge 2\), \(h(A_n) = 1 + \max (h(A_{n-1}), h(A_{n-2}))\). On en déduit que \(h(A_n)\) est croissante et donc que \(h(A_n) = 1 + h(A_{n-1})\) d'où \(h(A_n) = n-1\) pour \(n \ge 1\).
Question 10. Exprimer le nombre de feuilles de \(A_n\) à l'aide des nombres de la suite de Fibonacci \((F_n)_{n\in\N}\).
Corrigé
De même si \(f(A)\) est le nombre de feuilles de \(A\), on a \(f(A_0) = f(A_1) = 1\) et \(f(A_n) = f(A_{n-1}) + f(A_{n-2})\). Donc \(f(A_n) = F_{n+1}\) : mêmes deux premières valeurs et même récurrence.
Question 11. Exprimer le nombre de nœuds de \(A_n\) à l'aide des nombres de la suite de Fibonacci \((F_n)_{n\in\N}\).
Corrigé
On note \(N(A)\) le nombre de nœuds de \(A\).
On a \(N(A_0) = N(A_1) = 0\) et \(N(A_n) = 1+ N(A_{n-1}) + N(A_{n-2})\).
En posant \(u_n = N(A_n) + 1\), on a pour \(n \ge 2\), \(u_n = u_{n-1} + u_{n-2}\) et \(u_0 = u_1 = 1\). Donc \(u_n = F_{n+1}\) et \(N(A_n) = F_{n+1} - 1\).
Question 12. Montrer que les arbres de Fibonacci sont équilibrés : en tout nœud de l'arbre les hauteurs des sous-arbres gauche et droit diffèrent au plus de 1.
Corrigé
C'est une conséquence directe du calcul de \(h(A_n) = n-1\) et de la définition.
Question 13. Écrire en Caml une fonction arbre_fibonacci_bis : int -> arbre
de complexité \(O(n)\). Comment est-il possible d'avoir une fonction de
complexité linéaire en \(n\) qui crée un arbre de taille exponentielle en \(n\) ?
Corrigé
let arbre_fibonacci_bis n =
let f = ref Feuille in
let f' = ref Feuille in
for i = 1 to n do
let t = !f' in
f' := Noeud (!f', !f);
f := t
done;
!f
En fait, quand on écrit Noeud (!f', !f) on ne copie pas les arbres, on
se contente d'y faire référence. En mémoire, les valeurs ne sont pas
dupliquées.
III. Décomposition de Zeckendorf¶
Pour \(n \in \N^*\), on appelle décomposition de Zeckendorf de \(n\) une décomposition de \(n\) comme somme de termes distincts de la suite de Fibonacci d'indices supérieurs ou égaux à 2, de manière à ce qu'il n'y ait pas deux termes d'indices consécutifs dans la somme.
Théorème (Zeckendorf - 1972)
Soit \(n \in \N^*\), il existe une unique suite \(c_0, c_1, \dots, c_{k-1} \in \N \setminus \{0, 1\}\) vérifiant \(\forall i \in \range{0}{k-2}, c_{i+1} > c_i + 1\) telle que \(n =\sum_{i=0}^{k-1} F_{c_i}\).
Par exemple, \(2 + 5 = F_3 + F_5\) est une décomposition de Zeckendorf de 7, avec \(c_0 = 3\) et \(c_1 = 5\). En revanche, \(3 + 5 = F_4 + F_5\) n'est pas une décomposition de Zeckendorf de 8 car \(F_4\) et \(F_5\) sont deux termes consécutifs de la suite de Fibonacci.
Question 14. Déterminer une décomposition de Zeckendorf de 20, 21 et 22.
Corrigé
Les premiers termes de Fibonacci sont \(F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, F_7 = 13, F_8 = 21\) donc \(20 = 13 + 5 + 2 = F_7 + F_5 + F_3\), \(21 = F_8\) et \(22 = 21 + 1 = F_8 + F_2\).
Question 15. Montrer qu'il n'y a pas unicité de la décomposition si l'on autorise des indices de termes consécutifs.
Corrigé
On a \(8 = F_6 = F_4 + F_5\).
On considère le programme myst suivant.
let myst n res =
let i = ref 0 in
let j = ref n in
while !j > 0 do
let f = sous_fibonacci !j in
res.(!i) <- f;
j := !j - f;
i := !i + 1
done;
!i
Question 16. On suppose que tab est un tableau d'entiers de taille
suffisante. Décrire précisément ce que renvoie myst 17 tab et ce que contient
le tableau tab après l'appel.
Corrigé
On a les valeurs suivantes (au début de chaque itération, puis en sortie) :
| j | i | f |
|---|---|---|
| 17 | 0 | 13 |
| 4 | 1 | 3 |
| 1 | 2 | 1 |
| 0 | 3 |
L'appel renvoie donc 3 et on a placé [|13;3;1|] en préfixe de tab.
Question 17. Justifier très très soigneusement que ce programme termine.
Corrigé
\(j\) est un variant, en effet, comme on boucle, on a \(j > 0\) et donc il existe \(1 \le F_p \le j\) ainsi \(j \leftarrow j - F_p\) va faire diminuer \(j\) strictement à chaque itération.
Question 18. Expliquer rapidement ce que calcule ce programme en détaillant le rôle des paramètres et de la valeur de retour. On ne demande pas de le justifier précisément ni de trouver un invariant.
Corrigé
Cette fonction va donc décomposer \(n\) de manière gloutonne en prenant à chaque fois le plus grand \(F_p \le n\). \(j\) est la valeur courante à décomposer, \(i\) est le compteur du nombre de termes de la décomposition courante, \(f\) est le plus grand \(F_p \le j\).
La valeur de retour est donc le nombre de termes de la décomposition.
IV. Codage de Fibonacci¶
On appelle codage de Fibonacci d'un entier \(n \in \N^*\) un tableau code,
composé de 0 et de 1, indiquant par des 1 les indices des termes de la suite de
Fibonacci utilisés dans la décomposition de Zeckendorf de \(n\). Par exemple
code.(2) indique si \(F_2\) est utilisé dans la décomposition de Zeckendorf de
\(n\) ou non et [|0; 0; 0; 1; 0; 1|] est le codage de Fibonacci de 7. Pour avoir
un seul tableau codage pour la décomposition d'un entier, on impose que la
dernière valeur du tableau soit toujours un 1.
On remarque que par définition de la décomposition de Zeckendorf, code ne peut
contenir deux 1 consécutifs et commence toujours par deux 0.
Question 19. Écrire une fonction est_code : int -> int array -> bool telle
que l'appel est_code n tab pour un tableau tab, de taille \(n\ge 0\), composé
de 0 et de 1, renvoie true si le tableau tab est un codage de Fibonacci d'un
entier strictement positif et false sinon.
Corrigé
Un codage a au moins 3 cases (deux 0 initiaux et un 1 final) :
let est_code n tab =
if n < 3 then false
else begin
let valide = ref (tab.(0) = 0 && tab.(1) = 0 && tab.(n-1) = 1) in
for i = 2 to n-2 do
if tab.(i) = 1 && tab.(i+1) = 1
then valide := false
done;
!valide
end
On remarque que si code est un codage de Fibonacci, de taille \(k \ge 3\), alors
c'est le codage de Fibonacci de l'entier \(n= \sum_{i=0}^{k-1}\) code.(i)
\(\times F_i\).
On propose le programme suivant, qui suppose que le tableau code de taille \(k\)
est un codage de Fibonacci d'un nombre strictement positif et que fib est un
tableau de taille \(k\) contenant les \(k\) premiers entiers de la suite de
Fibonacci : pour tout \(m \in \range{0}{k-1}\), fib.(m) \(= F_m\).
let decode k code fib =
let j = ref 2 in
let n = ref 0 in
while !j < k do
n := !n + code.(!j) * fib.(!j);
j := !j + 1
done;
!n
Question 20. Expliquer simplement, en une phrase, ce que fait ce programme.
Corrigé
Il calcule la somme \(\sum_{i=0}^{k-1}\) code.(i) \(\times F_i\).
Question 21. En exhibant un variant de boucle, que l'on justifiera rapidement, montrer que ce programme termine.
Corrigé
Le variant est \(k - j\) qui diminue strictement car \(j\) s'incrémente mais \(k\) est fixe.
Question 22. Montrer très soigneusement que « \(j \le k\) et
\(n = \sum_{i=0}^{j-1}\) code.(i) \(\times F_i\) » est un invariant de boucle pour
la boucle while de ce programme.
Corrigé
On note \(I(j, n) := j \le k \text{ et } n = \sum_{i=0}^{j-1} \mathtt{code}_i \times F_i\)
où \(\mathtt{code}_i\) désigne code.(i).
- Initialisation : on a \(I(2,0)\) car \(0 = 0 \times F_0 + 0 \times F_1\).
- Si \(I(j,n)\) est vérifié en début d'itération, on a également \(I(j+1,n+\mathtt{code}_j \times F_j)\) en fin d'itération vu que \(j < k\) donc \(j+1 \le k\) et \(n + \mathtt{code}_j \times F_j = \sum_{i=0}^{j-1} \mathtt{code}_i \times F_i + \mathtt{code}_j \times F_j = \sum_{i=0}^{j} \mathtt{code}_i \times F_i\).
Question 23. Montrer la correction de ce programme.
Corrigé
Le programme termine et en sortie de boucle, on a \(j = k\) donc comme \(I(k,n)\) est vérifié, c'est que \(n = \sum_{i=0}^{k-1} \mathtt{code}_i \times F_i\).