Aller au contenu

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

Exercice 1

On souhaite ici écrire une fonction fusion qui permet, étant donné 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.

Question 1. Écrire la fonction fusion.

void fusion(int t1[], int n1, int t2[], int n2, int tf[])
{
    // t1 contient n1 éléments, t2 contient n2 éléments
    // et tf contient n1+n2 éléments indéterminés
}
Corrigé 
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++;
        }
    }
}

Tests :

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};
assert(memcmp(t, tres, sizeof(int) * 9) == 0);

Question 2. Prouver la correction de la fonction précédente. Il faudra non seulement s'assurer que le tableau final est trié, mais aussi qu'il contient exactement les éléments de t1 et de t2.

Corrigé

On va noter ici \(N = n_1+n_2\) et \(t[i..j]\) les éléments de \(t\) aux indices entre \(i\) et \(j\). On note aussi \(t1[n_1] = t2[n_2] = +\infty\).

On va prouver l'invariant

\[ I(i,a,b) = \mathrm{trie}(i) \wedge \mathrm{min12}(i,a,b) \wedge \mathrm{memes}(i,a,b) \wedge i = a + b \wedge a \le n_1 \wedge b \le n_2 \]

où \(\mathrm{trie}(i)\) signifie que \(tf[0..i-1]\) est trié, \(\mathrm{min12}(i,a,b)\) signifie que \(\forall k < i,\ tf[k] \le \min(t1[a],t2[b])\) et \(\mathrm{memes}(i,a,b)\) que \(tf[0..i-1]\) contient exactement les mêmes éléments que \(t1[0..a-1]\) et \(t2[0..b-1]\) réunis.

  • Initialisation : au départ \(i=a=b=0\) et on a donc directement \(\mathrm{trie}(0)\), \(\mathrm{min12}(0,0,0)\) et \(\mathrm{memes}(0,0,0)\) car tout est vide.
  • Hérédité : supposons \(I(i,a,b)\) vérifié au début de l'itération, avec \(i < N\). Alors :
    • Soit on est dans le premier cas car \(a < n_1\), \(b < n_2\) et \(t1[a] < t2[b]\). On va alors affecter \(t1[a]\) à \(tf[i]\), or \(\mathrm{min12}(i,a,b)\) est vérifié, donc pour \(k < i\) on a \(tf[k] \le \min(t1[a],t2[b]) = t1[a] = tf[i]\). Ainsi \(\mathrm{trie}(i+1)\) est vérifié. De plus, \(tf[i] = t1[a] \le t1[a+1]\) car \(t1\) est trié (ou \(t1[a+1] = +\infty\) si \(a+1 = n_1\)) et \(tf[i] < t2[b]\) par hypothèse. Donc on a \(\mathrm{min12}(i+1,a+1,b)\) vérifié. \(\mathrm{memes}(i+1,a+1,b)\) est vérifié directement car on a juste \(t1[a]\) comme nouvel élément et c'est celui qu'on a rajouté. Enfin, \(i+1 = (a+1) + b\) vu que \(i = a+b\), et \(a + 1 \le n_1\).
    • Soit on est dans le premier cas car \(a < n_1\) et \(b = n_2\). Il suffit de reprendre le cas précédent en ayant en tête qu'on a posé \(t2[b] = +\infty\).
    • Soit on est dans le second cas. Alors \(b < n_2\) : sinon, on aurait \(b = n_2\) et donc \(a = i - n_2 < n_1\), et on serait dans le premier cas. On a donc \(a = n_1\) ou \(t2[b] \le t1[a]\), c'est-à-dire, avec la convention \(t1[n_1] = +\infty\), \(t2[b] \le t1[a]\) dans tous les cas. Ce cas est alors symétrique des précédents en échangeant les rôles de \(t1\) et \(t2\) (et donc de \(a\) et de \(b\)).

L'invariant est bien vérifié en sortie d'itération.

Conclusion : on a \(I(N,a,b)\) en sortie, avec \(N = a+b\), \(a \le n_1\) et \(b \le n_2\). Comme \(N = n_1 + n_2\), forcément \(a = n_1\) et \(b = n_2\). Ainsi \(tf\) est trié et il contient les mêmes éléments que \(t1\) et \(t2\).

Question 3. Déterminer la complexité de cette fonction.

Corrigé

Pas de difficulté ici, on a une boucle for qui effectue un nombre constant d'opérations élémentaires lors de chacune de ses \(N\) étapes. On est donc en \(O(N) = O(n_1+n_2)\).

Exercice 2

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 \(N-1\) où \(N\) est fixé. L'idée est alors, dans un tableau de taille \(N\), 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 en \(O(N+n) = O(n)\) en supposant \(N\) constant, où \(n\) est la taille du tableau à trier.

Question 4. Écrire la fonction occurrences.

void occurrences(int t[], int n, int occ[], int N)
{
    // t est un tableau de n entiers
    // occ est un tableau de N entiers dont les valeurs sont
    // non initialisées.
    // on demande de placer dans occ[i] le nombre d'occurrences de i dans t
}
Corrigé 
void occurrences(int t[], int n, int occ[], int N)
{
    for(int i = 0; i < N; i++)
        occ[i] = 0;
    for(int i = 0; i < n; i++)
        occ[t[i]]++;
}

Tests :

int t[] = { 0, 1, 2, 3, 0, 1, 2, 1 };
int occ[4];
occurrences(t, 8, occ, 4);
int res[] = { 2, 3, 2, 1 };
assert(memcmp(occ, res, sizeof(int) * 4) == 0);

Question 5. Écrire la fonction comptage.

#define N 100 // on définit ici une constante N qui vaut 100,
              // ce qui permet de faire un tableau t[N]

void comptage(int t[], int n)
{
    // t contient n entiers entre 0 et N-1
    // trier t par comptage
}
Corrigé 
void comptage(int t[], int n)
{
    int occ[N];
    occurrences(t, n, occ, N);
    int a = 0;
    for(int i = 0; i < N; i++)
    {
        for(int k = 0; k < occ[i]; k++)
        {
            t[a] = i;
            a++;
        }
    }
}

Tests :

int t[] = { 0, 1, 2, 3, 0, 1, 2, 1 };
comptage(t, 8);
int res[] = { 0, 0, 1, 1, 1, 2, 2, 3 };
assert(memcmp(t, res, sizeof(int) * 8) == 0);

Question 6. Quelle est la complexité de ce tri ? Que pensez-vous de sa pertinence si on avait fixé \(2^{31}\) comme valeur de \(N\) ?

Corrigé

Le calcul du tableau des occurrences est en \(O(N+n) = O(n)\) en supposant \(N\) constant. Le tri lui-même crée ce tableau puis effectue une boucle en \(O(N+n)\) : \(N\) pour le premier for (rien que pour gérer les indices) et \(n\) pour la somme de toutes les itérations du second for. Donc le tri est globalement en \(O(N+n) =O(n)\).

Avec une très grande valeur de \(N\), il n'est plus pertinent de considérer \(N\) constant car \(n\) est sûrement d'un ordre de grandeur plus petit. En fait, \(N\) ne doit pas être d'un ordre de grandeur plus grand que \(n\) pour que ce tri soit efficace. De plus, pour une grande valeur de \(N\), le compromis espace-temps est peu favorable : on ne va pas allouer 8 Go (\(2^{31}\) entiers de 4 octets) pour trier un tableau !

Ce tri est donc bien plus adapté pour des petites valeurs de \(N\). Il reste alors très efficace et souvent plus pertinent qu'un tri en \(O(n \log n)\) comme le tri fusion.

Arbres dans des tableaux

On va considérer ici une structure arborescente stockée dans un tableau. Cet exercice est contextualisé en gestion d'épicerie...

Le précédent propriétaire du magasin de Gérard avait la réputation d'avoir absolument tout dans sa réserve. En découvrant celle-ci, Gérard comprend vite d'où il tient cette réputation : celle-ci est remplie d'une quantité impressionnante de produits divers et variés, accumulés au fil des années. Comme cette réserve attire des clients de toute la région, lassés du manque de choix des grandes surfaces classiques, Gérard a bien l'intention de continuer à fournir ce service. Contrairement à son prédécesseur qui en connaissait le moindre recoin, Gérard n'a cependant aucune idée des produits disponibles dans cette réserve et encore moins de leur position. Avec l'aide de quelques jeunes du quartier embauchés pour les vacances, il décide de réorganiser cette réserve et d'utiliser son système de codes-barres et son ordinateur, pour faciliter la recherche des produits demandés par ses clients.

Il s'est procuré une bonne quantité de cartons et boîtes de toutes tailles, dans lesquels il va placer les divers types d'objets. Tous les objets d'un même type sont placés dans une même boîte et les boîtes contenant des objets similaires sont elles-mêmes placées dans d'autres boîtes, ou cartons.

Ce système ne fonctionne que parce que Gérard a eu la bonne idée d'attribuer un code-barre à chaque boîte et chaque carton et qu'il a noté dans quel récipient est stocké chaque objet, boîte, ou carton. Gérard a également numéroté ses étagères, qu'on considérera comme des récipients, au même titre que les boîtes et cartons.

Dans les questions suivantes, les objets (produits ou récipients) ont des codes \(1, 2, \dots, n\) et l'inventaire de Gérard est un int inventaire[] de taille \(n\) où inventaire[k-1] donne le code du récipient où se trouve l'objet de code k. La valeur 0 indique que l'objet est directement posé dans la réserve.

Gérard a besoin de vous pour exploiter toutes ces données.

Question 7. Gérard vous demande pour commencer d'écrire un programme qui décrit précisément où se trouve un objet dont on fournit le code d'identification.

void cherche(int inventaire[], int objet, int chemin[], int *longueur)
{
    // ici inventaire décrit les objets de Gérard
    // objet est le code de l'objet à chercher
    // on place le chemin pour y accéder dans chemin et sa longueur dans
    // longueur, passé par pointeur
    // on suppose que chemin est un tableau contenant a priori assez de cases
    // pour tous les chemins
}
Corrigé 
void cherche(int inventaire[], int objet, int chemin[], int *longueur)
{
    *longueur = 0;
    while(objet != 0)
    {
        chemin[*longueur] = objet;
        objet = inventaire[objet-1];
        *longueur = *longueur + 1;
    }
}

Tests :

int inv[] = { 3, 3, 7, 3, 6, 7, 0, 0 };
int chemin[10];
int longueur;
cherche(inv, 1, chemin, &longueur);
int res1[] = {1, 3, 7};
assert(memcmp(chemin, res1, sizeof(int)*3) == 0 && longueur == 3);
cherche(inv, 5, chemin, &longueur);
int res2[] = {5, 6, 7};
assert(memcmp(chemin, res2, sizeof(int)*3) == 0 && longueur == 3);
cherche(inv, 8, chemin, &longueur);
int res3[] = {8};
assert(memcmp(chemin, res3, sizeof(int)) == 0 && longueur == 1);

Question 8. Gérard aime présenter les choses joliment, y compris les instructions imprimées par l'ordinateur indiquant comment retrouver un produit. Il souhaite peaufiner la mise en page des documents où il imprimera un certain nombre de ces listes. Il n'a cependant aucune idée de la taille maximale que peut avoir une de ces listes, ni de l'espace qu'il doit réserver à chacune dans son modèle de document.

Vous devez écrire un programme qui détermine le plus grand nombre d'étapes nécessaire pour retrouver un produit de son stock. L'organisation des produits dans les récipients est décrite de la même manière que pour le problème précédent.

int max_etapes(int inventaire[], int taille_inventaire);
Corrigé

Les codes des objets vont de \(1\) à taille_inventaire : il faut bien inclure le dernier objet dans la boucle.

int max_etapes(int inventaire[], int taille_inventaire)
{
    int longueur_max = 0;
    for(int i = 1; i <= taille_inventaire; i++)
    {
        int objet = i;
        int l = 0;
        while(objet != 0)
        {
            objet = inventaire[objet-1];
            l++;
        }

        if (l > longueur_max)
            longueur_max = l;
    }

    return longueur_max;
}

Tests :

int inv[] = { 3, 3, 7, 3, 6, 7, 0, 0 };
assert(max_etapes(inv, 8) == 3);
int inv2[] = { 0, 1, 2 }; // 3 est dans 2 qui est dans 1
assert(max_etapes(inv2, 3) == 3);

Question 9. Gérard se pose souvent des questions sur son choix d'organisation des produits dans son stock. Il lui semble logique que certains produits similaires soient stockés à peu près au même endroit. Régulièrement, votre ami choisit deux produits qui lui semblent proches et interroge l'ordinateur pour déterminer où ils se trouvent. Il vérifie alors s'ils se trouvent dans un même carton, que ce soit directement ou à l'intérieur de cartons placés eux-mêmes au même endroit.

Gérard vous demande d'écrire un programme pour l'aider dans cette tâche : à partir de deux codes d'objets (produits ou récipients) donnés, votre programme doit renvoyer le récipient le plus petit qui contienne les deux objets fournis (ou 0 si c'est la réserve elle-même). Un récipient est toujours plus grand que chacun des récipients ou objets qu'il contient (plus grand en taille uniquement, ceci est indépendant de la valeur des codes). On considère qu'un objet se contient lui-même.

#define N 100

int recipient_commun(int inventaire[], int objet1, int objet2)
{
    // ici inventaire décrit les objets de Gérard
    // objet1 et objet2 sont les deux objets dont on cherche le récipient commun
    // on pourra supposer que le nombre maximum d'objets est majoré par N
}
Corrigé

On remonte depuis objet2 jusqu'à rencontrer un récipient présent sur le chemin de objet1.

int recipient_commun(int inventaire[], int objet1, int objet2)
{
    int chemin[N];
    int l;
    cherche(inventaire, objet1, chemin, &l);
    while(objet2 != 0)
    {
        for(int i = 0; i < l; i++)
            if (chemin[i] == objet2)
                return objet2;
        objet2 = inventaire[objet2-1];
    }

    return 0;
}

Tests :

int inv[] = { 3, 3, 7, 3, 6, 7, 0, 0 };
assert(recipient_commun(inv, 1, 5) == 7);
assert(recipient_commun(inv, 5, 7) == 7);
assert(recipient_commun(inv, 2, 8) == 0);