Catégorie : Représentation de données

Fibonnacci et Zeckendorf

Exercice On considère la suite de Fibonnacci définie par :\[F(0) = 0 \text{ et } F(1) = 1\]\[\forall n \in \mathbb{N}, F(n+2) = F(n+1) + F(n)\] Étudions quelques algorithmes de calcul de cette suite. $1.a)$ Écrire un algorithme récursif prenant en entrée un entier $n$ et retournant $F(n)$. $b)$ Donner une borne inférieure et une […]

Exponentiation rapide et algorithme de Hörner

Le but de cet exercice est de calculer des puissances et d’évaluer des polynômes en utilisant le moins de multiplications possible. En effet, si on considère généralement que multiplier deux entiers est une opération élémentaire s’effectuant en $O(1)$, cette considération n’est plus possible lorsqu’on considère la multiplication d’entiers très grand, ou encore la multiplication de […]

Codage de Gray

Exercice Le but du codage de Gray est de représenter les entiers de telle sorte qu’un seul bit soit modifié à chaque incrémentation. Pour $n$ un entier strictement positif, on définit la fonction $\Gamma_n$ de $\{\;0,\;\ldots,\;2^{n}-1\;\}$ dans $\{\;0,\;1\;\}^{n}$, qui à un entier associe son codage de Gray sur $n$ bits. On définit de même la […]