1 Bases de la programmation

1.1 Structures conditionnelles

Rappeler quelles sont les structures conditionnelles et expliquer leur utilité.
Expliquer dans quelles circonstances il est préférable d’utiliser une structure en if plutôt qu’une structure en switch. Donner des exemples pour illustrer le propos.
Rappeler comment fonctionne l’opérateur conditionnel ternaire C?X:Y et énoncer sa principale différence vis-à-vis des structures conditionnelles.

1.2 Structures de boucle

Rappeler quelles sont les structures de boucle et expliquer leur utilité.
Expliquer dans quelles circonstances il est préférable d’utiliser une boucle for plutôt qu’une boucle while et réciproquement. Donner des exemples pour illustrer le propos.

1.3 Portée lexicale

Rappeler ce qu’est un bloc.
Rappeler ce qu’est la portée lexicale d’une variable.

Déterminer la portée lexicale de chaque variable déclarée dans les suite d’instructions ci-dessous.

{
    int a, b, c;

    a = 10;
    c = 8;
    {
        char c;
        c = 'a';
    }
    {
        int c;
        c = 16;
    }
    a += 1;
    b = 5;
}

int x;
{
    int y;
    float z;
    printf("%d", x);
    {
        float x;
        x = 3.4;
    }
    {
        char y;
        y = 'F';
    }
}

int a, b;

 a = 0;
 {
     int a;
     float b;
     a = 3;
     {
         b = 10;
         {
             int b;
             b = 3;
             a += 1;
         }
     }
 }

1.4 Conversions

Convertir en binaire les valeurs suivantes exprimées en base dix. Les résultats sont à donner sur $16$ bits.
1. $0$
2. $1$
3. $10$
4. $2224$
5. $3200$
6. $- 0$
7. $- 1$
8. $- 10$
9. $- 16$
10. $- 32$
11. $- 2224$
12. $- 3200$
Convertir en hexadécimal les valeurs suivantes exprimées en base deux. Les résultats sont à donner sur huit chiffres hexadécimaux.
1. 0011101010000001
2. 1
3. 11111111001001011111
4. 00010000
Convertir en binaire les valeurs suivantes exprimées en hexadécimal. Les résultats sont à donner sur $16$ bits.
1. 1010
2. ABC
3. F0B
4. 123A

1.5 Suite de Syracuse

La suite de Syracuse est une suite $\left( s_{i}^{(n)} \right)_{i \geq 0}$ d’entiers dépendant d’un paramètre $n$ définie de la manière suivante : $s_{i}^{(n)} := \left\{\begin{array}{ll} n & \text{ si }i = 0 \\ \frac{1}{2}s_{i - 1}^{(n)} & \text{ si }s_{i - 1}^{(n)}\text{ est pair} \\ 3s_{i - 1}^{(n)} + 1 & \text{ sinon } \end{array} \right.$ Par exemple, la suite de Syracuse avec $n = 12$ comme paramètre commence par $s_{0}^{(12)} = 12,6,3,10,5,16,8,4,2,1,s_{10}^{(12)} = 4,2,1,4,2,1.$

Une conjecture célèbre énonce que pour tout entier $n \geq 1$ , il existe un entier $i \geq 0$ tel que $S_{i} = 1$ . Le statut de cette assertion demeure encore inconnu aujourd’hui (2020).

Écrire un programme qui demande à l’utilisateur d’entrer au clavier un entier n et qui affiche les éléments de la suite $\left( s_{i}^{(n)} \right)_{i \geq 0}$ et s’arrête dès qu’un terme est égal à $1$ .
Expliquer si le programme précédent est un algorithme.

2 Expressions et effets secondaires

2.1 Instructions à effets secondaires

Rappeler ce qu’est une expression à effet secondaire.

Déterminer si les instructions suivantes sont à effet secondaire :

```
2 + (8 * 2);
```
```
printf("Bonjour\n");
```
```
int a;
```
```
int a = 2;
```
```
a = 2 + (8 * 2);
```
```
a == 2 + (8 * 2);
```
```
a * 2 + (8 * 2);
```
```
if (a == 17) {a;}
```
```
if (--a == 16) {a;}
```
```
a++;
```
```
a + 1;
```
```
while (1) a + 1;
```
```
while (1) a += 1;
```
```
return 1;
```
```
return a;
```
```
return a + 1;
```
```
p = malloc(64);
```
```
malloc(64);
```

2.2 Fonctions à effets secondaires

Rappeler ce qu’est une fonction à effet secondaire.

Déterminer si les fonctions suivantes sont à effet secondaire :

int addition_1(int a, int b) {
     return a + b;
 }

int addition_2(int a, int b) {
     int res;
     res = a + b;
     return res;
 }

void addition_3(int a, int b,
         int *res) {
     *res = a + b;
 }

int somme(int *tab, int n) {
     int i, res;
     res = 0;
     for (i = 0; i < n; i++)
         res += tab[i];
     return res;
 }

void afficher(int *tab, int n) {
     int i;
     for (i = 0; i < n; i++)
         printf("%d ", tab[i]);
 }

void echanger(int *x, int *y) {
     int tmp;
     tmp = *x;
     *x = *y;
     *y = tmp;
 }

int nb_appels = 0;
 int fct_1(int n) {
     nb_appels++;
     return n + 1;
 }

int nb_appels = 0;
 int fct_2(int n) {
     if (nb_appels == 0)
         return 0;
     else
         return n + 1;
 }

int remplacer(char *tab, char a, char c) {
     int i, nb;
     nb = 0;
     i = 0;
     while (tab[i] != '\0') {
         if (tab[i] == a) {
             tab[i] = c;
             nb += 1;
         }
         i += 1;
     }
     return nb;
}

3 Fonctions et pile d’appel

3.1 Déclaration de fonctions

Identifier et donner les différentes parties (identificateur, signature, type de retour, instructions) de la fonction suivante :
```
float aire(int a, int b) {
     return (.0 + a * b) / 2;
 }
```
Déclarer une fonction testant la primalité d’un entier.
Déclarer une fonction paramétrée par une chaîne de caractères et deux caractères. Cette fonction remplace les occurrences du 1 caractère par le 2 dans la chaîne de caractères.
Déclarer une fonction qui joue une note dans le terminal. La fonction accepte comme arguments la fréquence en Hz de la note à jouer ainsi que sa durée en ms.

3.2 Programme douteux

#include <stdio.h>

int etrange(int *n, int m) {
    *n += m;
    return *n + 1;
}

int main() {
    int n;
    n = 0;
    n = etrange(&n, etrange(&n, 10));
    printf("%d\n", n);
    return 0;
}

Expliquer ce qu’affiche le programme ci-contre et en quoi il n’est pas recommandable.

Indication : tenter de suivre l’exécution du programme pas à pas en présentant l’évolution de la valeur de la variable n en fonction du temps.

Donner tous les possibilités d’évolution. Isoler l’instruction qui pose problème et tenter de dégager une règle générale qui fait que toute instruction similaire provoque un problème.

3.3 Pile et fonctions

Schématiser l’état de la pile à chaque instant de l’exécution de l’instruction

afficher(7, 2);

avec les définitions suivantes :

void afficher(int larg, int haut) {
    int i;
    for (i = 1 ; i <= haut ; ++i) {
        afficher_ligne(larg);
        printf("\n");
    }
}

void afficher_ligne(int larg) {
    int i;
    for (i = 1 ; i <= larg ; ++i)
        printf("*");
}

Dessiner l’arbre des appels récursifs puis schématiser l’état de la pile à chaque instant de l’exécution de l’instruction
```
tribo(5);
```
avec la définitions suivante :
```
int tribo(int n) {
    if (n <= 2)
        return n;
    return tribo(n - 1) + tribo(n - 2) + tribo(n - 3);
}
```

Dessiner l’arbre des appels récursifs puis schématiser l’état de la pile à chaque instant de l’exécution de l’instruction

flip(5);

avec les définitions suivantes :

void flip(int n) {
    printf("flip %d\n", n);
    if (n >= 1)
        flop(n - 1);
}
void flop(int n) {
    printf("flop %d\n", n);
    if (n >= 1)
        flip(n - 1);
}

4 Entrées et sorties

4.1 Boucles et affichage de motifs

Écrire, en utilisant judicieusement des boucles for, while ou encore do while, les fonctions suivantes.

```
void afficher_drapeau(int n);
```
qui produit la sortie suivante (donnée ici dans le cas $n = 4$ ) :
```
----
*---
**--
***-
****
```
```
void afficher_damier(int n);
```
qui produit la sortie suivante (donnée ici dans le cas $n = 4$ ) :
```
*-*-
-*-*
*-*-
-*-*
```
```
void afficher_triangle(int n);
```
qui produit la sortie suivante (donnée ici dans le cas $n = 6$ :
```
*
**
***
****
*****
******
```

4.2 Écriture formatée

Écrire un programme Occurrences.c qui accepte en paramètre des entiers en base dix (en nombre arbitraire mais au moins un) et affiche, ligne par ligne pour chaque nombre entré, son nombre d’occurrences de manière justifiée. Par exemple, la commande

./Occurrences 211 2 2 1 211 1 1 1 44 211 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 affiche

211 3 2 16 1 6 44 1

Ceci indique qu’il y a entre autres seize occurrences d’arguments égaux à $2$ . Respecter la mise en page et l’alignement de l’exemple.

4.3 Miroir

Écrire un programme qui lit des chaînes de caractères de longueur au plus $4$ (la chaîne lue est tronquée le cas échéant) et qui les affiche de la plus récente à la plus ancienne une fois la chaîne "fin" saisie. Par exemple, sur l’entrée de

Bien le bonjour camarade ! fin le programme affiche

! cama bonj le Bien

4.4 Fichier de configuration

Écrire un programme qui lit un fichier de configuration (dont le nom est passé en argument au programme) qui renseigne sur une largeur, une hauteur et un caractère au format

largeur=L
hauteur=H
caractere=C

où L et H sont des entiers positifs non nuls, et C est un caractère affichage. Le programme affiche ensuite sur la sortie standard un rectangle à L colonnes et H lignes, fait de caractères C. Si le fichier de configuration n’est pas au bon format, le programme doit afficher un message d’erreur explicite renseignant sur la première erreur rencontrée dans le fichier de configuration.

4.5 Découpage d’un fichier en lignes

Écrire une fonction ficher_vers_lignes qui prend en argument un fichier et renvoie le tableau des lignes du fichier (sans les caractères de fin de ligne \n). Le nombre de zones mémoires allouées simultanément ne doit pas dépendre du nombre de lignes (il peut notamment être de deux à la fin de la fonction).

Représenter schématiquement l’organisation mémoire du tableau de lignes obtenu par votre fonction.

5 Gestion d’erreurs et assertions

5.1 Déclarations et pré-assertions

Pour chaque tâche décrite, proposer une déclaration de fonction y répondant, ainsi qu’une liste de pré-assertions adéquate (éventuellement vide). Il est important de s’interroger sur les entrées de chaque problème ainsi que sur sa (ou ses) sortie(s). Pour obtenir des pré-assertions pertinentes, il est nécessaire de s’interroger sur les entrées qui posent problème.

Le calcul du quotient de deux entiers
le calcul du reste de la division euclidienne de deux entiers $a$ et $b$ , compris entre $0$ et $b - 1$ (Attention : l’opérateur modulo % du C peut renvoyer un reste négatif.)
le calcul du $n^{ieme}$ nombre de Fibonacci
le calcul de l’image en $x$ d’un polynôme du second degré $a_{0} + a_{1}x + a_{2}x^{2}$
l’affichage d’une lettre $a$ minuscule suivie de sa version en majuscule
l’affichage d’un rectangle composé de $n$ lignes et de $m$ colonnes d’étoiles
l’échange des valeurs de deux entiers
le calcul du nombre de cases contenant des entiers positifs dans un tableau
le calcul de la moyenne des valeurs contenues dans un tableau de flottants
le calcul du maximum des valeurs contenues dans un tableau d’entiers
le calcul de la distance d’un point du plan par rapport à l’origine
l’initialisation de chaque case d’un tableau à deux dimensions par une valeur $a$
le calcul du nombre de voyelles dans une chaîne de caractères contenant des chiffres, des espaces ou des lettres
la création d’une chaîne de caractères obtenue en remplaçant toutes les majuscules par des minuscules d’une chaîne de caractères donnée en entrée
la création d’une chaîne de caractères obtenue en remplaçant tout caractère alphabétique $c$ par un caractère alphabétique $c'$ d’une chaîne de caractères donnée en entrée.

5.2 Ajout de mécanismes de gestion d’erreurs

Réécrire les fonctions suivantes de sorte à les munir d’un mécanisme de gestion d’erreurs. Pour chaque nouvelle fonction ainsi écrite, rédiger une documentation appropriée.

void doubler() {
    int entree;
    scanf("%d", &entree);
    printf("%d\n", 2 * entree);
}

void repeter_affichage(char *chaine, int nombre) {
    int i;

    assert(chaine != NULL);
    assert(nombre >= 0);

    for (i = 0 ; i < nombre ; ++i)
        printf("%s\n", chaine);
}

int premiere_position(char *chaine, char lettre) {
    int i;

    assert(chaine != NULL);

    i = 0;
    while (chaine[i] != '\0') {
        if (chaine[i] == lettre)
            return i;
        i += 1;
    }
    return -1;
}

int *allouer_tab_int(int taille) {
    assert(taille >= 1);

    return (int *)
        malloc(sizeof(int) * taille);
}

void copier_pointeur(char *source, char **cible) {
    assert(source != NULL);
    assert(cible != NULL);

    *cible = (char *)
        malloc(sizeof(char));

    **cible = *source;
}

5.3 Écriture de fonctions sûres

Pour chaque fonction ci-dessous, la définir, la munir de pré-assertions, imaginer les cas d’erreur possibles et mettre en place un mécanisme de gestion d’erreurs.

calculer_moyenne paramétrée par un tableau de notes comprises entre 0 et 20, calculant la moyenne des notes
lettre_frequente paramétrée par une chaîne de caractères, calculant sa lettre strictement plus fréquente
dessiner_etoiles paramétrée par un tableau d’entiers et dessinant, pour chaque entier $a$ du tableau lu de la droite vers la gauche, une nouvelle ligne de $a$ occurrences de ’*’ sur la sortie standard
lire_points_isobarycentre qui lit sur l’entrée standard deux points du plan cartésien au format X Y et affiche sur la sortie standard leur isobarycentre.

5.4 Utilisation de fonctions à gestion d’erreurs

Écrire une fonction est_nom paramétrée par une chaîne de caractères qui teste si celle-ci est constituée uniquement de caractères alphabétiques.
Écrire une fonction demander_nom qui lit une chaîne de caractères sur l’entrée standard. Celle-ci doit gérer les erreurs qui peuvent survenir (une chaîne de caractère qui n’est pas un nom est entrée ou bien une erreur provient de la fonction de lecture sur l’entrée standard).
Utiliser la fonction demander_nom dans un programme complet pour demander un nom à un utilisateur et l’afficher sur la sortie standard. Lors de l’exécution, le programme demande un nom tant que l’utilisateur ne rentre pas un nom valide.

5.5 Sécurisation des fonctions précédentes Reprendre

toutes les fonctions écrites dans les exercices précédents et les munir d’un mécanisme de gestion d’erreurs lorsque cela est approprié. On n’oubliera pas de les munir également de pré-assertions adéquates.

6 Modularisation

6.1 Projets et graphes d’inclusions

On considère un projet constitué de cinq modules A, B, C, D et E. Ces modules sont utilisés dans un fichier Main.c qui contient la fonction main. Dans ce projet figurent les inclusions suivantes :

A.h inclut B.h, C.h et E.h
A.c inclut D.h
B.h inclut C.h
D.h inclut A.h
E.c inclut D.h
Main.c inclut A.h et E.h.

Donner le nombre de fichiers qui constituent le projet.
Donner la liste des commandes qui permettent de compiler le projet.
Dire si l’ordre des commandes de compilation est important et justifier pourquoi.
Tracer le graphe d’inclusions (étendues) du projet.
Expliquer, graphe d’inclusions (étendues) à l’appui, si le projet est bien structuré. Mettre en évidence les éventuels problèmes qu’il contient.
Supposons (uniquement pour cette question) que B.h inclut D.h. Expliquer, graphe d’inclusions (étendues) à l’appui, si le projet est bien structuré. Mettre en évidence les éventuels problèmes qu’il contient.
Supposons (uniquement pour cette question) que B.c inclut D.h. Expliquer, graphe d’inclusions (étendues) à l’appui, si le projet est bien structuré. Mettre en évidence les éventuels problèmes qu’il contient.
Supposons (uniquement pour cette question) que B.h inclut D.h. On suppose également que dans l’en-tête du module B est déclaré un type B_type et que dans l’en-tête du module A est déclarée une fonction de prototype void a_fct(B_type x). Expliquer pourquoi la commande gcc -c B.c provoque une erreur. Expliquer pourquoi la commande gcc -c A.c produit bien un fichier objet.
Écrire un Makefile complet pour compiler le projet.

6.2 Découpage d’un projet en modules : le Gomoku

Le but de cet exercice est de réaliser l’analyse d’un petit projet en le découpant en modules et en écrivant ses fichiers d’en-tête. On ne donnera pas l’implantation des modules.

Le projet consiste à réaliser un jeu de Gomoku¹. Une partie se joue à deux joueurs sur un plateau de $19 \times 19$ cases. À chaque tour de jeu, le joueur qui a le trait (Blanc ou Noir) choisit une case du plateau de jeu et y pose un pion de sa couleur. Le premier joueur qui réussit à aligner $5$ pions de sa couleur gagne la partie. Si le plateau est rempli de pions sans aucune configuration de gain, la partie est déclarée nulle. Le joueur Noir commence toujours la partie.

Au lancement du programme, il est de possible de :

commencer une nouvelle partie
charger une partie depuis un fichier
quitter le programme.

Au cours de la partie, il est possible de :

jouer un coup (par le joueur qui possède le trait)
abandonner la partie et céder ainsi la victoire à son adversaire
sauvegarder la partie en cours (sans quitter le programme, la partie continue)
quitter la partie en cours et revenir au menu de lancement du programme.

Lorsque la partie s’arrête (gain d’un joueur ou partie nulle), le résultat est affiché, suivi du menu de lancement du programme.

Les parties sont sauvegardées dans un fichier selon un format choisi par le programmeur. Ce format doit permettre de représenter toutes les informations d’une partie pour que, à partir d’un fichier de sauvegarde, le programme puisse entièrement restaurer la partie qu’il représente. De plus, l’interaction avec les utilisateurs se fait par le biais de l’entrée et de la sortie standard.

Découper ce projet en modules. Ce découpage doit permettre de le faire facilement évoluer. Expliquer comment prendre en compte les variantes suivantes :
- changement du format des fichiers de sauvegarde
- changement des règles ( $6$ pions alignés pour le gain au lieu de $5$ , taille du plateau $21 \times 21$ au lieu de $19 \times 19$ , trois joueurs au lieu de deux)
- affichage graphique à la place d’un affichage sur la sortie standard
- ajout d’un mode de jeu humain vs machine.
Pour chacune des ces quatre évolutions, expliquer leur impact sur l’ensemble des modules du projet.
Déterminer les types et les prototypes des fonctions que chaque module doit contenir. En déduire les en-têtes des modules du projet.

6.3 Modélisation d’un projet : polynômes

On souhaite réaliser un projet qui permet de manipuler des polynômes sur une variable $x$ et à coefficients flottants (double). Plus précisément, le programme doit pouvoir :

lire un polynôme à partir d’un fichier, calculer sa dérivée par rapport à $x$ et afficher le résultat sur la sortie standard
lire un polynôme à partir d’un fichier, calculer sa $n^{ieme}$ puissance et afficher le résultat sur la sortie standard
lire deux polynômes à partir d’un fichier, calculer leur somme et afficher le résultat sur la sortie standard
lire deux polynômes à partir d’un fichier, calculer leur produit et afficher le résultat sur la sortie standard
lire un polynôme à partir d’un fichier et afficher dans une fenêtre graphique le graphe du polynôme dans un intervalle d’abscisse et d’ordonnée spécifié.

L’utilisateur peut choisir l’une ou l’autre de ces fonctionnalités par le biais d’une option (respectivement -d, -p N, -s, -m, -g). Le dernier paramètre de l’exécutable est le nom du fichier contenant le(s) polynôme(s) à traiter. Dans le cas où l’option -g est choisie, après le nom du fichier figurent les paramètres X_MIN, X_MAX, Y_MIN et Y_MAX qui définissent les dimensions du repère du graphique.

Le format des fichiers contenant les polynômes est spécifié par l’exemple suivant : le polynôme $- 3 + 2.5x^{5} - 4.7x^{11}$ est codé par

-3 + 2.5x^5 - 4.7x^11.

Découper ce projet en modules.
Pour chacun des modules, donner les fichiers d’en-tête au complet (directives du pré-processeur, définitions de types, déclarations de fonctions).
Dessiner le graphe d’inclusions du projet.
Écrire le code de la fonction main du projet.
Écrire un Makefile complet pour compiler le projet.

7 Manipulation de la mémoire

7.1 Opérations sur les pointeurs

Pour chacune des suites d’instructions suivantes, donner ligne par ligne l’état des variables déclarées. Présenter la solution sous forme de tableau et dessiner, étape par étape, l’état de la mémoire.

int a, b;
int *p;

a = 10;
p = &a;
b = *p + 2;
*p = *p + 4;
a = *p;

int a, b;
int *p1, *p2;

a = 3;
p2 = &b;
*p2 = a + 1;
p1 = p2;
*p1 = 5;

int tab[10];
int *p1, *p2;

tab[0] = 4;
tab[3] = 2;
p1 = &tab[0];
tab[1] = *p1;
p2 = p1 + 3;
tab[2] = *p2;

int a, b;
int *p1;
int **p2;

p1 = &a;
p2 = &p1;
**p2 = 3;
*p2 = &b;
*p1 = 4;

7.2 Tableaux statiques

On souhaite manipuler une fonction paramétrée par un entier n qui renvoie un pointeur sur un tableau de n entiers initialisés à 0.

int *creer_tableau(int n) {
    int tab[n];
    int i;

    for (i = 0 ; i < n ; ++i)
        tab[i] = 0;
    return tab;
}

Expliquer pourquoi la fonction ci-contre ne répond pas à cette spécification en donnant deux raisons bien précises. En supposant que cette fonction est acceptée par le compilateur, expliquer aussi ce qu’il se passe lorsqu’elle est appelée (faire des dessins de mémoire).

7.3 Tableaux dynamiques à une dimension

Écrire une fonction creer_tab paramétrée par un entier n et qui renvoie un pointeur sur un tableau de n entiers initialisés à 0.
Écrire une fonction detruire_tab paramétrée par un pointeur tab sur un tableau d’entiers et qui libère la place mémoire occupée par tab.

7.4 Tableaux dynamiques à deux dimensions

Écrire une fonction creer_tab_2d paramétrée par des entiers n et m et qui renvoie un pointeur sur un tableau à deux dimensions de n $\times$ m entiers initialisés à 0.
Écrire une fonction detruire_tab_2d paramétrée par un entier n et un pointeur tab sur un tableau à deux dimensions de n $\times$ m entiers (il n’est pas nécessaire de connaître m ici). Cette fonction doit libérer la place mémoire occupée par tab.
Dessiner l’état de la mémoire étape par étape et de manière très précise lors de l’exécution des instructions
```
int **tab = creer_tab_2d(2, 3);
detruire_tab_2d(tab, 2);
```
Expliquer comment représenter et gérer un tableau à deux dimensions par un tableau à une seule dimension.

7.5 Tableaux dynamiques en dents de scie

Écrire une fonction creer_scie paramétrée par un entier n et qui renvoie un pointeur sur un tableau à deux dimensions de caractères. Pour tout $0 \leq i \leq n - 1$ , la $i^{\text{eme}}$ case du tableau à construire contient un tableau à une dimension de $i$ modulo $5$ plus un caractères ’*’.
Écrire une fonction detruire_scie paramétrée par un entier n et un pointeur scie sur un tableau à deux dimensions de caractères (pouvant être construit par un appel à creer_scie). Cette fonction doit libérer la place mémoire occupée par scie.

7.6 Variables simples en mémoire

Rappeler la différence entre la convention little-endian et la convention big-endian pour l’écriture des données dans la mémoire.

Pour chaque déclaration et affectation de variable suivante, dessiner la zone de la mémoire impliquée ainsi que son contenu octet par octet.

```
unsigned int x;
x = 0;
```
```
char x;
x = 'a';
```
```
int x;
x = 2224;
```
```
int x;
x = -2224;
```
```
short x;
x = -10;
```
```
unsigned short x;
x = -10;
```
```
int *ptr;
ptr = NULL;
```
```
char tab[4] = {21, -1, 'a', 99};
```
```
unsigned char tab[2] = {-1, 1};
```
```
int tab[3] = {21, -1, 'a', 120};
```

int tab[3][2];
tab[0][0] = 1;
tab[0][1] = 10;
tab[1][0] = 100;
tab[1][1] = 1000;
tab[2][0] = 10000;
tab[2][1] = 100000;

7.7 Lecture de zones mémoire

Soit la suite d’instructions suivante :

unsigned int *ptr_int;
unsigned short *ptr_short;
unsigned char *ptr_char;
unsigned int a;
a = 0xBEA0201F;

Expliquer ce qu’affichent les instructions

```
ptr_int = &a;
printf("%x\n", *ptr_int);
```

ptr_short = (unsigned short *) &a;
printf("%x\n", *ptr_short);

ptr_char = (unsigned char *) &a;
printf("%x\n", *ptr_char);

ptr_short = (unsigned short *) &a;
printf("%x\n", *(ptr_short + 1));

ptr_char = (unsigned char *) &a;
printf("%x\n", *(ptr_char + 1));

ptr_char = (unsigned char *) &a;
printf("%x\n", *(ptr_char + 2));

Reprendre la question précédente dans le cas où l’on supprime les quatre occurrences de unsigned dans la suite d’instructions.

7.8 Lecture de zones mémoire et tableaux

Soit la suite d’instructions suivante :

unsigned char tab[8] = {0xAA, 0x10, 0x3B, 0x44, 0x21, 0x45, 0x00, 0x7C};
unsigned char *ptr_char;
unsigned short *ptr_short;
unsigned int *ptr_int;

Expliquer ce qu’affichent les instructions

ptr_char = tab;
printf("%x\n", *ptr_char);

ptr_short = (unsigned short *) tab;
printf("%x\n", *ptr_short);

ptr_int = (unsigned int *) tab;
printf("%x\n", *ptr_int);

ptr_short = (unsigned short *) tab;
printf("%x\n", *(ptr_short + 1));

ptr_char = tab;
printf("%x\n", *(ptr_char + 1));

ptr_char = tab;
printf("%x\n", *(ptr_char + 2));

Reprendre la question précédente dans le cas où l’on supprime les quatre occurrences de unsigned dans la suite d’instructions.

7.9 Tableau à deux dimensions avec une allocation

On présente dans le cours une méthode pour allouer un tableau à deux dimensions de taille M x N en M + 1 allocations : une pour le tableau des M pointeurs, puis une par tableau de taille N.

Une seconde méthode consiste à ne faire que deux allocations : une pour le tableau de M pointeurs et une pour les M x N éléments. Un calcul permet ensuite de faire pointer chaque pointeur vers une portion de N éléments dans le tableau de M x N éléments.

Représenter graphiquement l’organisation de la mémoire pour ces deux méthodes.
En remarquant que la seconde méthode consiste à regrouper les M allocations de tableaux à N éléments en une allocation d’un tableau à M x N élément, proposer une méthode pour réduire le nombre d’allocations à une seule allocation pour les pointeurs et la donnée. Donner une représentation graphique puis un code réalisant cette solution.

7.10 Constructeur de chaine de caractère

On propose ici de coder un type utilitaire pour construire facilement des chaines de caractères par accumulation. Ce type utilisera un tableau dynamique pour gérer sa mémoire.

// Constructeur de chaine de caractère
typedef struct {
    char *cars;   // Pointeur vers la zone mémoire
    int capacite; // Taille de la zone mémoire
    int longueur; // Nombre de caractères stockés
} ChaineConstructeur;

// TODO...

int main(void) {
    ChaineConstructeur cc = {0};
    cc_ajouter_chaine(&cc, "Hello");
    cc_ajouter_caractere(&cc, ' ');
    cc_ajouter_caracteres(&cc, "World!!!", 6);

    char *str = cc_vers_chaine(&cc);
    printf("%s\n", str); // Hello World!
    str[1] = 'a';
    printf("%s\n", str); // Hallo World!

    char *extract = cc_extraire_chaine(&cc);
    printf("%s\n", extract); // Hello World!

    cc_ajouter_chaine(&cc, "Pwet!");
    printf("%.*s", cc.longueur, cc.cars); // Pwet!
    cc_detruire(&cc);

    free(str);
    free(extract);
}

Implémenter et tester les fonctions suivantes.

// Ajoute à la fin du constructeur `taille` caractères depuis `cars`
int cc_ajouter_caracteres(ChaineConstructeur *cc, char *cars, int taille);

En utilisant la fonction cc_ajouter_caracteres

// Ajoute un caractère à la fin du constructeur
int cc_ajouter_caractere(ChaineConstructeur *cc, char c);

En utilisant la fonction cc_ajouter_caracteres

// Ajoute une chaine de caractère à la fin du constructeur (sans son caractère `\0`)
int cc_ajouter_chaine(ChaineConstructeur *cc, char str[]);

// Renvoie une nouvelle chaine de caractère de contenu celui du constructeur
char *cc_vers_chaine(const ChaineConstructeur *cc);

// Extrait du constructeur la chaine qui s'y trouve, le constructeur est mis à zero
char *cc_extraire_chaine(ChaineConstructeur *cc);

// Libére la zone mémoire du constructeur et le met à zero.
void cc_detruire(ChaineConstructeur *cc);

7.11 Vue sur les chaines de caractère

En C, une chaine de caractères est une convention, une suite d’octet se terminant par le caractère nul. On propose la structure suivante pour représenter une vue sur une chaine.

typedef struct {
    const char *cars; // Adresse du premier caractère de la chaine
    int longueur;     // Taille de la chaine
} ChaineVue;

int cv_print(ChaineVue cv) {
    // Format printf pour ne pas dépendre du caractère nul
    return printf("%.*s", cv.longueur, cv.cars);
}

Note: L’attribut cars est un pointeur vers un const char. On indique ainsi qu’une vue ne modifiera pas le contenu de la chaine d’origine.

Une vue est la donnée de l’adresse du premier caractère d’une chaine et de sa taille. Contrairement à une chaine de caractères usuelle, on ne se repose pas sur la présence du caractère nul pour délimiter la fin de la chaine mais sur une taille. Cela permet alors simplement de construire une vue sur une sous-chaine : il suffit de calculer l’adresse du premier caractère de cette sous-chaine et d’avoir sa taille.

Écrire la fonction ChaineVue cv_nouveau(char *str) qui renvoie une vue sur une chaine de caractère.
Comment représenter une vue vide ?
Écrire la fonction ChaineVue cv_sous_vue(ChaineVue cv, int debut, int longueur) qui renvoie une vue vers la sous-chaine de longueur longueur commençant à l’indice debut

En notant que la chaine de caractère pointé par s est dans la zone statique, représenter l’organisation de la mémoire du programme suivant :

int main(void) {
    char *s = "Hello World!";
    // Vue sur la chaine complete
    ChaineVue tout = cv_nouveau(s);
    // VUe sur "Hello"
    ChaineVue hello = cv_sous_vue(tout, 0, 5);
    // Vue sur "World"
    ChaineVue world = cv_sous_vue(tout, 6, 5);
}

On ajoute au programme l’instruction
```
ChaineVue meh = cv_sous_vue(hello, 3, 5);
```
Intégrer cette nouvelle variable au schéma précédent. Que représente la variable meh ? Commenter.
Écrire la fonction PaireVue cv_couper(ChaineVue cv, char c) qui renvoie la paire de vues obtenue par le découpage de cv en deux à la première occurrence de c. Par exemple, couper la vue "Hello World" au premier ' ' produit la paire ("Hello", "World") Si le caractère n’est pas présent, couper(vue, c) produit (vue, "").

Note : il faut définir au préalable le type PaireVue.
Écrire une boucle parcourant une chaine de caractère ligne par ligne en utilisant les fonctions précédentes.

8 Pointeurs de fonctions

8.1 Déclarations de pointeurs de fonctions

Déclarer un pointeur f_1 sur une fonction paramétrée par deux entiers et qui renvoie un caractère.
Déclarer un pointeur f_2 sur une fonction paramétrée par une chaîne de caractères et un flottant et qui renvoie un pointeur sur un entier.
Déclarer un pointeur f_3 sur une fonction paramétrée par un caractère et un pointeur sur une fonction de même prototype que celle de f_1 et qui renvoie une chaîne de caractères.
Déclarer un pointeur f_4 sur une fonction paramétrée par deux caractères et qui renvoie un pointeur sur une fonction de même prototype que celle de f_2.
Déclarer un pointeur f_5 sur une fonction paramétrée par une fonction de même prototype que celle de f_2 et qui renvoie un pointeur sur une fonction de même prototype que celle de f_1.
Déclarer un tableau statique tab_f_1 de 32 pointeurs de fonctions de mêmes signatures que celle de f_1.

8.2 Pointeurs de fonction et tableaux

Écrire une fonction fois_deux qui renvoie le double de son argument entier.
Écrire une fonction fact qui renvoie la factorielle de son argument entier.
Écrire une fonction
```
void appliquer_tableau(int (*f)(int), int *tab, int n);
```
qui modifie chaque élément du tableau tab de taille n en son image par la fonction pointée par f.
En supposant que tab est un tableau d’entiers de taille 128, écrire une suite d’instructions qui modifie chaque élément du tableau en le double de sa factorielle. On suppose que les valeurs du tableau sont telles que chaque calcul peut se faire sans dépassement de capacité.
Nous voulons maintenant modifier chaque élément d’un tableau tab d’entiers de sorte à remplacer chaque entrée tab[i] par son image par une fonction f_i. Pour cela, écrire une fonction
```
void appliquer_tableau_2(int (*tab_f[])(int), int *tab, int n);
```
paramétrée par un tableau tab_f de n fonctions et un tableau d’entiers tab de taille n.

8.3 Pointeurs de fonction et tris

Considérons les deux fonctions suivantes :

void tri_croissant(int *tab, int n) {
    int i, i_min, j, tmp;
    for (i = 0 ; i < n - 1 ; i++) {
        i_min = i;
        for (j = i ; j < n ; j++) {
            if (tab[j] < tab[i_min])
                i_min = j;
        }
        tmp = tab[i_min];
        tab[i_min] = tab[i];
        tab[i] = tmp;
    }
}

void tri_decroissant(int *tab, int n) {
    int i, i_max, j, tmp;
    for (i = 0 ; i < n - 1 ; i++) {
        i_max = i;
        for (j = i ; j < n ; j++) {
            if (tab[j] > tab[i_max])
                i_max = j;
        }
        tmp = tab[i_max];
        tab[i_max] = tab[i];
        tab[i] = tmp;
    }
}

L’une trie les éléments d’un tableau tab de taille n dans l’ordre croissant et l’autre, dans l’ordre décroissant.

Ces deux fonctions sont identiques, à l’exception de l’opérateur de comparaison en ligne 6 et de certains noms pour les variables locales. L’utilisation de pointeurs de fonctions permet d’éviter cette redondance de code et d’avoir ainsi une unique fonction qui réalise, selon la manière dont elle est appelée, l’un ou l’autre tri.

Écrire une fonction
```
int superieur(int a, int b);
```
qui renvoie 1 si a est strictement supérieur à b, 0 s’ils sont égaux et -1 sinon.
Écrire une fonction
```
int inferieur(int a, int b);
```
qui renvoie 1 si a est strictement inférieur à b, 0 s’ils sont égaux et -1 sinon.
Écrire une fonction tri, paramétrée par un tableau d’entiers tab, sa taille n et une fonction comparer. Cette fonction modifie tab de sorte à le trier selon la comparaison dictée par la fonction comparer. Plus précisément, si a et b sont des éléments de tab et que a apparaît dans tab à gauche de b, il faut que la fonction comparer appelée avec les arguments a et b renvoie -1 (ou 0 pour les répétitions d’éléments).
En supposant que tab est un tableau d’entiers de taille 2047, écrire une suite d’instructions qui trie tab dans l’ordre croissant, affiche ses valeurs, trie tab dans l’ordre décroissant et affiche ses valeurs.

9 Généricité

9.1 Pointeurs et données génériques

Un pointeur générique est un pointeur de type void *. Une donnée générique est une variable adressée par un pointeur générique.

On suppose que a est une variable de type int. Définir un pointeur générique ptr qui adresse a.
Multiplier par trois la valeur de a en opérant uniquement sur ptr.
On suppose maintenant que ptr est un pointeur générique et que l’on dispose d’un type
```
typedef struct {
    int x;
    int y;
} Couple;
```
et d’une variable b de ce type. Faire pointer ptr vers b.
Incrémenter le champ y de b en opérant uniquement sur ptr.
Écrire une fonction
```
void *twist(void *couple);
```
qui travaille avec des pointeurs génériques voués à être des données de type Couple. Cette fonction renvoie un nouveau couple obtenu en permutant les champs x et y du couple en argument.
En supposant que c est une variable de type Couple, écrire une suite d’instructions appelant la fonction précédente sur c.

9.2 Test d’égalité de zones de la mémoire

Écrire une fonction qui permet de tester l’égalité entre deux variables d’un type quelconque. La fonction admet le prototype
```
int sont_egales(int nb_octets, void *var1, void *var2);
```
et elle renvoie 1 si les nb_octets lus à partir des adresses var1 et var2 sont égaux deux à deux et 0 sinon.
On suppose que num1 et num2 sont deux variables de type short. Écrire l’appel à la fonction sont_egales pour comparer les valeurs de ces variables.

On suppose que res est une variable de type int. Pour chacune des suites d’instructions suivantes, expliquer la valeur de res à la fin de leur exécution.

int a;
char b;

a = 3;
b = 3;
res = sont_egales(1, &a, &b);

int a;
int b;

a = (1 << 8) + 32;
b = 32;
res = sont_egales(1, &a, &b);

int a;
int b;

a = (1 << 8) + 32;
b = 32;
res = sont_egales(2, &a, &b);

int a;
int b;

a = 0xAE00BBAA;
b = 0xEA00BBAA;
res = sont_egales(3, &a, &b);

Expliquer comment utiliser la fonction sont_egales pour tester si deux variables d’un type structuré T quelconque sont égales. Expliquer ce qu’il se passe si certains champs de T sont des pointeurs.

9.3 Tableaux génériques

Un tableau générique est une variable de type void *, interprétée comme une concaténation d’octets formant, bloc par bloc, les cases du tableau. Pour manipuler une telle donnée, il est nécessaire de connaître la taille du tableau (nombre de cases) ainsi que le nombre d’octets nécessaires pour représenter un élément du tableau (nombre d’octets par bloc).

Calculer le nombre d’octets nécessaires pour représenter un tableau générique de taille $24$ voué à contenir des valeurs occupant chacune $8$ octets.
Représenter graphiquement un tableau générique de taille $4$ voué à contenir des valeurs occupant chacune $2$ octets.
Représenter graphiquement un tableau générique de taille $2$ voué à contenir des valeurs occupant chacune $4$ octets.
Supposons que tab est un tableau générique. Supposons de plus que tab est utilisé pour contenir des données de type short. Donner trois manières d’accéder à la $4^{ieme}$ donnée du tableau.
Répondre à la même question que la précédente dans le cas où tab est utilisé pour contenir des int.

9.4 Minimum générique dans un tableau

L’objectif de cette exercice est d’écrire une fonction générique qui calcule la plus petite valeur contenue dans un tableau générique.

Déterminer la signature d’une fonction qui prend deux données génériques en argument et qui renvoie la plus petite des deux. En faire un type.
Écrire une telle fonction générique qui calcule la plus petite valeur entre deux entiers.
Écrire une telle fonction générique qui calcule la plus petite valeur entre deux chaînes de caractères (il est conseillé d’utiliser la fonction strcmp de string.h).
Déterminer la signature de la fonction min_tab qui répond à l’objectif de l’exercice. Elle est paramétrée, entre autres, par un tableau générique et une fonction de calcul de la plus petite valeur entre deux valeurs données.
Donner le corps de la fonction min_tab.
En supposant que tab est un tableau d’entiers de taille 64, écrire une suite d’instructions qui calcule et affiche sa plus petite valeur, en utilisant min_tab.
En supposant que tab est un tableau de 64 chaînes de caractères et toutes de taille 96, écrire une suite d’instructions qui calcule et affiche sa plus petite valeur, en utilisant min_tab.

10 Macro-instructions

10.1 Macro-instructions à paramètres erronées

Voici un code C utilisant une macro de debug. Le code ne compile compile pas quand la macro est utilisée (option 2). Déterminer la raison et proposer une correction.

#include <stdio.h>

// Option 1: Pas de message de debug
#define DEBUG(s) /* rien */

// Option 2: Messages de debug activés
#define DEBUG(s) fprintf(stderr, "%d: %s\n", __LINE__, s);

void division(int x, int y) {
    if (y == 0)
        DEBUG("Valeur inattendue, y ne doit pas être nul");
    else
        printf("x / y = %d\n", x, y, x / y);
}

Qu’affiche ce programme ? Compiler avec gcc et clang et analyser le résultat produit. Comment peut-on l’expliquer ?²

#include <stdio.h>

#define DOUBLE(x) ((x) + (x))

int main(void) {
    int x = 1;
    int y = DOUBLE(x++);
    int z = DOUBLE(++x);
    printf("%d %d %d\n", x, y, z);
}

11 Débogage

11.1 Macro-instruction de debug

Proposer un unique message de debug à placer avec la macro DEBUG_LOG dans le code suivant pour aider à déceler l’erreur.

#include <stdio.h>

#define DEBUG_LOG(fmt, ...)                                           \
    fprintf(stderr, "%s:%d:%s(): " fmt, __FILE__, __LINE__, __func__, \
            __VA_ARGS__)

// Renvoie 1 si la valeur `v` est dans le tableau `tab` de taille `size`
int dichotomie(int v, int *tab, int size) {
    // premier indice valide
    int i = 0;
    // dernier indice valide
    int j = size - 1;
    while (i < j) {
        // Milieu
        int mid = (i + j) / 2;
        if (tab[mid] == v)
            return 1;
        if (tab[mid] < v) {
            // si à droite, on met à jour i en excluant mid
            i = mid + 1;
        } else {
            // si à gauche, on met à jour j en excluant mid
            j = mid - 1;
        }
    }
    return 0;
}

int main() {
    int tab[] = {0, 2, 4, 6, 8};
    for (int i = 0; i < 5; i++) {
        if (!dichotomie(tab[i], tab, 5)) {
            printf("La valeur %d à l'indice %i est introuvable...\n", tab[i], i);
        }
    }
    return 0;
}

En réalité, il s’agit ici d’une variante du Gomoku.↩︎
une piste de recherche peut se trouver dans les avertissements↩︎