Cadre des TP

Utilisation de Repl.it

On va utiliser pour commencer le site https://replit.com.

Pour chaque TP, on commence ainsi par créer un Repl avec le bouton + Create et on sélectionne le langage C (et pas C++, car cela fera vite une différence) :

L'interface est assez simple :

• la colonne de gauche où on peut voir les fichiers édités et en changer (pour le moment on aura juste un seul fichier) et des outils ;
• la colonne centrale où on édite un fichier ;
• la colonne de droite où on a la console dans laquelle s'effectuent les entrées et sorties textuelles et le shell qui fournit une invite de commande dans un répertoire où sont situés les fichiers.

Pour compiler et lancer son programme, on peut appuyer sur le gros bouton vert et on verra l'affichage (et les éventuelles erreurs) dans la console, on peut aussi utiliser le shell pour compiler manuellement avec le compilateur gcc.

La commande est gcc -o nomduprogramme fichier.c. Pour le lancer, on va alors utiliser la commande ./nomduprogramme. On reviendra sur ces notions, mais . signifie le répertoire courant et pour des raisons de sécurité, il faut donner le chemin d'accès à un programme qui n'est pas dans l'emplacement usuel des exécutables.

Remarque

Il est vivement conseillé de compiler avec les options gcc -Wall -Wextra -g -fsanitize=address,undefined -o nomduprogramme fichier.c : les deux premières activent les avertissements du compilateur, les suivantes ajoutent des vérifications à l'exécution qui détectent la plupart des erreurs d'accès mémoire (voir le chapitre Gestion de la mémoire).

Une autre possibilité qui sera très pratique pour vous est d'utiliser le débogueur (debugger) visuel intégré. On y accède en cliquant sur le bouton Debugger de Tools. Il s'ouvre par défaut dans les onglets de l'éditeur.

Ce n'est pas très pratique, je vous recommande de faire glisser l'onglet à côté.

L'avantage du débogueur, c'est qu'on peut mettre des points d'arrêt (breakpoints) où le programme va s'arrêter et attendre quand il atteint ces points.

Pour lancer le débogage, il faut cliquer sur le bouton démarrer de la partie Debugger. Ça prend un peu de temps et on se retrouve sur le premier accès à un point d'arrêt avec l'état complet du programme.

On peut cliquer sur > à droite du bouton démarrer pour avancer d'un pas dans le programme (on dit step en anglais). On va ainsi passer dans les fonctions par les appels et on peut observer le contenu des paramètres.

En l'absence d'interprète, il va être nécessaire de faire des affichages complets pour observer des valeurs. C'est assez fastidieux. C'est là que le débogueur (ou l'observateur mémoire https://pythontutor.com/c.html) va permettre de récupérer la souplesse qu'on connaît en Python ou en OCaml.

Mais ne nous trompons pas : c'est beaucoup plus délicat de programmer ainsi. On va donc aller doucement.

On verra aussi que la mise en place de tests va permettre de vérifier que tout fonctionne sans intervention humaine.

Structure des questions

Les questions du TP vous demandent d'écrire des fonctions. Pour cela, on vous donne leur prototype (aussi appelé une déclaration), c'est-à-dire une ligne de la forme :

typeret nomfonction(typearg1 arg1, ..., typeargn argn);

Par exemple :

int ajoute(int x, int y);

On vous décrit également ce que doit faire votre fonction. À vous de vous assurer qu'elle fonctionne. Avec des tests, des affichages, le débogueur. Savoir vérifier qu'une fonction fait ce qu'on attend est quelque chose qu'on va apprendre progressivement.

Quand vous répondez à la question, vous allez donner une définition de la fonction, c'est-à-dire que la première ligne sera identique au prototype, sans le ; et avec à la place des instructions entre { et }.

TP1 - Introduction au C

Normalement un programme en C est composé d'un fichier .c (le plus souvent plusieurs qui sont réunis) contenant une fonction main qui est le point d'entrée du programme.

Voici un exemple de contenu d'un tel fichier :

// déclaration de fonctions d'impression pour pouvoir les utiliser
#include <stdio.h>

int x = 3; // une variable globale entière x pour tout le programme

// déclaration d'une fonction qui prend deux entiers en entrée et renvoie un entier
int ajoute(int a, int b)
{
    return a+b;
}

// la fonction principale

int main(void)
{
    int a = 2; // déclaration de variables locales
    int b; // non initialisée ici

    b = 3; // nécessite que b soit déclarée.

    printf("La somme de %d + %d = %d\n",
           b, x, ajoute(b, x)); // la fonction principale d'affichage, véritable couteau-suisse
                        // ici %d signifie un entier qui figure dans la liste juste après

    // On retrouve des boucles for
    a = 0;
    for (int i = 0; i < 10; i++) // mais on doit gérer notre compteur nous-même
    {
        a = a + i;
    }
    printf("La somme des entiers de 0 à 9 vaut %d\n", a);

    return 0; // pour main signifie que tout va bien
}

Question 1

Écrire une fonction de prototype :

int multiplie(int a, int b);

qui renvoie le produit de a et de b.

Corrigé

int multiplie(int a, int b)
{
    return a * b;
}

Les bases du C

Types et variables

Mis à part l'ajout des points-virgules à la fin des instructions, la différence principale entre OCaml, Python et C dans ce qu'on vient de voir se situe au niveau des instructions explicites de type et donc de la notion de déclaration de variable.

On a en C des types de base sur lesquels on reviendra dans les exercices : int, float, bool, mais une variable doit être déclarée comme ayant un type donné et, bien qu'on puisse en changer la valeur, on ne pourra pas changer le type des données qu'elle contient.

Pour déclarer une variable x ayant le type t on écrit t x;, par exemple int b; ici. Une fois une variable déclarée, on peut l'utiliser en lecture et en écriture. Mais il faut écrire dedans AVANT d'y lire quoi que ce soit. Pour cela, on pourra écrire x = val; pour que la variable x prenne la valeur val. Il est possible de déclarer et d'initialiser une variable, comme dans int x = val;.

ATTENTION : si on écrit juste int x; sans valeur, on ne peut pas supposer que x contienne une valeur spécifique comme 0. On peut juste dire que x contient un entier quelconque qu'on se gardera bien d'utiliser dans un calcul.

Ainsi, comme OCaml, C est un langage typé statiquement : le type de chaque variable est fixé à la compilation. Mais ici les types sont explicites.

int x; // x n'est pas initialisé mais c'est un entier
float y = 3.2; // y est un flottant initialisé à 3.2
bool b = true; // b est un booléen qui vaut true (nécessite stdbool.h, voir TP2)
char c = 'a'; // le type des caractères

Un type propre à C est le type de rien, qui se nomme void. Cela correspond au type unit de OCaml.

Remarque

Le typage du C est cependant beaucoup moins strict que celui d'OCaml : de nombreuses conversions sont implicites, par exemple int n = 3.7; est accepté et donne n = 3, et 3 / 2 vaut 1 alors que 3 / 2.0 vaut 1.5.

Blocs et portée

En C on a une notion de bloc : ce sont des instructions ou des déclarations de variables entourées d'accolades, comme dans :

{
    int x = 3;
    printf("x vaut %d\n", x);
}

Une variable déclarée dans un bloc n'existe que dans celui-ci. Dès qu'on sort du bloc on ne peut plus y accéder. Les fonctions, les instructions conditionnelles ou les boucles utilisent des blocs.

// exemple avec deux blocs imbriqués où on retrouve la valeur précédente de x
// qui a juste été masquée dans le sous-bloc
{
    int x = 3;
    printf("x vaut %d\n", x);

    {
        int x = 4;
        printf("x vaut %d\n", x);
    }

    printf("x vaut %d\n", x);
}

qui va afficher :

x vaut 3
x vaut 4
x vaut 3

Attention, par contre, le code suivant utilise x dans le bloc pour le changer de valeur et comme c'est le x du bloc principal, ça le modifie :

{
    int x = 3;
    printf("x vaut %d\n", x);

    {
        x = 4;
        printf("x vaut %d\n", x);
    }

    printf("x vaut %d\n", x);
}

x vaut 3
x vaut 4
x vaut 4

Fonctions

Une fonction en C a un type de retour et chacun des arguments est donné avec son type. S'ensuit un bloc d'instructions qui peut comporter une ou plusieurs instructions return v; qui vont renvoyer la valeur v. Pour une fonction de type de retour void, il n'y a pas de valeur à renvoyer : on peut omettre le return ou écrire return; sans valeur pour sortir de la fonction.

On définit une fonction ainsi :

type_retour nom_fonction(type_arg1 nom_arg1, ..., type_argn nom_argn)
{
    // bloc d'instructions qui constitue le corps
    // de la fonction
}

On est donc très proche des fonctions Python mais avec cette contrainte de type.

int f(int a, char c)
{
    printf("a=%d et c=%c\n", a, c);
    return a*a;
}

On appelle alors la fonction comme en Python avec nom_fonction(val1, ..., valn). Ainsi, l'instruction

int r = f(3, 'z');

affiche

a=3 et c=z

et place dans r la valeur 9.

On voit que la valeur de sortie de la fonction est bien le résultat du return, le reste c'est juste de l'affichage. Si on écrit simplement f(3, 'z');, l'affichage a lieu mais la valeur renvoyée est perdue.

Les arguments sont des variables qu'on peut utiliser directement : cela ne changera pas la valeur passée en paramètre si on les redéfinit. Une fonction peut s'appeler elle-même, avec toutes les réserves vues quant à l'utilisation de la pile d'exécution.

Instructions conditionnelles

Pour effectuer une instruction conditionnelle, on écrit

if (condition)
{
    // bloc d'instructions à exécuter quand la condition est vraie
}
else
{
    // bloc d'instructions à exécuter quand la condition est fausse
}

Par exemple, on pourra écrire :

if (n % 2 == 0)
{
    printf("n est pair\n");
}
else
{
    printf("n est impair\n");
}

Ici, comme il n'y a qu'une instruction, on pourrait ne pas faire de bloc et écrire juste l'instruction. Mais on se gardera de faire ça pour le moment, car c'est une source classique d'erreurs.

On note qu'il n'est pas nécessaire d'avoir un else. Ici, comme en Python et contrairement à OCaml, on n'a pas de notion de type associé aux branches, ce sont juste des suites d'instructions.

On peut ainsi écrire

if (condition)
{
    // instructions si condition est vérifiée
}

Notamment : en C, ce if est une instruction et pas une expression. Si on peut écrire

let x = if n mod 2 = 0 then 1 else 2

en OCaml, en C, on devra écrire :

int x;

if (n % 2 == 0)
{
    x = 1;
}
else
{
    x = 2;
}

Au passage, remarquons qu'on utilise == comme en Python. Par contre, contrairement à Python, comme les déclarations ne sortent pas des blocs, on ne peut pas transposer

if n % 2 == 0:
    x = 1
else:
    x = 2
print("x vaut ", x)

car en C le programme suivant est erroné :

if (n % 2 == 0)
{
    int x = 1;
}
else
{
    int x = 2;
}
printf("x vaut %d\n", x);

En effet, x n'est pas définie en dehors des blocs.

Exercice

Pour la question suivante, on rappelle la définition de la suite de Syracuse.

Étant donné \(a \in \mathbb{N}^*\), on appelle suite de Syracuse de premier terme \(a\) la suite \((u_n)_{n\in\mathbb{N}}\) définie par \(u_0 = a\) et pour \(n \in \mathbb{N}\) :

\[ u_{n+1} = \begin{cases} \frac{u_n}{2} & \text{si } u_n \text{ est pair} \\ 3 u_n + 1 & \text{sinon.} \end{cases} \]

Indications :

• pour déterminer si un nombre a est pair, on peut utiliser le modulo et tester a % 2 == 0 comme en Python ;
• une fonction peut avoir plusieurs return, donc quand vous avez calculé une valeur, il suffit de la renvoyer.

Question 2

Écrire une fonction de prototype

int suivant(int u);

qui renvoie la valeur du terme qui suit u dans la suite.

Corrigé

int suivant(int u)
{
    if (u % 2 == 0)
    {
        return u/2;
    }
    else
    {
        return 3*u+1;
    }
}

Boucles conditionnelles

Pour effectuer une boucle conditionnelle, on écrit

while(condition)
{
    // instructions à réaliser
}

Ce sont, comme en Python, les boucles les plus simples mais elles demandent de gérer plus de choses qu'une boucle inconditionnelle. Par exemple, pour calculer la somme \(\sum_{k=0}^n k\), on doit nécessairement gérer les indices à la main :

int somme_entiers(int n)
{
    int k = 0; // l'indice
    int s = 0;  // la somme courante

    while (k <= n)
    {
        s = s + k;
        k = k+1;
    }

    return s;
}

Le cas le plus approprié d'une telle boucle est quand on ne peut maîtriser le nombre d'itérations comme dans la fonction suivante.

Question 3

Écrire une fonction de prototype

int sup_log2(int n);

qui renvoie, pour \(n \ge 0\), le plus petit entier naturel \(d\) tel que \(n < 2^d\) (attention, cette puissance n'existe pas en C).

Corrigé

int sup_log2(int n)
{
    int d = 0;
    int p = 1;
    while (p <= n)
    {
        p = p * 2;
        d = d + 1;
    }

    return d;
}

Invariant : \(p = 2^d\) et \(2^{d-1} \le n\) dès que \(d \ge 1\). On a ainsi sup_log2(0) = 0, sup_log2(1) = 1 et sup_log2(15) = 4.

Boucles for

Contrairement à Python, il n'y a aucun mécanisme permettant de parcourir des valeurs. Mais contrairement aux boucles for de OCaml, il ne s'agit pas simplement de boucles inconditionnelles. Le mécanisme est plus complexe.

Commençons par un exemple en reprenant la fonction somme_entiers :

int somme_entiers(int n)
{
    int s = 0;

    for(int k = 0; k <= n; k++)
    {
        s = s + k;
    }

    return s;
}

Déjà, précisons que k++ est une manière d'écrire k = k+1. On parle d'incrémentation de k.

Ensuite, on peut voir qu'il y a trois parties dans la boucle for :

for (initialisation; condition; miseajour)
{
    // instructions
}

L'initialisation est la plupart du temps la déclaration d'une variable de boucle. Ici, on peut utiliser le raccourci permettant de déclarer et définir la variable directement. Par opposition au fait d'écrire :

int k;
for (k = 0; k <= n; k++)
{
    s = s+k;
}

Ensuite, vient la condition d'arrêt qui est très proche de celle d'un while.

Enfin, la mise à jour est une instruction qui sera effectuée à la fin de chaque itération. Finalement, une boucle for en C n'est qu'un while déguisé :

initialisation;

while(condition)
{
    // instructions

    miseajour;
}

Pour autant, la lisibilité d'une boucle for est bien meilleure que celle d'un while car elle structure plus en mettant en valeur les vraies instructions du corps de boucle. On ne sera pas surpris de trouver ainsi des for dès que c'est possible.

Question 4

Écrire une fonction de prototype

int somme_carres(int n);

qui renvoie la somme des carrés des entiers de 0 à \(n\) : \(0^2 + 1^2 + \dots + n^2\).

Corrigé

int somme_carres(int n)
{
    int s = 0;
    for (int k = 0; k <= n; k++)
    {
        s = s + k*k;
    }
    return s;
}

Par exemple, somme_carres(13) vaut \(\frac{13 \times 14 \times 27}{6} = 819\).

J'aimerais tant (re)voir Syracuse

Question 5

Écrire une fonction de prototype

int syracuse(int a, int n);

qui renvoie le \(n\)-ième terme \(u_n\) de la suite de Syracuse de premier terme \(a\).

Attention : on utilisera suivant et on ne fera pas de copier-coller de code.

Corrigé

int syracuse(int a, int n)
{
    int u = a;
    for (int k = 1; k <= n; k++)
    {
        u = suivant(u); // on calcule u(k) ici
    }
    return u;
}

Question 6

Écrire une fonction de prototype

int temps_de_vol(int a);

qui renvoie le temps de vol pour \(a\), c'est-à-dire le plus petit entier \(n\) tel que \(u_n = 1\) quand \(u_0 = a\).

Corrigé

int temps_de_vol(int a)
{
    int n = 0;
    int u = a;
    while (u != 1)
    {
        u = suivant(u);
        n = n+1;
    }
    return n;
}

Par exemple temps_de_vol(1) vaut 0 et temps_de_vol(14) vaut 17. La terminaison de cette boucle pour tout \(a\) est exactement la conjecture de Syracuse, qui n'est pas démontrée !

Question 7

Écrire une fonction de prototype

int altitude_maximale(int a);

qui renvoie l'altitude maximale de \(a\), c'est-à-dire la plus grande valeur prise par la suite quand \(u_0 = a\).

Corrigé

Une fois arrivée à 1, la suite boucle sur \(4, 2, 1\) : l'altitude maximale est donc au moins 4, et il ne faut pas oublier le premier terme \(u_0 = a\) (sinon on obtiendrait 8 au lieu de 16 pour \(a = 16\)).

int altitude_maximale(int a)
{
    int m = 4; // la suite finit par boucler sur 4, 2, 1
    if (a > m)
    {
        m = a;
    }
    int u = a;
    while (u != 1)
    {
        u = suivant(u);
        if (u > m)
        {
            m = u;
        }
    }
    return m;
}

Par exemple, altitude_maximale(1) et altitude_maximale(2) valent 4, et altitude_maximale(14) vaut 52.

TP2 - Les tableaux

Déclaration et initialisation

La structure de données la plus primitive en C est celle des tableaux. Attention, ce sont des tableaux de taille fixe comme les 'a array de OCaml. Pour déclarer un tableau t de n valeurs (où n est une CONSTANTE et pas une variable) d'un type T, on écrit

T t[n];

Par exemple int a[10]; déclare a comme étant un tableau de 10 entiers.

Remarque

Depuis C99, il est possible de déclarer un tableau dont la taille est une variable (variable length array). On ne le fera pas : un tel tableau est placé sur la pile et une taille trop grande provoque un dépassement de pile. On verra plus tard comment allouer un tableau de taille quelconque avec malloc.

On peut alors accéder en lecture et en écriture à la \(i\)-ème case du tableau en écrivant t[i]. Ici tout se passe comme si t était une collection de variables accessibles par des indices. De plus, on a l'assurance que les cases se suivent linéairement en mémoire, ce qui sera utile dans la suite.

REMARQUE : C est un langage sans garde-fou, on peut tout à fait écrire t[100] pour un tableau de taille 3 et ainsi aller écrire n'importe où en mémoire et...

Explosion d'Ariane 5 au premier lancement (1996), suite à une erreur de conversion d'un flottant vers un entier 16 bits trop petit, non rattrapée, qui a conduit à l'autodestruction du lanceur.

Attention : dans presque tous les cas, les valeurs ne sont pas initialisées, et comme pour les variables, il faut attribuer des valeurs avant de travailler sur le tableau. Notamment, les cases ne sont pas initialisées à zéro.

Il est possible d'initialiser un tableau au moment de sa déclaration. Pour cela, on met les valeurs entre accolades comme ici :

int t[3] = { 1, 3, 5 };

Ce qui équivaut à l'écriture de :

int t[3];
t[0] = 1;
t[1] = 3;
t[2] = 5;

Si jamais on donne moins de n valeurs pour t[n], on va compléter par des valeurs nulles. Cela permet d'utiliser le cas spécial { 0 } pour tout initialiser à zéro. Les trois définitions suivantes sont alors équivalentes :

int t[3] = { 0, 0, 0 };
int t[3] = { 0, 0 };
int t[3] = { 0 };

Remarque

On rencontre aussi int t[3] = {}; : c'est une extension de gcc, acceptée par la norme seulement depuis C23.

Quand on donne une succession complète de valeurs, on connaît déjà le nombre d'éléments du tableau. Il est alors assez redondant de le donner une seconde fois dans la déclaration. On dispose ainsi d'un mécanisme automatique en écrivant juste T t[] = ...;. On peut reprendre la déclaration précédente ainsi :

int t[] = { 1, 3, 5 };

Tableaux en arguments

Pour passer un tableau en paramètre à une fonction on pourra utiliser, entre autres, int t[] ou int t[10] avec une taille précise, mais il n'y a aucune vérification de taille en C. On prendra donc l'habitude de donner en arguments le nombre d'éléments du tableau.

Ainsi la fonction suivante calcule la somme des éléments d'un tableau.

int somme_tableau(int t[], int nb_elements)
{
    int s = 0;

    for (int i = 0; i < nb_elements; i++)
    {
        s = s + t[i];
    }

    return s;
}

Qu'on peut tester ainsi :

int t[] = { 0, 1, 2, 3 };
printf("%d\n", somme_tableau(t, 4)); // affiche 6

Mais on peut très bien appeler la fonction sur le même tableau avec une taille plus petite :

printf("%d\n", somme_tableau(t, 3)); // affiche 3

Ou une taille plus grande, mais alors rappelez-vous de la fusée au-dessus...

printf("%d\n", somme_tableau(t, 1000)); // comportement indéterminé

Remarque

En fait, le tableau n'est pas copié lors de l'appel : la fonction reçoit l'adresse de sa première case. C'est pourquoi elle ne peut pas connaître sa taille, et pourquoi elle peut modifier ses cases. On reviendra sur ce point avec les pointeurs (voir Pointeurs et tableaux).

Question 1

Écrire une fonction

int recherche(int t[], int nb_elements, int x);

qui renvoie le plus petit indice de x dans le tableau t ; si x n'est pas présent, on renvoie -1 (qui est toujours un indice invalide).

Rappel : on peut faire des return quand on veut.

Corrigé

int recherche(int t[], int nb_elements, int x)
{
    for (int i = 0; i < nb_elements; i++)
    {
        if (t[i] == x)
        {
            return i;
        }
    }

    return -1;
}

Question 2

Écrire une fonction

int maximum(int t[], int nb_elements);

qui renvoie la valeur du maximum du tableau t.

On considère que nb_elements \(> 0\), donc il en existe toujours un.

Corrigé

int maximum(int t[], int nb_elements)
{
    int m = t[0];
    for (int i = 1; i < nb_elements; i++)
    {
        if (m < t[i])
        {
            m = t[i];
        }
    }

    return m;
}

Question 3

En déduire une fonction arg_max qui renvoie le plus petit indice du maximum de t où nb_elements \(> 0\).

Attention : on ne fera pas de boucles ici.

Corrigé

int arg_max(int t[], int nb_elements)
{
    return recherche(t, nb_elements, maximum(t, nb_elements));
}

Cette solution parcourt deux fois le tableau, ce qui reste linéaire.

Les booléens

Les booléens ne sont pas définis par défaut, il faut pour cela charger un fichier d'en-tête particulier, stdbool.h. Pour cela, on rajoute en tête de fichier la ligne

#include <stdbool.h>

On dispose alors d'un type bool ayant deux valeurs true et false.

Il s'agit en fait d'un enrobage autour des entiers 1 et 0, mais c'est beaucoup plus sûr de passer par le type bool.

Question 4

Écrire une fonction de prototype

bool est_trie(int t[], int nb_elements);

qui renvoie un booléen indiquant si un tableau d'entiers est trié dans l'ordre croissant.

Note : on pourra interrompre l'exécution pour return false, pas besoin de calculer explicitement ce booléen dans une variable.

Corrigé

bool est_trie(int t[], int nb_elements) {
    for(int i = 0; i < nb_elements-1; i++) {
        if (t[i] > t[i+1])
            return false;
    }
    return true;
}

Un tableau vide ou à un élément est trié : la boucle ne fait alors aucune itération.

Des tableaux particuliers : les chaînes de caractères

Présentation du type

Une chaîne de caractères en C est juste un tableau de char dont on impose que la dernière case soit nulle. Dans le contexte des caractères on note '\0' le caractère nul, mais cela correspond à la valeur 0.

Ainsi :

char chaine[] = { 'B', 'o', 'n', 'j', 'o', 'u', 'r', '\0' };

est la chaîne contenant Bonjour. Comme écrire ainsi les chaînes serait très fastidieux, on utilise la notation usuelle :

char chaine[] = "Bonjour";

et tout se passe comme dans la définition ci-dessus : le tableau a 8 cases.

Pour afficher une chaîne, on peut utiliser printf. Attention à s'assurer d'avoir la ligne

#include <stdio.h>

en tête de votre fichier.

Pour afficher la chaîne s puis revenir à la ligne, on écrira :

printf("%s\n", s);

Attention, les caractères en C sont limités : un char occupe un seul octet et ne peut contenir que les caractères de la table ASCII (lettres non accentuées, chiffres, ponctuation...). On peut tout de même écrire des caractères accentués, de l'arabe ou du japonais dans une chaîne : ils sont alors codés (en UTF-8 sur nos machines) sur plusieurs octets, donc plusieurs char, ce qui fausse par exemple le calcul de la longueur de la chaîne. Il y a un certain nombre de caractères spéciaux comme \n pour effectuer un saut de ligne. On reverra ce codage plus tard.

Parcourir une chaîne

La valeur finale '\0' est ce qu'on appelle en informatique une sentinelle : elle permet de s'assurer que le tableau est fini et de ne pas avoir à donner sa longueur en plus. Une alternative pourrait être de mettre la longueur du tableau en première case pour un tableau d'entiers, mais c'est problématique quand on a un tableau de valeurs non entières ou qui peuvent dépasser cela.

On peut donc parcourir une chaîne avec une boucle while pour s'assurer qu'on est sur un caractère autre que '\0'.

Question 5

Écrire une fonction de prototype

int longueur(char s[]);

qui renvoie le nombre de caractères de s, sans compter le '\0'.

Corrigé

int longueur(char s[]) {
    int n = 0;
    while (s[n] != '\0') {
        n = n+1;
    }
    return n;
}

Cette fonction est si courante qu'elle existe déjà en C avec la fonction strlen présente dans l'en-tête

#include <string.h>

On écrira donc souvent

int n = strlen(s);
for(int i = 0; i < n; i++)
{
    // parcours de la chaîne
}

Attention, si on effectue le test i < strlen(s) avec des compilateurs pas malins, l'appel à strlen est effectué à chaque itération et c'est très coûteux : on obtient une boucle de complexité quadratique en la longueur de la chaîne.

Premières fonctions sur les chaînes

Un caractère est un petit entier sur un octet, entre -128 et 127 (ou entre 0 et 255 selon les compilateurs). Il n'y a pas de conversion à faire : en C, la valeur 'a' est un entier valant \(97\), son code ASCII.

Les lettres de l'alphabet se suivent dans ce codage, ainsi une lettre minuscule est entre 'a' et 'z'.

Question 6

Écrire une fonction de prototype

bool est_minuscule(char s[]);

qui renvoie un booléen indiquant si tous les caractères de s sont des lettres minuscules.

On pourra simplement tester la fonction en appelant est_minuscule("Toto"), donc en donnant une chaîne constante directement, sans définir de variable.

Corrigé

bool est_minuscule(char s[]) {
    int n = strlen(s);
    for(int i = 0; i < n; i++) {
        if (s[i] < 'a' || s[i] > 'z')
            return false;
    }

    return true;
}

Contrairement à OCaml ou Python, on peut modifier les caractères d'une chaîne.

Ainsi :

s[1] = 'c';

remplace le second caractère de s par 'c'.

Question 7

Écrire une fonction de prototype

void capitalise(char s[]);

qui remplace toutes les lettres minuscules par la majuscule correspondante.

Attention, pour tester, on ne peut pas écrire

capitalise("Toto");

car "Toto" est en lecture seule. Il faut écrire

char s[] = "Toto";
capitalise(s);

Corrigé

void capitalise(char s[]) {
    int n = strlen(s);
    for(int i = 0; i < n; i++) {
        if (s[i] >= 'a' && s[i] <= 'z') {
            s[i] = s[i] + 'A' - 'a';
        }
    }
}

Question 8

Écrire une fonction de prototype

bool palindrome(char s[]);

qui vérifie si une chaîne est un palindrome, c'est-à-dire si on peut la lire de la même manière de gauche à droite et de droite à gauche.

Corrigé

On compare les caractères deux à deux en partant des deux extrémités, sans oublier de faire avancer les deux indices.

bool palindrome(char s[]) {
    int i = 0;
    int j = strlen(s) - 1;
    while (i < j) {
        if (s[i] != s[j]) {
            return false;
        }
        i = i + 1;
        j = j - 1;
    }
    return true;
}

La chaîne vide (j = -1) et les chaînes d'un caractère sont des palindromes.

La fonction printf

On va maintenant revenir sur la fonction printf vue précédemment. C'est une fonction spéciale qui peut prendre un nombre variable d'arguments mais qui en aura toujours au moins un : printf(format, ...) où format est une chaîne de caractères. Cette chaîne peut comporter des symboles spéciaux commençant par % et affichant, dans l'ordre de gauche à droite, les valeurs passées en argument après format.

On a par exemple %d pour afficher un entier signé, %s pour une chaîne de caractères ou %c pour un caractère. Exemple :

char s[] = "Test";
int i = 2;
printf("Le %deme caractère de la chaine %s est %c\n",
     i, s, s[i]); // oui on commence à compter à 0

Le nombre renvoyé par printf est le nombre de caractères (plus précisément d'octets) affichés après ces substitutions.

On pourra utiliser la fonction suivante pour afficher un tableau :

void print_tableau(int t[], int nb_elements)
{
    for(int i = 0; i < nb_elements; i++)
    {
        char c = ',';
        if (i == nb_elements - 1)
            c = '\n'; // fin de ligne pour le dernier élément.
        printf("%d%c", t[i], c);
    }
}

qu'on appelle ainsi :

int t[] = {1, 2, 3};
print_tableau(t, 3); // affiche 1,2,3

Question 9

Écrire une fonction de prototype

void print_matrix(int t[], int n, int p);

qui prend un tableau de \(n \times p\) entiers représentant une matrice à \(n\) lignes et \(p\) colonnes comme la suite de ses coefficients ligne après ligne, et affiche cette matrice sous un format lisible, avec une ligne d'affichage par ligne de la matrice.

Par exemple, la matrice

\[ \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix} \]

sera représentée par le tableau { 1, 2, 3, 4, 5, 6 }. On l'affichera ainsi :

1 2 3
4 5 6

Corrigé

Le coefficient de la ligne \(i\) et de la colonne \(j\) se trouve à l'indice \(i \times p + j\) du tableau.

void print_matrix(int t[], int n, int p)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < p; j++)
        {
            printf("%d", t[i * p + j]);
            if (j < p - 1)
            {
                printf(" ");
            }
        }
        printf("\n");
    }
}

TP3 - Renforcement

Vous pouvez directement récupérer le fichier TP_C_3.c pour le compléter : il contient les squelettes des fonctions (à la place des // FIXME) et des tests automatiques, lancés par la fonction main qui affiche VALIDE ou INVALIDE pour chaque question.

Manipulations de tableaux

Question 1

Écrire une fonction swap qui prend en entrée, dans cet ordre, un tableau d'entiers, deux indices i et j et permute les valeurs du tableau situées à ces indices.

void swap(int tab[], int i, int j);

Corrigé

void swap(int tab[], int i, int j)
{
    int temp = tab[i];
    tab[i] = tab[j];
    tab[j] = temp;
}

Question 2

Écrire une fonction renverse qui prend en entrée, dans cet ordre, un tableau d'entiers puis un entier indiquant le nombre d'éléments de ce tableau, et permute ses éléments de manière à renverser le tableau : 1,2,3 devient 3,2,1.

void renverse(int tab[], int nb);

Corrigé

void renverse(int tab[], int nb)
{
    for (int i = 0; i < nb/2; i++)
    {
        swap(tab, i, nb-1-i);
    }
}

Question 3

Prouver la correction de renverse.

Indication : on pourra noter \(a_0,\dots,a_{n-1}\) les valeurs initiales du tableau et \(t_0,\dots,t_{n-1}\) les valeurs à un instant donné de l'exécution, et exprimer l'invariant en liant ces valeurs et l'indice de boucle.

Corrigé

Tout d'abord, on remarque qu'il n'est pas nécessaire de prouver la terminaison vu qu'il s'agit d'une boucle for effectuant exactement \(\lfloor n/2 \rfloor\) itérations.

On va prouver l'invariant suivant, vérifié au début de l'itération d'indice \(i\) :

\[ I(i) : \left(\forall k \in \range{0}{i-1},\ t_k = a_{n-1-k} \wedge t_{n-1-k} = a_k \right) \wedge \left(\forall k \in \range{i}{n-1-i},\ t_k = a_k\right). \]

• Initialisation : on a directement \(I(0)\) car \(\range{0}{-1} = \emptyset\) et aucune case n'a été modifiée.
• Hérédité : si on a \(I(i)\) en début d'itération, avec \(i < \lfloor n/2 \rfloor\), alors \(i < n-1-i\) et les indices \(i\) et \(n-1-i\) sont dans \(\range{i}{n-1-i}\). On va donc réaliser l'échange entre \(t_i = a_i\) et \(t_{n-1-i} = a_{n-1-i}\) (par l'invariant). On va ainsi avoir ensuite \(t_i = a_{n-1-i}\) et \(t_{n-1-i} = a_i\), ce qui permet de compléter la première propriété de l'invariant pour \(k=i\). Comme on n'a pas touché aux autres éléments, la seconde propriété reste vérifiée sur \(\range{i+1}{n-2-i}\). On a bien \(I(i+1)\) en sortie.

Conclusion : on a \(I(\lfloor n/2 \rfloor)\) vérifié en sortie de boucle, ainsi \(\forall k \in \range{0}{\lfloor n/2 \rfloor-1},\ t_k = a_{n-1-k} \wedge t_{n-1-k} = a_k\). Quand \(n = 2p\) est pair, les indices \(k\) et \(n-1-k\) pour \(k \in \range{0}{p-1}\) couvrent tout le tableau. Il n'y a qu'un élément potentiellement non couvert, quand \(n = 2p+1\) est impair : c'est l'élément central d'indice \(p\). Or, la seconde partie de l'invariant devient alors \(\forall k \in \range{p}{2p+1-1-p} = \{ p \},\ t_k = a_k\). Cet élément n'a donc pas bougé, et \(t_p = a_p = a_{n-1-p}\). On a bien renversé le tableau dans tous les cas.

Question 4

Écrire une fonction qui, étant donné un tableau d'entiers et sa taille, effectue un traitement en place sur le tableau en sorte que le tableau commence par les nombres pairs et termine par les impairs, en respectant l'ordre dans lequel ils étaient dans le tableau initialement.

void pairs_devant(int tab[], int nb);

Exemples :

• 1, 2, 3, 4 devient 2, 4, 1, 3 ;
• 1, 3 reste 1, 3 ;
• 5, 4, 1, 2, 3 devient 4, 2, 5, 1, 3.

On pourra commencer par écrire deux fonctions : cherche_pair qui cherche l'indice du premier nombre pair à partir d'un indice i (et -1 s'il n'y en a pas), et decale qui prend deux indices i et j et effectue les affectations dans le tableau ainsi : j-1 \(\rightarrow\) j, j-2 \(\rightarrow\) j-1, ..., i \(\rightarrow\) i+1, pour pouvoir placer un élément en i.

Corrigé

Ici, les deux fonctions auxiliaires ont été écrites directement dans la boucle : à l'étape i, on cherche le premier pair d'indice r >= i, on décale d'un cran vers la droite les cases d'indices i à r-1 (qui sont toutes impaires) et on place le pair trouvé en i.

void pairs_devant(int tab[], int nb)
{
    for(int i = 0; i < nb; i++)
    {
        int r = -1;
        for (int j = i; j < nb; j++)
        {
            if(tab[j] % 2 == 0)
            {
                r = j;
                break;
            }
        }
        if (r == -1) break;
        int p = tab[r];
        for (int k = r-1; k >= i; k--)
        {
            tab[k+1] = tab[k];
        }
        tab[i] = p;
    }
}

Dans le pire cas, cet algorithme est en \(O(n^2)\).

Le chiffre de Playfair

Le chiffre de Playfair est une technique manuelle de chiffrement symétrique et a été historiquement la première technique de chiffrement par substitution de digrammes.

Ce chiffre utilise une table de 5 par 5 contenant chaque lettre de l'alphabet latin exactement une fois, hormis la lettre Q. La table constitue la clé de chiffrement.

Par exemple, on peut considérer la table suivante :

P	L	A	Y	F
I	R	E	X	M
B	C	D	G	H
J	K	N	O	S
T	U	V	W	Z

Pour chiffrer un message, on retire tous les espaces et on coupe le message en digrammes (groupes de deux lettres) de telle sorte que, par exemple, Hello World devienne HE LL OW OR LD. Ensuite on applique les règles suivantes pour chaque digramme afin de produire le message chiffré.

• Si les deux lettres sont les mêmes (ou qu'il n'y a plus qu'une lettre comme à la fin d'un message de longueur impaire), on remplace la seconde lettre par un X et on chiffre le digramme obtenu.
• Si les lettres sont sur la même rangée de la table, on les chiffre avec les lettres situées immédiatement à leur droite (si on sort de la rangée ainsi, on retourne à la première lettre de celle-ci). Avec la table au-dessus, CH devient DB.
• Si les lettres sont sur la même colonne, on les chiffre par les lettres situées immédiatement en dessous dans la table, en revenant aussi à la première en cas de dépassement. Ainsi VA devient AE.
• Si les lettres ne sont pas sur la même rangée ou la même colonne, elles sont les sommets d'un rectangle dans la table, on les chiffre alors avec les autres sommets du rectangle. Comme l'ordre importe, on choisit de chiffrer une lettre par le sommet qui est sur la même rangée. Ainsi KM devient SR.

Remarque

Dans le vrai chiffre de Playfair, la première règle insère un X entre les deux lettres identiques, la seconde lettre étant reportée dans le digramme suivant : TREES se découpe en TR EX ES. On a simplifié ici en remplaçant la seconde lettre, ce qui garantit que le message chiffré a la même longueur que le message (arrondie au nombre pair supérieur), au prix de la perte d'une lettre : le déchiffrement donnera TREXES... à moins de ne jamais avoir deux lettres identiques dans un digramme.

La table précédente pourra être stockée sous la forme de la chaîne "PLAYFIREXMBCDGHJKNOSTUVWZ" : la lettre de la rangée row et de la colonne col est à l'indice 5 * row + col.

On ne considère ici que des messages en majuscules, sans espace et sans la lettre Q. De plus, on va supposer qu'on n'a jamais deux X consécutifs ni un X en dernière position (avec le vrai chiffre, cela ferait boucler la première règle).

Question 5

Écrire deux fonctions qui prennent un caractère c présent dans la clé et renvoient respectivement son numéro de rangée et son numéro de colonne dans la table.

int car_vers_row(char cle[], char c);
int car_vers_col(char cle[], char c);

Avec la table précédente, K est à la rangée 3 et à la colonne 1.

Corrigé

int car_vers_row(char cle[], char c)
{
    int i;
    for (i = 0; i < 25; i++)
    {
        if (cle[i] == c)
            break;
    }
    return i / 5;
}

int car_vers_col(char cle[], char c)
{
    int i;
    for (i = 0; i < 25; i++)
    {
        if (cle[i] == c)
            break;
    }
    return i % 5;
}

Question 6

Écrire une fonction qui renvoie le caractère situé dans la table cle sur la rangée row et la colonne col.

char position_vers_car(char cle[], int row, int col);

Corrigé

char position_vers_car(char cle[], int row, int col)
{
    return cle[5 * row + col];
}

Question 7

Écrire une fonction qui réalise le chiffrement de s avec la clé cle sous forme d'une chaîne comme ci-dessus.

void chiffre(char cle[], char s[], char sortie[]);

La chaîne sortie contient assez de place pour stocker le message chiffré. Vous devrez bien rajouter un '\0' à la fin.

Avec la table précédente, HIDETHEGOLDINTHETREEESTUMP devient BMNDZBXDKYBEJVDMUIXMMNUVIF.

Corrigé

void chiffre(char cle[], char s[], char sortie[])
{
    int n = strlen(s);
    for (int i = 0; i < n; i += 2)
    {
        char c1 = s[i];
        char c2;
        if (i+1 < n) c2 = s[i+1];
        else c2 = 'X';
        if (c1 == c2) c2 = 'X';

        int x1 = car_vers_row(cle, c1);
        int y1 = car_vers_col(cle, c1);
        int x2 = car_vers_row(cle, c2);
        int y2 = car_vers_col(cle, c2);

        if (x1 == x2)
        {
            c1 = position_vers_car(cle, x1, (y1+1)%5);
            c2 = position_vers_car(cle, x2, (y2+1)%5);
        }
        else if (y1 == y2)
        {
            c1 = position_vers_car(cle, (x1+1)%5, y1);
            c2 = position_vers_car(cle, (x2+1)%5, y2);
        }
        else
        {
            c1 = position_vers_car(cle, x1, y2);
            c2 = position_vers_car(cle, x2, y1);
        }
        sortie[i] = c1;
        sortie[i+1] = c2;
    }
    if (n%2 == 0) sortie[n] = '\0';
    else sortie[n+1] = '\0';
}

La chaîne sortie doit donc pouvoir contenir \(n+2\) caractères quand \(n\) est impair, et \(n + 1\) sinon.

TP4 - Automates de Wolfram

Vous pouvez directement récupérer le fichier TP_C_4.c pour le compléter. Il contient des tests automatiques de vos fonctions.

Conversions binaires

On considère l'écriture binaire \(n = \sum_{k=0}^{+\infty} b_k 2^k\) d'un entier naturel \(n\), où les \(b_k \in \{0, 1\}\) sont presque tous nuls. En pratique, on ne considère que des nombres dont la taille est majorée, donc de la forme \(\sum_{k=0}^{N-1} b_k 2^k\). \(N\) est le nombre de bits sur lequel on a écrit l'entier \(n\). Le bit \(b_{N-1}\) peut être nul, c'est-à-dire qu'on n'impose pas que \(b_{N-1} \neq 0\) ; par contre, on a forcément \(n < 2^N\).

Les différents types de valeurs entières en C sont de la forme t ou unsigned t où :

• unsigned signifie qu'on ne peut stocker que des valeurs positives ; si on l'omet on peut avoir des valeurs négatives, sachant qu'il faut un bit pour coder l'information du signe : un même type peut prendre des valeurs deux fois plus grandes en unsigned, de \(0\) à \(2^N - 1\) ;

• t peut valoir (types principaux) ATTENTION : c'est dépendant du compilateur, on donne ici les valeurs usuelles pour un compilateur moderne et un processeur 64 bits ! :

  • char : pour des valeurs sur \(N=8\) bits, donc 1 octet, donc de \(-128\) à \(127\) ;
  • short : pour des valeurs sur \(N=16\) bits, 2 octets, donc de \(-2^{15}\) à \(2^{15}-1\) ;
  • int : pour des valeurs sur \(N=32\) bits, donc 4 octets, donc de \(-2^{31}\) à \(2^{31}-1\) ;
  • long : pour des valeurs sur \(N=64\) bits, donc 8 octets, donc de \(-2^{63}\) à \(2^{63}-1\) (mais seulement 4 octets sous Windows).

Dans le doute, on peut connaître la taille en nombre d'octets en utilisant sizeof :

printf("%zu\n", sizeof(long));

va afficher 8.

Il est aussi possible d'utiliser des types explicites comme int32_t ou int64_t, définis dans stdint.h, qui ont une taille indépendante de l'architecture de compilation.

Question 1

Écrire une fonction de prototype

void vers_binaire(unsigned int x, unsigned char b[]);

où on considère ici que b est un tableau de 32 unsigned char. Cette fonction renvoie dans b la représentation en binaire de x de sorte que b[i] contienne \(b_i\) de l'expression au-dessus (comme toujours, voir les tests en cas de doute).

Corrigé

void vers_binaire(unsigned int x, unsigned char b[])
{
    for (int i = 0; i < 32; i++)
    {
        b[i] = x % 2;
        x = x / 2;
    }
}

Question 2

Écrire une fonction de prototype

unsigned int depuis_binaire(unsigned char b[]);

qui renvoie l'entier représenté par le tableau de 32 bits b. On fera en sorte que depuis_binaire et vers_binaire soient réciproques l'une de l'autre.

Corrigé

unsigned int depuis_binaire(unsigned char b[])
{
    unsigned int x = 0;
    unsigned int p = 1;
    for (int i = 0; i < 32; i++)
    {
        if (b[i] == 1)
        {
            x = x + p;
        }
        p = 2*p;
    }
    return x;
}

Au dernier tour, p = 2*p dépasse \(2^{32} - 1\) : pour un type unsigned, le calcul est fait modulo \(2^{32}\) (ici p revient à 0), ce qui est sans conséquence. Avec un int, ce dépassement serait un comportement indéterminé.

Présentation et premier automate de Wolfram

On va s'intéresser ici à des automates cellulaires unidimensionnels. On considère ainsi une ligne infinie de cellules. Chaque cellule a exactement deux cellules voisines, une à sa droite et une à sa gauche. Les cellules contiennent un état. Pour simplifier ici, on ne va considérer que deux états 1 et 0, noir ou blanc, ou encore '#' et ' ' dans la suite.

Afin de représenter informatiquement de telles lignes infinies, on va considérer un nombre fini de cellules en supposant que toutes les autres sont dans l'état 0.

Une ligne finie de cellules (bleu = 1, blanc = 0), toutes les autres étant à 0.

Un automate de Wolfram est la donnée d'un ensemble de règles de la forme

Les huit règles $(g,c,d) \rightarrow c'$ : en haut le voisinage, en bas le nouvel état (bleu = 1).

ce qui peut se lire sous la forme \((g,c,d) \rightarrow c'\) : connaissant l'état \(g\) de la cellule de gauche, \(c\) de la cellule courante et \(d\) de la cellule de droite, le nouvel état de la cellule courante est \(c'\).

Exemple : dans le cas du jeu de règles au-dessus, une cellule à 1 dont la voisine de gauche est à 1 et la voisine de droite à 0 va passer à 0.

Question 3

Écrire une fonction de prototype

int regle_vois(int g, int c, int d);

qui prend un triplet \((g,c,d)\) sous la forme de valeurs 0 ou 1 et renvoie \(c'\) selon la règle au-dessus en image, selon la correspondance case pleine (bleue) = 1, case vide = 0.

Indication : oui, il faut faire un paquet de if sans aucune finesse.

Corrigé

int regle_vois(int g, int c, int d)
{
    if (g == 1 && c == 1 && d == 1)
        return 0;
    if (g == 1 && c == 1 && d == 0)
        return 0;
    if (g == 1 && c == 0 && d == 1)
        return 0;
    if (g == 1 && c == 0 && d == 0)
        return 1;
    if (g == 0 && c == 1 && d == 1)
        return 1;
    if (g == 0 && c == 1 && d == 0)
        return 1;
    if (g == 0 && c == 0 && d == 1)
        return 1;
    return 0;
}

On voit dans l'exemple précédent qu'il y a 8 cas de figure ; on peut les numéroter de 0 à 7. En fait, on peut considérer l'entier \(4g + 2c + d\) pour associer à un tel triplet ce numéro. Par exemple, la configuration \((1,1,0)\) correspond à \(4 + 2 = 6\).

On a ici rajouté ces numéros sur la règle précédente :

Les mêmes règles, numérotées par $4g+2c+d$.

Question 4

Écrire une fonction de prototype

int regle(int config);

qui se comporte comme la fonction précédente mais prend le triplet sous la forme d'un numéro comme décrit au-dessus et renvoie la nouvelle valeur.

On ne fera PAS appel à la fonction regle_vois précédente.

Corrigé

int regle(int config)
{
    if (config == 0 || config == 5 || config == 6 || config == 7)
        return 0;
    return 1;
}

On va considérer que la configuration est donnée sous la forme d'une chaîne, par exemple "__##__#" (on a écrit _ pour les espaces ici pour qu'ils soient visibles), où les '#' correspondent à noir, donc à 1, et les ' ' à blanc, donc à 0. On suppose qu'à gauche et à droite de cette configuration, il n'y a que des ' '.

Si on applique la règle précédente sur cette configuration, on va obtenir "_##_###". On remarque que la cellule juste à droite de la chaîne devrait devenir noire en appliquant la règle (sa configuration est \((1,0,0)\)), mais pour simplifier, on ignore cette cellule, ce qui va, dans la suite, revenir à la maintenir blanche.

Question 5

Écrire une fonction de prototype

void suivant(char in[], char out[]);

qui prend une configuration in de cellules SOUS LA FORME D'UNE CHAÎNE (donc terminée par '\0' et dont on peut obtenir la taille avec strlen), applique la règle précédente sur chacune des cellules et stocke la nouvelle configuration dans la chaîne out DE MÊME LONGUEUR.

ATTENTION : on utilise à la place de 0 le caractère ' ' et à la place de 1 le caractère '#'.

ATTENTION : en dehors du tableau, on considère que les cellules sont à ' '.

Corrigé

void suivant(char in[], char out[])
{
    int n = strlen(in);
    for(int i = 0; i < n; i++)
    {
        int config = 0;
        if (i > 0 && in[i-1] == '#')
        {
            config += 4;
        }
        if (in[i] == '#')
        {
            config += 2;
        }
        if (i < n-1 && in[i+1] == '#')
        {
            config += 1;
        }
        if (regle(config) == 1)
        {
            out[i] = '#';
        }
        else
        {
            out[i] = ' ';
        }
    }
}

Il est indispensable d'écrire dans une autre chaîne que in : sinon, la cellule i+1 serait calculée à partir de la nouvelle valeur de la cellule i.

Question 6

Écrire une fonction de prototype

void copie_chaine(char tgt[], char src[]);

qui prend en entrée deux chaînes src et tgt de même longueur et copie la chaîne src dans la chaîne tgt.

Corrigé

void copie_chaine(char tgt[], char src[])
{
    int n = strlen(src);
    for (int i = 0; i < n; i++)
    {
        tgt[i] = src[i];
    }
}

Comme les deux chaînes ont la même longueur, le '\0' de tgt est déjà à la bonne place. La fonction strcpy de string.h fait la même chose en recopiant aussi le '\0'.

Question 7

Écrire une fonction de prototype

void itere_regle(char depart[], char temp[], char sortie[], int iterations);

qui applique iterations fois la fonction suivant en partant de la configuration depart et place la configuration finale dans sortie.

Comme on ne sait pas encore allouer une telle chaîne dynamiquement, on vous donne aussi une chaîne temp comme espace de travail.

ATTENTION : les chaînes depart, temp et sortie sont de même longueur.

ATTENTION : il ne faut pas modifier la chaîne depart.

Corrigé

void itere_regle(char depart[], char temp[], char sortie[], int iterations)
{
    copie_chaine(sortie, depart);
    copie_chaine(temp, depart);
    for (int i = 0; i < iterations; i++)
    {
        suivant(temp, sortie);
        copie_chaine(temp, sortie);
    }
}

La suite d'instructions suivante devrait vous permettre de voir les 30 premières itérations.

char init[81];
for(int i = 0; i < 80; i++)
{
    init[i] = ' ';
}
init[80] = '\0';
init[40] = '#';

char temp[81], sortie[81];
strcpy(temp, init);
strcpy(sortie, init);

for(int i = 0; i < 30; i++)
{
    itere_regle(init, temp, sortie, i);
    printf("%s\n", sortie);
}

Les premières lignes affichées sont :

                                        #
                                       ###
                                      ##  #
                                     ## ####
                                    ##  #   #
                                   ## #### ###
                                  ##  #    #  #
                                 ## ####  ######

Les 256 règles

Il se trouve que la règle qu'on vient d'implémenter s'appelle la règle 30. En effet, si on décore la règle précédente :

Les sorties lues de 7 à 0 forment le nombre binaire 00011110 = 30.

on peut lire le nombre binaire 00011110 qui correspond à \(0 \times 128 + 0 \times 64 + 0 \times 32 + 1 \times 16 + 1 \times 8 + 1 \times 4 + 1 \times 2 + 0 \times 1 = 16 + 8 + 4 + 2 = 30\).

Autrement dit, la valeur associée à la configuration numéro \(k\) est le bit \(b_k\) de l'écriture binaire du numéro de la règle.

On va maintenant définir une fonction permettant d'obtenir la règle associée à un nombre entre 0 et 255. Par exemple, comme \(111\) s'écrit \(01101111\) en binaire, cela signifie qu'on associe la valeur 0 aux configurations de numéro 7 et 4 (i.e. \((g,c,d)\) valant \((1,1,1)\) et \((1,0,0)\)) et la valeur 1 à toutes les autres.

Question 8

Écrire une fonction de prototype

int regle_gen(int gen, int config);

qui renvoie la valeur obtenue en appliquant la règle gen sur la configuration de numéro config.

On pourra utiliser vers_binaire, même si, sur 32 bits, beaucoup de valeurs seront à 0.

Corrigé

int regle_gen(int gen, int config)
{
    unsigned char r[32];
    vers_binaire(gen, r);
    return r[config];
}

On peut aussi éviter le tableau en écrivant directement return (gen >> config) % 2; où >> est le décalage à droite des bits.

Question 9

Écrire une fonction de prototype

void suivant_gen(int gen, char in[], char out[]);

qui prend une configuration in de cellules SOUS LA FORME D'UNE CHAÎNE (donc terminée par '\0' et dont on peut obtenir la taille avec strlen), applique la règle gen sur chacune et stocke la nouvelle configuration dans la chaîne out DE MÊME LONGUEUR.

ATTENTION : on utilise à la place de 0 le caractère ' ' et à la place de 1 le caractère '#'.

ATTENTION : en dehors du tableau, on considère que les cellules sont à ' '.

REMARQUE : avec un COPIER-COLLER de ce que vous avez fait pour suivant, ça prend une seconde.

Corrigé

void suivant_gen(int gen, char in[], char out[])
{
    int n = strlen(in);
    for(int i = 0; i < n; i++)
    {
        int config = 0;
        if (i > 0 && in[i-1] == '#')
        {
            config += 4;
        }
        if (in[i] == '#')
        {
            config += 2;
        }
        if (i < n-1 && in[i+1] == '#')
        {
            config += 1;
        }
        if (regle_gen(gen, config) == 1)
        {
            out[i] = '#';
        }
        else
        {
            out[i] = ' ';
        }
    }
}

Question 10

Écrire une fonction de prototype

void itere_regle_gen(int gen, char depart[], char temp[], char sortie[], int iterations);

qui applique iterations fois la fonction suivant_gen en partant de la configuration depart et place la configuration finale dans sortie.

Comme on ne sait pas encore allouer une telle chaîne dynamiquement, on vous donne aussi une chaîne temp comme espace de travail.

ATTENTION : les chaînes depart, temp et sortie sont de même longueur.

REMARQUE : avec un COPIER-COLLER de ce que vous avez fait pour itere_regle, ça prend une seconde.

Corrigé

void itere_regle_gen(int gen, char depart[], char temp[], char sortie[], int iterations)
{
    copie_chaine(sortie, depart);
    copie_chaine(temp, depart);
    for (int i = 0; i < iterations; i++)
    {
        suivant_gen(gen, temp, sortie);
        copie_chaine(temp, sortie);
    }
}

Question 11

En vous inspirant des 30 itérations calculées par le code donné plus haut, affichez les 30 premières itérations des 256 règles en partant d'une même configuration.

Corrigé

Il suffit de rajouter une boucle sur les numéros de règle, de 0 à 255 inclus. Plutôt que de tout recalculer à chaque ligne avec itere_regle_gen, on peut appliquer une fois suivant_gen par ligne.

char init[81];
for(int i = 0; i < 80; i++)
{
    init[i] = ' ';
}
init[80] = '\0';
init[40] = '#';

char temp[81], sortie[81];
for (int gen = 0; gen < 256; gen++)
{
    printf("Règle %d\n", gen);
    strcpy(sortie, init);
    for(int j = 0; j < 30; j++)
    {
        printf("%s\n", sortie);
        strcpy(temp, sortie);
        suivant_gen(gen, temp, sortie);
    }
    printf("\n");
}