L'examen peut être fait sur Repl ou sur votre ordinateur avec un compilateur C. Le rendu se fera par mail à l'adresse exam@de-falco.fr sous la forme d'un fichier C nommé nom.c, avec votre nom (et pas le prénom) sans accents, quitte à abréger mais avec le bon préfixe, contenant vos fonctions dans l'ordre des questions.

On vous donne des exemples de tests pour vérifier vos fonctions : ils ne sont pas exhaustifs, vos fonctions seront vérifiées sur un jeu de tests plus grand.

Vous pouvez laisser vos tests dans le rendu, mais vos fonctions doivent nécessairement avoir le prototype donné dans le sujet et pas un autre !

Une somme

Écrire une fonction de prototype

int somme(int n);

qui renvoie pour \(n \ge 0\), la valeur de \(S_n = \sum_{k=1}^{n} k (k+2)\).

Réponse

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

Une suite

Écrire une fonction de prototype

int suite(int n);

qui renvoie \(u_n\) pour \(n \ge 0\), où \((u_n)_{n \in \N}\) est la suite définie par :

\[ u_0 = 1, \quad \forall n \ge 0, \; u_{n+1} = \begin{cases} 2 u_n + 1 & \text{ si } u_n \text{ pair } \\ 3 - u_n & \text{ sinon } \end{cases} \]

On a ainsi \(u_{10} = 45\).

Réponse

int suite(int n)
{
    int u = 1;
    for(int i = 1; i <= n; i++)
    {
        if (u % 2 == 0)
            u = 2*u+1;
        else
            u = 3-u;
    }
    return u;
}

Écrire une fonction de prototype

int compteneg(int n);

qui renvoie le nombre de \(u_k\) pour \(0 \le k \le n\) tels que \(u_k < 0\).

Pour \(n = 10\), cette fonction renvoie 4.

Réponse

int compteneg(int n)
{
    int c = 0;
    for(int i = 0; i <= n; i++)
        if (suite(i) < 0)
            c++;
    return c;
}

Tri par comptage

On considère ici une méthode de tri dite par comptage. On va supposer que les tableaux qu'on cherche à trier ne contiennent que des entiers entre 0 et 99.

L'idée est alors, dans un tableau de taille 100, de compter le nombre d'occurrences de chacun des entiers.

Ensuite, on peut se servir de ce tableau d'occurrences pour en déduire le tableau trié.

On demande à ce que la complexité soit linéaire en le nombre d'éléments, c'est-à-dire que le nombre d'opérations élémentaires soit proportionnel au nombre d'éléments.

Occurrences

Écrire une fonction de prototype

void occurrences(int t[], int n, int occ[]);

qui prend en entrée t un tableau de n entiers appartenant à \(\range{0}{99}\), occ un tableau de 100 entiers dont les valeurs sont non initialisées et qu'on utilisera uniquement pour écrire dedans.

Cette fonction doit alors placer, pour tout \(i \in \range{0}{99}\), dans occ[i] le nombre d'occurrences de l'entier i dans t.

bool test_occ()
{
    int t[] = { 0, 1, 2, 3, 0, 1, 2, 1 };
    int occ[100];
    occurrences(t, 8, occ);
    int res[] = { 2, 3, 2, 1 };
    bool valide = true;
    for(int i = 0; i < 100; i++)
    {
        if(i < 4)
            valide = valide && occ[i] == res[i];
        else
            valide = valide && occ[i] == 0;
    }
    return valide;
}

Réponse

void occurrences(int t[], int n, int occ[])
{
    for(int i = 0; i < 100; i++)
        occ[i] = 0;
    for(int i = 0; i < n; i++)
        occ[t[i]]++;
}

Le tri

L'idée pour trier un tableau 1, 3, 0, 1, 3, 1 c'est de se rendre compte qu'il contient :

• 1 fois la valeur 0 et donc que le tableau trié doit commencer par 0
• 3 fois la valeur 1 et donc qu'ensuite le tableau trié doit se poursuivre par 0, 1, 1, 1
• 0 fois la valeur 2 donc on ne la met pas dans le tableau trié
• 2 fois la valeur 3 et donc on les rajoute 0, 1, 1, 1, 3, 3
• 0 fois de toute autre valeur, donc c'est fini le tableau trié est 0, 1, 1, 1, 3, 3

Écrire une fonction de prototype

void comptage(int t[], int n);

qui trie en place le tableau t ainsi. Note, il faudra surement définir des tableaux intermédiaires, mais cela ne pose pas de problèmes si on connait leur taille à la compilation.

Par contre, il est impossible d'écrire int temp[n]; car n est une variable. Si vous voulez faire ça, c'est que vous faites fausse route.

Note cette fonction va naturellement appeler la fonction occurrences.

bool test_comptage()
{
    int t[] = { 0, 1, 2, 3, 0, 1, 2, 1 };
    comptage(t, 8);
    int res[] = { 0, 0, 1, 1, 1, 2, 2, 3 };
    bool valide = true;
    for(int i = 0; i < 8; i++)
    {
        valide = valide && t[i] == res[i];
    }
    return valide;
}

Réponse

void comptage(int t[], int n)
{
    int occ[100];
    occurrences(t, n, occ);
    int a = 0;
    for(int i = 0; i < 100; i++)
    {
        for(int k = 0; k < occ[i]; k++)
        {
            t[a] = i;
            a++;
        }
    }
}

Chaine

Rappel on peut utiliser strlen(s) pour calculer la longueur de s. Cette fonction est déclarée dans string.h.

Plus longue plage minuscule

Écrire une fonction de prototype

int plagemin(char *s);

qui renvoie le plus grand entier k tel qu'il existe k caractères consécutifs en minuscule dans s.

Exemple :

• s = "totoTtotou" on renvoie 5 qui correspond à "totou"
• s = "AtA" on renvoie 1
• s = "AAB" on renvoie 0

bool test_plagemin()
{
    bool valide = true;
    valide = valide && plagemin("totoTtotou") == 5;
    valide = valide && plagemin("AtA") == 1;
    valide = valide && plagemin("AAB") == 0;
    return valide;
}

Réponse

int plagemin(char *s)
{
    int k = 0;
    bool plage = false;
    int cur = 0;
    for(int i = 0; i < strlen(s); i++)
    {
        char c = s[i];
        bool minus = 'a' <= c && c <= 'z';
        if (minus)
        {
            if(!plage)
            {
                cur = 1;
                plage = true;
            } else
                cur++;
        } else {
            if(plage) {
                if (cur > k)
                    k = cur;
                plage = false;
            }
        }
    }
    if(plage && cur > k)
        k = cur;
    return k;
}

Recherche linéaire

Écrire une fonction de prototype

int recherche(char *s, char* motif);

qui prend en entrée deux chaines, une chaine motif correspondant à une chaine que l'on va chercher dans une autre chaine s, et qui renvoie l'indice de la première occurrence de motif dans s quand il est présent et -1 sinon.

Exemples :

• s = "tototatota", motif = "tota" le motif est présent deux fois à l'indice 2 et à l'indice 6, on renvoie donc la valeur 2.
• s = "tototatota", motif = "tata" le motif n'est pas présent on renvoie -1
• s = "toto", motif = "tototo" pas présent non plus donc -1
• s = "test", motif = "" motif présent tout de suite, on renvoie 0

bool test_recherche()
{
    bool valide = true;
    valide = valide && recherche("tototatota", "tota") == 2;
    valide = valide && recherche("tototatota", "tata") == -1;
    valide = valide && recherche("toto", "tototo") == -1;
    valide = valide && recherche("test", "") == 0;
    return valide;
}

Réponse

int recherche(char *s, char *motif)
{
    int n = strlen(s);
    int p = strlen(motif);
    for(int i = 0; i <= n-p; i++)
    {
        bool flag = true;
        for(int j = 0; j < p; j++)
            flag = flag && s[i+j] ==motif[j];
        if (flag)
            return i;
    }
    return -1;
}

Fusion de deux tableaux

On souhaite ici écrire une fonction fusion de prototype

void fusion(int t1[], int n1, int t2[], int n2, int tf[]);

qui permet, étant donnés deux tableaux triés t1 et t2 de construire un tableau tf contenant les éléments de t1 et de t2 mais globalement triés.

Ainsi, si t1 contient 0, 1, 4, 6 et t2 contient 1, 2, 3, 4, 5, le tableau tf contiendra 0, 1, 1, 2, 3, 4, 4, 5, 6.

On suppose que t1 contient n1 éléments, t2 contient n2 éléments et tf contient n1+n2 éléments dont la valeur est indéterminée (on considère qu'on a juste le droit d'écrire dans tf).

bool test_fusion()
{
    int t1[] = { 0, 1, 4, 6 };
    int t2[] = { 1, 2, 3, 4, 5 };
    int t[9];
    fusion(t1, 4, t2, 5, t);
    int tres[] = {0, 1, 1, 2, 3, 4, 4, 5, 6};
    bool valide = true;
    for(int i = 0; i < 9; i++) {
        if (tres[i] != t[i]) {
            valide = false;
        }
    }
    return valide;
}

Réponse

void fusion(int t1[], int n1, int t2[], int n2, int tf[])
{
    int a = 0;
    int b = 0;
    for(int i = 0; i < n1 + n2; i++)
    {
        if (a < n1 && (b == n2 || t1[a] < t2[b]))
        {
            tf[i] = t1[a];
            a++;
        }
        else
        {
            tf[i] = t2[b];
            b++;
        }
    }
}