Langage C - TP 6: Récursivité et Manipulation de bits

1. Récursivité simple

Exercice 1.1.

Ecrire un programme tp6-ex11.c contenant une fonction récursive int factorielle(int n) qui calcule la valeur de la factorielle du nombre n. Le programme doit
contenir également une fonction main qui permet de faire saisir à l’utilisateur une valeur et d’afficher sa factorielle.

Exemple d'exécution

Entrer un nombre: 8
8! = 40320

Exercice 1.2.

Ecrire un programme tp6-ex12.c contenant une fonction récursive int somme(int n) qui calcule la somme des nombres entiers de 1 à n (n étant positif). Le programme
doit contenir également une fonction main qui permet de faire saisir à l’utilisateur une valeur et d’afficher la somme souhaitée. Si n n'est pas strictement positif, la fonction somme retourne 0.

Exemple d'exécution

Entrer un nombre: 6
somme(6) = 21

Entrer un nombre: -1
somme(-1) = 0

Exercice 1.3.

La suite de Fibonacci est une suite de nombres $u_{n}, n\geq{}0$ définie telle que:

$$
\left\{
\begin{array}{l}
u_{0} = 0 \\
u_{1} = 1 \\
u_{n} = u_{n-1}\ +\ u_{n-2},\ n > 1
\end{array}
\right.
$$

Ecrire un programme tp6-ex13.c contenant une fonction récursive int fibonacci(int n) qui calcule la valeur de la suite de Fibonacci au rang n. sous la forme:

u_O, u₁, ..., u_n

Le programme doit contenir également une fonction main qui permet de faire saisir à l’utilisateur une valeur et d’afficher la suite jusqu’au rang souhaité.

Exemple d'exécution

Entrer un nombre: 5
0, 1, 1, 2, 3, 5

Exercice 1.4.

Ecrire un programme tp6-ex14.c contenant une fonction récursive int digits(int n) qui affiche le nombre de chiffres formant le nombre n. Le programme doit contenir également une fonction main qui permet de faire saisir à l’utilisateur un nombre et d’afficher le nombre de chiffres le composant.

Exemple d'exécution

Entrer un nombre: 123
Le nombre possede 3 chiffres.

Entrer un nombre: 0
Le nombre possede 1 chiffre.

Exercice 1.5.

Ecrire un programme tp6-ex15.c contenant une fonction récursive int pgcd(unsigned int n, unsigned int m) qui calcule le plus grand commun diviseur (PGCD) des nombres n et m. Le programme doit contenir également une fonction main qui permet de faire saisir à l’utilisateur deux nombres positifs et d’afficher leur PGCD.

Exemple d'exécution

Entrer un premier nombre: 27
Entrer un second nombre: 63
Le PGCD de 27 et 63 est 9

Entrer un premier nombre: 0
Entrer un second nombre: 12
Le PGCD de 0 et 12 est 12

2. Conjecture de Syracuse

Soit la fonction $f: \mathbb{N}\rightarrow{}\mathbb{N}$ définie telle que:

\[
f(x)\ =\ \left\{
\begin{array}{l}
\cfrac{x}{2},\ si\ x\ est\ pair \\
3x\ +\ 1,\ si\ x\ est\ impair
\end{array}
\right.
\]

On appelle cette fonction la fonction de Collatz. Celle-ci a pour particularité que pour tout $x$, le calcul de $f(x)$ puis $f(f(x))$, puis $f(f(f(x)))$ finit toujours par valoir 1 à partir d’un certain nombre d’appels récursifs (nombre de fois où l’on a appliqué $f$).

La fonction de Collatz permet de construire une suite définie par récurrence à partir d’un nombre $x$ telle que:

\[
\begin{array}{l}
u_{0}\ =\ x \\
\cdots{} \\
u_{n}\ =\ f(u_{n-1}),\ n>0
\end{array}
\]

La conjecture de Syracuse est qu’il existe un nombre $n\in\mathbb{N}$ pour lequel la suite un finit par atteindre la valeur $1$ et qu’une fois cette valeur atteinte, la suite devient alors périodique de période $4,\ 2,\ 1$. On dit alors que la suite est entrée dans un puit.

Par exemple, pour $x\ =\ 15$, la suite est:

Les mathématiciens parlent de la trajectoire de $n$ pour désigner cette suite et ils définissent également le temps de vol (le nombre de termes avant le premier $1$, ici $17$) et d’altitude maximale pour la valeur maximale prise par la suite (ici $160$).

Une conjecture étant une hypothèse non démontrée, son acceptation peut provenir de l’expérience et de sa vérification sur un grand nombre de cas. Cette partie est dédiée à la mise en place de fonctions permettant de vérifier la conjecture de Syracuse pour des valeurs de $x$ diverses.

Exercice 2.1.

Ecrire un programme tp6-syracuse.c contenant une fonction int collatz(unsigned int x) qui calcule la valeur de la fonction de Collatz $f(x)$ pour un $x$ donné. Le programme doit contenir également une fonction main qui permet de faire saisir à l’utilisateur une valeur $x$ et d’afficher $f(x)$.

Exemple d'exécution

Entrer x: 15
collatz(15) = 46

Entrer x: 46
collatz(46) = 23

Entrer x: 0
collatz(0) = 0

Exercice 2.2.

Dans le programme tp6-syracuse.c ajouter une fonction récursive void syracuse(unsigned int x) qui affiche les termes de la suite un jusqu’au premier 1 rencontré pour la valeur x. Modifier ensuite la fonction main afin de saisir un nombre et d’afficher les termes de la suite jusqu’au premier 1.

Exemple d'exécution

Entrer x: 15
collatz(15) = 46
Syracuse: 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1

Exercice 2.3.

Dans le programme tp6-syracuse.c ajouter une fonction récursive int temps_de_vol(unsigned int x) qui renvoie l’index du premier terme de la suite un pour lequel $u_{n}\ =\ 1$. Modifier la fonction main afin d’afficher le temps de vol de la valeur saisie précédemment.

Exemple d'exécution

Entrer x: 15
collatz(15) = 46
Syracuse: 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1

Temps de vol: 17

Exercice 2.4.

Dans le programme tp6-syracuse.c ajouter une fonction récursive int altitude(unsigned int x) qui renvoie l’altitude de x. Modifier la fonction main afin d’afficher l’altitude de la valeur saisie précédemment.
RAPPEL : L’altitude de x est la valeur maximale des termes de la suite un créée à partir de x.

Exemple d'exécution

Entrer x: 15
collatz(15) = 46
Syracuse: 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1

Temps de vol: 17
Altitude: 160

Entrer x: 36
collatz(36) = 18
Syracuse: 36 18 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Temps de vol: 21
Altitude: 52

3. Manipulations de bits

Le langage C permet de manipuler directement des bits composants les valeurs de ses types entiers (char, short, int, long).

Exercice 3.1.

Créer le le programme tp6-bits.c et ajouter une fonction void print_uchar(unsigned char c) qui affiche sur la sortie standard le nombre c sous forme de vecteur de bits. Le bit de poids faible étant affiché à droite, le bit de poids fort à gauche. Créer une fonction main qui demande à l'utilisateur de saisir un nombre de type unsigned char et affiche sa représentation binaire.

ATTENTION: Afin de saisir un nombre de type unsigned char, la sequence "%hhu" doit être utilisée dans le scanf correspondant.

Exemple d'exécution

Saisir un nombre entre 0 et 255: 0
0 s'ecrit en binaire: 00000000

Saisir un nombre entre 0 et 255: 255
255 s'ecrit en binaire: 11111111

Saisir un nombre entre 0 et 255: 1
1 s'ecrit en binaire: 00000001

Saisir un nombre entre 0 et 255: 128
128 s'ecrit en binaire: 10000000

Saisir un nombre entre 0 et 255: 145
145 s'ecrit en binaire: 10010001

Saisir un nombre entre 0 et 255: 3
3 s'ecrit en binaire: 00000011

En informatique, plusieurs opérations sont possibles sur les vecteurs de bits pour faciliter la représentation de nombres. Parmi ces transformations, le complément à 2 est l'une des plus utilisées. Pour calculer le complément à 2 d'un nombre quelconque il suffit d'appliquer les étapes suivantes:

Représenter le nombre voulu sous sa forme de vecteur binaire
Inverser chaque bit du vecteur binaire tel que chaque 0 devient 1 et chaque 1 devient 0 (complément à 1)
Ajouter 1 au vecteur binaire inversé (sans conserver le dépassement s'il y en a)

Le vecteur binaire obtenu est alors le complément à 2 du vecteur original et par extension le nombre correspondant au nouveau vecteur binaire est appelé complément à 2 du nombre original.

Exercice 3.2.

Dans le le programme tp6-bits.c, ajouter une fonction unsigned char comp2_uchar(unsigned char c) qui calcule et retourne le complément à 2 de la valeur passée en paramètre. Modifier la fonction main pour saisir un nombre et afficher sa représentation binaire et son complément à 2.

Exemple d'exécution

Saisir un nombre entre 0 et 255: 0
0 : 00000000
Comp2(0) : 00000000

Saisir un nombre entre 0 et 255: 255
255 : 11111111
Comp2(255) : 00000001

Saisir un nombre entre 0 et 255: 3
3 : 00000011
Comp2(3) : 11111101

Exercice 3.3.

Dans le le programme tp6-bits.c, remplacer la fonction main de la façon suivante:

int main(){
    
    unsigned char c;
    char comp2;
    
    printf("Saisir un nombre entre 0 et 255: ");
    scanf("%hhu", &c);
    
    printf("%d        : ", c);
    print_uchar(c);
    printf("\n");
    
    comp2 = comp2_uchar(c);
    printf("Comp2(%d) : ", c);
    print_uchar(comp2);
    printf(" = %d\n", comp2);
    
    return 0;
}

Exécuter le programme et le tester avec les valeurs 0, 12, 25, 36, 127. Que pouvez-vous en déduire sur la façon dont le langage C représente les entiers ?

Exercice 3.4.

Dans le le programme tp6-bits.c, ajouter une fonction unsigned char extract(unsigned char val, unsigned char begin, unsigned char end) qui retourne la valeur composée des bits extraits de val entre l'index begin et l'index end (tous deux inclusifs), comme le montre le schéma suivant:

Modifier la fonction main pour demander à l'utilisateur une valeur, un index de début, un index de fin et afficher la valeur extraite entre les indexes.

Exemple d'exécution

Saisir un nombre entre 0 et 255: 139
Saisir un bit de depart (0...7): 0
Saisir un bit de fin: (0...7): 7
139 : 11010001
139[0...7] : 11010001

Saisir un nombre entre 0 et 255: 139
Saisir un bit de depart (0...7): 1
Saisir un bit de fin: (1...7): 3
139 : 11010001
139[1...3] : 10100000

Saisir un nombre entre 0 et 255: 139
Saisir un bit de depart (0...7): 3
Saisir un bit de fin: (3...7): 7
139 : 11010001
139[3...7] : 10001000

Tout nombre entier en Langage C peut être utilisé comme un vecteur binaire de taille fixe. Une information importante que l'on peut extraire d'un vecteur binaire est le nombre de ses bits à 1. Cette valeur, appelée poids binaire, notée $p$, se calcule par:

\[
\forall{}a\in{}\mathbb{F}_{2}^{n},\ a\ =\ (a_{i}),\ 1\leq{}i\leq{}n,\ p(a)\ =\ \sum_{i=1}^{n}a_{i}
\]

Exercice 3.5.

Dans le le programme tp6-bits.c, ajouter une fonction unsigned char poids(unsigned char a) qui calcule le poids du vecteur binaire a. Modifier la fonction main afin de saisir un nombre entier représentant un vecteur binaire, d'afficher sa représentation binaire et d'afficher son poids.

Exemple d'exécution

Saisir un nombre entre 0 et 255: 0
p(00000000) = 0

Saisir un nombre entre 0 et 255: 145
p(10010001) = 3

Une opération très utile lors de l'utilisation de vecteurs est de déterminer leurs nombre de composantes différentes. La distance de Hamming est définie en ce sens et se décrit formellement par:

$$
\forall{}a,\ b\in{}F^{n},\ a\ =\ (a_{i}),\ b\ =\ (b_{i}), 1\leq{}i\leq{}n,\ d(a,\ b)\ =\ \#\{i:\ a_{i}\neq{}b_{i}\}
$$

où $F^{n}$ est un ensemble de vecteurs de dimension $n$ et $\#$ est le cardinal.

Dans le cadre de vecteurs de bits, cette distance peut s'écrire:

\[
\forall{}a,\ b\in{}\mathbb{F}_{2}^{n},\ a\ =\ (a_{i}),\ b\ =\ (b_{i}), 1\leq{}i\leq{}n,\ d(a,\ b)\ =\ \sum_{i=1}^{n}a_{i}\oplus{}b_{i}
\]

où $\oplus$ est l'addition binaire.

Exercice 3.6.

Dans le le programme tp6-bits.c, ajouter une fonction unsigned char hamming(unsigned char a, unsigned char b) qui calcule la distance de Hamming entre les deux vecteurs binaires a et b. Modifier la fonction main afin de saisir deux nombres entiers représentant des vecteurs binaires, d'afficher leur représentation binaire et d'afficher la distance de Hamming correspondante.

AIDE: Penser à la façon $\oplus{}$ est calculé sur un vecteur de bits et à l'utilisation de la fonction poids.

Exemple d'exécution

Saisir un nombre a entre 0 et 255: 12
Saisir un nombre b entre 0 et 255: 127
a = 00001100
b = 01111111
d(a, b) = 5

Saisir un nombre a entre 0 et 255: 255
Saisir un nombre b entre 0 et 255: 255
a = 11111111
b = 11111111
d(a, b) = 0

4. Codage RGB8

Une image peut être vue comme un ensemble de pixels ou chaque pixel est défini par :

Sa coordonnée en X
Sa coordonnée en Y
Sa couleur

Le codage couleur le plus répandu est le RGB (Red, Green, Blue), qui représente une couleur comme le mélange d’une nuance rouge, une nuance verte et une nuance bleue. Le codage RGB peut être représenté sur différents nombres de bits. Par exemple, le RGB24 (ou encore format TrueColor) représente chaque nuance des 3 couleurs sur 1 octet (8 bits). Bien que ce format permettent de représenter une large plage de nuances, il oblige à stocker 3 octets pour chaque pixels d'une image, ce qui peut produire des fichiers lourds pour les images en haute résolution. Le format RGB8 à été conçu comme un moyen de représenter les images en utilisant seulement 1 octet par pixel pour stocker une nuance RBG. Pour cela, certains bits de l'octet de nuance sont réservés à certaines couleurs:

Les 3 bits de poids fort pour le rouge
Les 3 bits de poids moyen pour le vert
les 2 bits de poids faible pour le bleu

Le format RGB8 permet d'utiliser 8 nuances de rouge, 8 nuances de vert et 4 nuances de bleu.

Le passage d'un format RGB24 à un format RGB8 est une compression (avec perte d'information) qui repose sur l'échantillonnage d'une nuance sur 8 bits à une nuance codée sur 3 ou 2 bits.

Un échantillonnage est le passage d'une valeur $x$ codée sur $n$ bits vers une valeur $y$ codée sur $m$ bits, avec $m\ <\ n$ et se calcule de la façon suivante:

\[
y\ =\ \cfrac{x\times{}(2^{m}-1)}{2^{n}-1)}
\]

Exercice 4.1.

Créer un fichier tp-couleur.c et y ajouter un fonction unsigned char echantillonne(unsigned char nuance, unsigned char n, unsigned char m) qui retourne le résultat de échantillonne la valeur nuance exprimée sur n bits en une valeur exprimée sur m bits. Ajouter une fonction main qui permet de saisir une valeur de nuance RGB24 (entre 0 et 255) et qui affiche sa valeur echantillonnée en RGB8 ainsi que sa représentation binaire.

AIDE: Il est très rapide de calculer la valeur $2^{n}$ en utilisant le décalage à gauche (<<).

Exemple d'exécution

Saisir une nuance RGB24 [0...255]: 0
Nuance : 0 (00000000)
Echantillon: 0 (00000000)

Saisir une nuance RGB24 [0...255]: 255
Nuance : 255 (11111111)
Echantillon: 7 (00000111)

Saisir une nuance RGB24 [0...255]: 45
Nuance : 45 (00101101)
Echantillon: 1 (00000001)

Saisir une nuance RGB24 [0...255]: 96
Nuance : 96 (01100000)
Echantillon: 2 (00000010)

Exercice 4.2.

Dans le fichier tp6-couleur.c, ajouter une fonction unsigned char encode(unsigned char r, unsigned char g, unsigned char b) qui prends en paramètre 3 nuances de couleurs r, g et b et retourne un entier codant la couleur au format RGB8. Le programme doit contenir également une fonction main qui permet de faire saisir à l’utilisateur une couleur au format RGB et qui affiche l’entier codant cette couleur au format RGB8.

Exemple d'exécution

Entrer une couleur sous forme (r g b): 255 255 255
Couleur saisie (255, 255, 255)
Couleur encodee: 255

Entrer une couleur sous forme (r g b): 0 0 0
Couleur saisie (0, 0, 0)
Couleur encodee: 0

Entrer une couleur sous forme (r g b): 145 28 64
Couleur saisie (145, 28, 64)
Couleur encodee: 96

5. Représentation des flottants

Exercice 5.1.

Ecrire un programme qui permet de demander à l’utilisateur un float et qui affiche sur la console la représentation en binaire de ce flottant.

AIDE : Penser aux union et aux opérations de manipulation de bits.

Exemple d'exécution

Entrer un nombre flottant: -12.5
Binaire: 11000001010010000000000000000000

Langage C