Aller au contenu

Les tests sont écrits avec assert (il faut #include <assert.h>) et sont à placer dans la fonction main. On aura aussi besoin de stdio.h et de string.h.

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 ;

  • 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 \(0\) à \(255\) en unsigned (de \(-128\) à \(127\) sinon) ;
    • short : pour des valeurs sur \(N=16\) bits, 2 octets, donc de \(0\) à \(2^{16}-1\) en unsigned ;
    • int : pour des valeurs sur \(N=32\) bits, donc 4 octets, donc de \(0\) à \(2^{32}-1\) en unsigned ;
    • long : pour des valeurs sur \(N=64\) bits, donc 8 octets, donc de \(0\) à \(2^{64}-1\) en unsigned.

    En version signée, un type sur \(N\) bits va de \(-2^{N-1}\) à \(2^{N-1}-1\).

Dans le doute, on peut connaître la taille en nombre d'octets en utilisant sizeof : sizeof(long) vaut 8.

Il est aussi possible d'utiliser des types explicites comme int32_t ou int64_t (dans stdint.h).

Question 1

Écrire une fonction void vers_binaire(unsigned int x, unsigned char b[]). 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).

Tests :

unsigned char b[32];
unsigned char out[] = { 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1,
                        1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
vers_binaire(123457, b);
for(int i = 0; i < 32; i++)
{
    assert(b[i] == out[i]);
}
vers_binaire(4294967295, b);
for(int i = 0; i < 32; i++)
{
    assert(b[i] == 1);
}
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 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.

Tests :

unsigned char b[] = { 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1,
                      1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
assert(depuis_binaire(b) == 123457);
unsigned char c[32];
for (int i = 0; i < 32; i++) c[i] = 1;
assert(depuis_binaire(c) == 4294967295);
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;
}

Retour sur les chaînes

On rappelle qu'une chaîne de caractères en C est juste un tableau de char. Les char sont des valeurs entières sur un octet (8 bits). En pratique, on ne s'intéressera pas à la valeur entière mais uniquement à leur représentation sous forme de caractère, donc on écrira 'a' et pas 97 bien que ce soit la même valeur : 'a' == 97 est vrai.

On ne considère ici que les caractères ASCII dont la valeur est comprise entre 0 et 127. ATTENTION : comme les char sont limités, on ne peut pas écrire for(char i = 0; i < 128; i++) car, sur la plupart des machines où char va de \(-128\) à \(127\), la comparaison avec 128 est toujours vraie : la boucle ne termine pas.

Les chaînes finissent toutes par '\0' et donc on peut passer des chaînes en argument sans se soucier de donner leur taille grâce à ce caractère spécial. On appelle ça une sentinelle.

Pour faire une boucle dans un tableau de taille n, on écrit for(i = 0; i < n; i++) mais ici, comme on ne connaît pas n, il faut utiliser la sentinelle, par exemple en écrivant for(i = 0; s[i] != '\0'; i++).

Question 3

Écrire une fonction int longueur_chaine(char s[]) qui renvoie la longueur de la chaîne s.

Tests :

assert(longueur_chaine("test") == 4);
assert(longueur_chaine("") == 0);
Corrigé 
int longueur_chaine(char s[])
{
    int i;
    for (i = 0; s[i] != '\0'; i++)
    {
    }
    return i;
}

Cette fonction, comme d'autres sur les chaînes, est définie directement dans la bibliothèque standard du C (en-tête string.h) : c'est strlen. On pourra donc l'utiliser dans la suite pour pouvoir faire des boucles avec la taille comme dans un tableau usuel.

Il est probable que pour écrire la fonction suivante vous souhaitiez pouvoir sortir prématurément d'une boucle comme en Python. C'est également possible en C, on peut utiliser :

  • break; pour sortir de la boucle ;
  • continue; pour finir l'itération et passer à l'itération suivante.

Question 4

Écrire une fonction int recherche_motif(char s[], char m[]) qui renvoie l'indice de début de la première occurrence du motif m dans s s'il est présent, ou -1 sinon.

Tests :

char s[] = "tetututo";
assert(recherche_motif(s, "tu") == 2);
assert(recherche_motif(s, "to") == 6);
assert(recherche_motif(s, "ti") == -1);
Corrigé 
int recherche_motif(char s[], char m[])
{
    int n = strlen(s);
    int p = strlen(m);
    for (int i = 0; i <= n-p; i++)
    {
        int j;
        for (j = 0; j < p; j++)
        {
            if (s[i+j] != m[j])
            {
                break;
            }
        }
        if (j == p)
        {
            return i;
        }
    }

    return -1;
}

En sortie de la boucle sur j, on a j == p exactement quand on n'est pas sorti par le break, c'est-à-dire quand le motif est présent à l'indice i. Si le motif est plus long que la chaîne, n-p < 0 et on renvoie directement -1. Cet algorithme naïf est en \(O(np)\) dans le pire cas.

Question 5

Écrire une fonction void occurrences(char s[], int occ[]) qui renvoie dans le tableau occ, contenant 128 valeurs NON INITIALISÉES, les nombres d'occurrences de chaque caractère dans la chaîne s.

Tests :

int occ[128];
occurrences("test", occ);
for(int i = 0; i < 128; i++)
{
    if (i == 't') assert(occ[i] == 2);
    else if (i == 'e' || i == 's') assert(occ[i] == 1);
    else assert(occ[i] == 0);
}
Corrigé 
void occurrences(char s[], int occ[])
{
    for (int i = 0; i < 128; i++)
    {
        occ[i] = 0;
    }
    for (int i = 0; s[i] != '\0'; i++)
    {
        occ[(unsigned char) s[i]]++;
    }
}

La conversion en unsigned char évite un indice négatif si char est signé ; on suppose de plus que la chaîne ne contient que des caractères ASCII, sinon l'indice peut dépasser 127.

Automates de Wolfram

Présentation et premier automate

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.

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). Les huit règles (g,c,d) rightarrow c' : en haut le voisinage, en bas le nouvel état (bleu = 1).
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'\).

Question 6

Écrire une fonction 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.

Tests :

assert(regle_vois(0,0,0) == 0);
assert(regle_vois(0,0,1) == 1);
assert(regle_vois(0,1,0) == 1);
assert(regle_vois(0,1,1) == 1);
assert(regle_vois(1,0,0) == 1);
assert(regle_vois(1,0,1) == 0);
assert(regle_vois(1,1,0) == 0);
assert(regle_vois(1,1,1) == 0);
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\).

Question 7

Écrire une fonction int regle(int config) qui 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.

Tests :

int attendu[8] = { 0, 1, 1, 1, 1, 0, 0, 0 };
for (int k = 0; k < 8; k++)
{
    assert(regle(k) == attendu[k]);
}
Corrigé 
int regle(int config)
{
    if (config == 0 || config == 5 || config == 6 || config == 7)
        return 0;
    return 1;
}

Question 8

Écrire une fonction 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 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 à ' '.

Test :

char in[] =  "    ##   ## ##     #  # # #";
char out[] = "                           "; // de même longueur
suivant(in, out);
assert(strcmp(out, "   ## # ##  # #   ##### # #") == 0);
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] = ' ';
        }
    }
}

Question 9

Écrire une fonction 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.

Test :

char src[] = "toto";
char tgt[] = "abcd";
copie_chaine(tgt, src);
assert(strcmp(src, tgt) == 0);
Corrigé 
void copie_chaine(char tgt[], char src[])
{
    int n = strlen(src);
    for (int i = 0; i < n; i++)
    {
        tgt[i] = src[i];
    }
}

Question 10

Écrire une fonction 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.

Test :

char init[81];
for(int i = 0; i < 80; i++)
{
    init[i] = ' ';
}
init[80] = '\0';
char temp[81], sortie[81];
strcpy(temp, init);
strcpy(sortie, init);
init[40] = '#';
itere_regle(init, temp, sortie, 30);
assert(strcmp(sortie, "          ##  #    # ###  # ## # #  ##### #  ######  #   # ##   #  #  #         ") == 0);
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);
    }
}

Vous pouvez maintenant profiter de l'affichage des 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);
}

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

Il se trouve que la règle qu'on vient d'implémenter s'appelle la règle 30. En effet, si on construit l'entier \(\sum_{i=0}^7 \mathrm{regle}(i)\, 2^i\), où \(\mathrm{regle}(i)\) a été définie au-dessus, on obtient l'entier :

\[ 0 \times 128 + 0 \times 64 + 0 \times 32 + 1 \times 16 + 1 \times 8 + 1 \times 4 + 1 \times 2 + 0 \times 1 = 30 \]

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 11

Écrire une fonction 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.

Tests :

assert(regle_gen(30, 2) == 1);
assert(regle_gen(188, 6) == 0);
assert(regle_gen(188, 7) == 1);
assert(regle_gen(188, 2) == 1);
assert(regle_gen(188, 3) == 1);
Corrigé 
int regle_gen(int gen, int config)
{
    unsigned char r[32];
    vers_binaire(gen, r);
    return r[config];
}

Question 12

Écrire une fonction void suivant_gen(int gen, char in[], char out[]) qui fait comme suivant mais en appliquant la règle gen.

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

Tests :

char in[] =  "    ##   ## ##     #  # # #";
char out[] = "                           "; // de même longueur
suivant_gen(30, in, out);
assert(strcmp(out, "   ## # ##  # #   ##### # #") == 0);
suivant_gen(188, in, out);
assert(strcmp(out, "    # #  # ## #    ## #####") == 0);
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 13

Écrire une fonction void itere_regle_gen(int gen, char depart[], char temp[], char sortie[], int iterations) qui fait comme itere_regle mais en appliquant suivant_gen.

Tests (avec init, temp et sortie comme dans le test de la question 10) :

itere_regle_gen(30, init, temp, sortie, 30);
assert(strcmp(sortie, "          ##  #    # ###  # ## # #  ##### #  ######  #   # ##   #  #  #         ") == 0);
itere_regle_gen(188, init, temp, sortie, 30);
assert(strcmp(sortie, "                                        # ### ### ### ### ### ### ### #         ") == 0);
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);
    }
}

Dernière étape : savourez en affichant les 256 règles sur 30 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 < 256; i++)
{
    printf("Règle %d\n", i);
    for(int j = 0; j < 30; j++)
    {
        itere_regle_gen(i, init, temp, sortie, j);
        printf("%s\n", sortie);
    }
    printf("\n");
}