Aller au contenu

Les fonctions sont à écrire en C. Chaque question est suivie de tests qui doivent passer sans erreur.

Exercice 1

Question 1. Écrire une fonction swap qui prend en entrée, dans cet ordre, un tableau d'entiers et deux indices i et j, et qui 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;
}

Tests :

int t1[] = { 1, 2, 3 };
swap(t1, 1, 2);
assert(t1[0] == 1 && t1[1] == 3 && t1[2] == 2);

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 qui 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);
    }
}

Tests :

int t1[] = { 1, 2, 3 };
renverse(t1, 3);
assert(t1[0] == 3 && t1[1] == 2 && t1[2] == 1);
int t2[] = { 1, 2, 3, 4, 5, 6 };
renverse(t2, 6);
for (int i = 0; i < 6; i++)
    assert(t2[i] == 6-i);

Question 3. Prouver la correction de votre programme 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.

Attention : on fera attention à la parité du nombre d'éléments.

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

\[ 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 le tableau n'a pas encore été modifié.
  • Hérédité : si on a \(I(i)\) en début d'itération, avec \(i < \lfloor n/2 \rfloor\), on a \(i < n-1-i\) et on va réaliser l'échange entre \(t_i = a_i\) et \(t_{n-1-i} = a_{n-1-i}\) (par l'invariant). On va donc 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\) est pair, cela couvre tous les indices. Il n'y a qu'un élément 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é, ce qui est bien attendu car \(n-1-p = p\). On a bien renversé le tableau dans tous les cas.

Exercice 2

Question 4. Écrire une fonction qui, étant donné un tableau d'entiers et sa taille, effectue un traitement en place sur le tableau de 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.

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 renvoie -1 s'il n'y en a pas), et decale qui prend deux indices i et j et effectue les affectations j-1 -> j, j-2 -> j-1, ..., i+1 -> i+2, i -> i+1 dans le tableau pour pouvoir placer un élément en i.

void pairs_devant(int *tab, int nb);
Corrigé

Ici, les deux fonctions intermédiaires sont écrites directement dans la boucle principale.

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;
    }
}

Tests :

int t[] = { 1, 2, 3, 4 };
pairs_devant(t, 4);
assert(t[0] == 2 && t[1] == 4 && t[2] == 1 && t[3] == 3);
int t2[] = { 1, 3 };
pairs_devant(t2, 2);
assert(t2[0] == 1 && t2[1] == 3);
int t3[] = { 5, 4, 1, 2, 3 };
pairs_devant(t3, 5);
assert(t3[0] == 4 && t3[1] == 2 && t3[2] == 5 && t3[3] == 1 && t3[4] == 3);

Exercice 3

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 digraphes.

Ce chiffre utilise une table de 5 par 5 contenant chaque lettre de l'alphabet anglais 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 digraphes (groupes de deux lettres) : par exemple, Hello World devient HE LL OW OR LD. Ensuite, on applique les règles suivantes à chaque digraphe 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 (on ajoute un X après la lettre restante dans le second cas), et on chiffre le digraphe obtenu. Ainsi LL est chiffré comme LX.
  • 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 ci-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 ni sur la même rangée ni sur la même colonne, elles sont les sommets d'un rectangle dans la table, on les chiffre alors avec les deux 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.

La table précédente pourra être stockée sous la forme de la chaîne "PLAYFIREXMBCDGHJKNOSTUVWZ" (les rangées les unes à la suite des autres).

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, car cela ferait boucler la première règle.

Question 5. Écrire les deux fonctions suivantes.

void car_vers_position(char *cle, char c, int *row, int *col)
{
    // prend un caractère c présent dans la clé et renvoie
    // son numéro de rangée dans row et son numéro de colonne dans col
    // en les passant par pointeurs
}

char position_vers_car(char *cle, int row, int col)
{
    // renvoie le caractère dans la table cle sur la rangée row et
    // la colonne col
}
Corrigé 
void car_vers_position(char *cle, char c, int *row, int *col)
{
    int i;
    for (i = 0; i < 25; i++)
    {
        if (cle[i] == c)
            break;
    }
    *row = i / 5;
    *col = i % 5;
}

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

Tests :

char cle[] = "PLAYFIREXMBCDGHJKNOSTUVWZ";
int r, c;
car_vers_position(cle, 'K', &r, &c);
assert(r == 3 && c == 1);
car_vers_position(cle, 'E', &r, &c);
assert(r == 1 && c == 2);
assert(position_vers_car(cle, 1, 2) == 'E');

Question 6. Écrire une fonction qui réalise le chiffrement de s avec la clé cle donnée sous forme d'une chaîne comme ci-dessus. La chaîne de sortie contient assez de place pour stocker le message chiffré. Vous devrez bien rajouter un '\0' à la fin.

void chiffre(char *cle, char *s, char *sortie);
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, y1, x2, y2;
        car_vers_position(cle, c1, &x1, &y1);
        car_vers_position(cle, c2, &x2, &y2);

        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';
}

Tests :

char cle[] = "PLAYFIREXMBCDGHJKNOSTUVWZ";
char s[] = "HIDETHEGOLDINTHETREEESTUMP";
char o[30];
chiffre(cle, s, o);
assert(strcmp(o, "BMNDZBXDKYBEJVDMUIXMMNUVIF") == 0);
char cle2[] = "THEMAGICKYBDFJLNOPRSUVWXZ";
char s2[] = "ILOVEPROGRAMMINGCOMPETITION";
chiffre(cle2, s2, o);
assert(strcmp(o, "YDVHCWSPKNTAHKUBIPERMHGHDVRU") == 0);