نموذج مباراة ولوج السنة الثانية من سلك مهندسي الدولة - المعهد الوطني للبريد والمواصلات (INPT) 2010 - اختبار المعلوميات

Ce modèle est l'épreuve d'informatique du concours d'accès en 2e année du cycle d'ingénieurs d'État de l'INPT, session du 13 juillet 2010. Durée : 1 h 30. Un problème en six questions (2 + 1 + 3 + 4 + 5 + 5 = 20 points) sur la manipulation de fragments d'ADN codés par une chaîne « brin1#brin2 », à programmer en C ou en Pascal, sans autre fonction prédéfinie que les fonctions de lecture/écriture (d'où la fonction longueur écrite à la main). Voici une correction proposée en C.

💡 Commencez par écrire les petites fonctions utilitaires (longueur, complement, insertion/suppression d'un caractère) : elles rendent les questions 5 et 6 presque immédiates, et le jury apprécie la décomposition.

Fonctions utilitaires

#include <stdio.h>

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

int estBase(char c) { return c == 'A' || c == 'C' || c == 'G' || c == 'T'; }

char complement(char b)
{
    if (b == 'A') return 'T';
    if (b == 'T') return 'A';
    if (b == 'C') return 'G';
    return 'C';                       /* b == 'G' */
}

Question 1 — valide (2 points)

Une chaîne valide a la forme brin1 # brin2 avec deux brins de même longueur L ≥ 1 : sa longueur n = 2L + 1 est impaire, le caractère d'indice L est '#', le premier brin ne contient que A, C, G, T, et chaque base du second brin est le complément de la base de même rang du premier (A–T, C–G). Ces tests écartent aussi un second '#' ou un caractère parasite dans le second brin.

int valide(char ch[])
{
    int n = longueur(ch), L = (n - 1) / 2, i;
    if (n < 3 || n % 2 == 0 || ch[L] != '#') return 0;   /* L bases, '#', L bases */
    for (i = 0; i < L; i++)
        if (!estBase(ch[i]) || ch[L + 1 + i] != complement(ch[i])) return 0;
    return 1;
}

(L'énoncé précise que chaque base « apparaît une ou plusieurs fois dans un brin » ; c'est une description du modèle biologique. Si on la lit comme une règle de validité, il suffit d'ajouter un comptage des quatre bases sur le premier brin et d'exiger que chacune soit présente.)

Question 2 — nombreBases (1 point)

Le fragment étant valide, tous ses caractères sauf '#' sont des bases : 2L = n − 1 (18 pour l'exemple).

int nombreBases(char f[])
{
    return longueur(f) - 1;           /* tous les caracteres sauf '#' */
}

Question 3 — pourcentageMaxBases (3 points)

On compte chaque base dans les deux brins, on cherche le maximum puis on affiche toutes les bases qui l'atteignent (il peut y en avoir plusieurs : par complémentarité, A et T ont toujours le même effectif, de même C et G). Le pourcentage est arrondi à l'entier le plus proche. Exemple : A = 5, T = 5, C = 4, G = 4 sur 18 bases, 5/18 ≈ 27,8 % → affichage « A : 28 %; T : 28 % ».

void pourcentageMaxBases(char f[])
{
    char b[4] = {'A', 'C', 'G', 'T'};
    int nb[4] = {0, 0, 0, 0}, i, k, max = 0, total = nombreBases(f), premier = 1;
    for (i = 0; f[i] != '\0'; i++)
        for (k = 0; k < 4; k++)
            if (f[i] == b[k]) nb[k]++;
    for (k = 0; k < 4; k++)
        if (nb[k] > max) max = nb[k];
    for (k = 0; k < 4; k++)
        if (nb[k] == max) {
            if (!premier) printf("; ");
            printf("%c : %d %%", b[k], (100 * nb[k] + total / 2) / total);  /* arrondi */
            premier = 0;
        }
    printf("\n");
}

Question 4 — contientSousSequence (4 points)

On cherche la sous-séquence dans chaque brin séparément, sans jamais chevaucher le séparateur '#' (borne fin).

/* 1 si s apparait dans f a partir de la position debut, sans franchir fin */
int apparaitEn(char f[], int debut, int fin, char s[])
{
    int j = 0;
    while (s[j] != '\0') {
        if (debut + j >= fin || f[debut + j] != s[j]) return 0;
        j++;
    }
    return 1;
}

int contientSousSequence(char f[], char s[])
{
    int n = longueur(f), L = (n - 1) / 2, i;
    if (longueur(s) == 0) return 1;
    for (i = 0; i < L; i++)                       /* premier brin : indices 0..L-1 */
        if (apparaitEn(f, i, L, s)) return 1;
    for (i = L + 1; i < n; i++)                   /* second brin : indices L+1..n-1 */
        if (apparaitEn(f, i, n, s)) return 1;
    return 0;
}

Question 5 — insererBase (5 points)

Pour que le fragment reste valide, on insère la base à la position n du premier brin et sa base complémentaire à la même position du second brin. On numérote les positions de 1 à L + 1 dans le premier brin (L + 1 = ajout en fin de brin) ; la fonction échoue (retour 0) si la base n'est pas A, C, G ou T ou si n est hors bornes. Après la première insertion, le '#' est en L + 1 et le second brin commence en L + 2. Le tableau passé doit disposer de deux cases libres.

/* insere le caractere c a l'indice q (decalage vers la droite, '\0' compris) */
void insererCar(char f[], int q, char c)
{
    int i;
    for (i = longueur(f); i >= q; i--) f[i + 1] = f[i];
    f[q] = c;
}

/* n : position (1 a L+1) dans le premier brin ; le tableau f doit avoir 2 cases libres */
int insererBase(char base, char f[], int n)
{
    int L = (longueur(f) - 1) / 2;
    if (!estBase(base) || n < 1 || n > L + 1) return 0;
    insererCar(f, n - 1, base);                   /* premier brin   */
    insererCar(f, L + 2 + (n - 1), complement(base)); /* second brin : '#' est maintenant en L+1 */
    return 1;
}

Contrôle : insererBase('C', "AGGAGTCTA#TCCTCAGAT", 5) donne "AGGACGTCTA#TCCTGCAGAT", fragment valide.

Question 6 — supprimerBase (5 points)

Symétriquement, on supprime la base de rang n du premier brin et celle de même rang du second (en commençant par le second, d'indice plus grand, pour ne pas décaler l'autre). On refuse la suppression si n est hors de [1, L] ou si les brins n'ont qu'une base (ils deviendraient vides, fragment invalide).

/* supprime le caractere d'indice q */
void supprimerCar(char f[], int q)
{
    int i;
    for (i = q; f[i] != '\0'; i++) f[i] = f[i + 1];
}

/* n : position (1 a L) dans le premier brin */
int supprimerBase(int n, char f[])
{
    int L = (longueur(f) - 1) / 2;
    if (n < 1 || n > L || L == 1) return 0;       /* chaque brin doit rester non vide */
    supprimerCar(f, L + 1 + (n - 1));             /* d'abord le second brin (indice plus grand) */
    supprimerCar(f, n - 1);
    return 1;
}

Contrôle : supprimerBase(1, "AGGAGTCTA#TCCTCAGAT") donne "GGAGTCTA#CCTCAGAT", fragment valide.