DS 2 (MPSI option 2021-2022) — Fibonacci et décomposition de Zeckendorf¶
Devoir surveillé · MPSI (option informatique) · 2021-2022 · parties I, III et IV du DS 2 (2 h au total)
Cours : Terminaison · Correction
Autres parties : II. Arbres de Fibonacci
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
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\).