TP 1 : Révisions de MP2I

Ce TP est à effectuer en C, sous Visual Code. Vous pouvez utiliser le Codespace GitHub ou votre ordinateur personnel.
On pensera à tester les fonctions.

On rappelle la commande pour compiler, qui créé un fichier a.out :

gcc nom_fichier.c

Puis, pour exécuter :

./a.out

On peut faire les deux en une seule commande :

gcc nom_fichier.c && ./a.out

Si vous avez une boucle infinie (le terminal qui ne répond pas) : Ctrl + C

Recherche d'un mot (facteur) dans un texte

Exercice

Écrire une fonction naïve int recherche(char *m, char *texte) qui renvoie l'indice de la première occurrence du mot m dans texte ou -1 si le mot n'est pas présent. Le mot doit apparaître comme facteur, c'est-à-dire de façon consécutive.

Indice

On pourra utiliser int strlen(char*) de string.h pour connaître la taille d'une chaîne de caractères.

#include <string.h>
#include <stdio.h>

int recherche(char* m, char* text) {
    ...
}        

int main() {
    printf("%d\n", recherche("world", "hello world!")); // affiche 6
    printf("%d\n", recherche("elo", "hello")); // affiche -1
    return 0;
}

Solution

#include <string.h>
#include <stdio.h>

int recherche(char* m, char* text) {
    int k = strlen(m);
    for(int i = 0; i < strlen(text) - k + 1; i++)
        for(int j = 0; text[i + j] == m[j]; j++)
            if(j == k - 1)
                return i;
    return -1;
}        

int main() {
    printf("%d\n", recherche("world", "hello world!"));
    printf("%d\n", recherche("elo", "hello"));
    return 0;
}

Dichotomie

On rappelle que la recherche par dichotomie d'un élément e dans un tableau trié t consiste à considérer l'élément au milieu t[m] puis :

• Si e == t[m] : on renvoie true.
• Si e < t[m] : on regarde à gauche de m.
• Si e > t[m] : on regarde à droite de m.

Exercice

Écrire une fonction dichotomie déterminant si un élément e appartient à un tableau t. On pourra utiliser soit une fonction récursive, soit une boucle while.

Indice

Version récursive

#include <stdbool.h>
#include <stdio.h>

bool dichotomie(int* t, int e, int i, int j) {
    // détermine si e apparait entre les indices i et j de t
    ...
}

int main() {
    int t[10] = {-4, -2, 0, 1, 3, 5, 7, 9, 11, 13};
    printf("%d\n", dichotomie(t, 1, 0, 10)); // 1 
    printf("%d\n", dichotomie(t, 4, 0, 10)); // 0
    printf("%d\n", dichotomie(t, 13, 0, 10)); // 1
    return 0;
}

Version itérative

#include <stdbool.h>
#include <stdio.h>

bool dichotomie(int* t, int e, int n){
    int i = 0, j = n - 1; // indices de début et de fin de l'intervalle où on cherche e
    ...
}

int main() {
    int t[10] = {-4, -2, 0, 1, 3, 5, 7, 9, 11, 13};
    printf("%d\n", dichotomie(t, 1, 10)); // 1 
    printf("%d\n", dichotomie(t, 4, 10)); // 0
    printf("%d\n", dichotomie(t, 13, 10)); // 1
    return 0;
}

Solution

#include <stdbool.h>
#include <stdio.h>

bool dichotomie(int* t, int e, int i, int j) {
    if (i > j) {
        return false;
    }
    int m = (i + j) / 2;
    if (t[m] == e) {
        return true;
    } 
    if (t[m] < e) {
        return dichotomie(t, e, m + 1, j);
    }
    return dichotomie(t, e, i, m - 1);
}

int main() {
    int t[10] = {-4, -2, 0, 1, 3, 5, 7, 9, 11, 13};
    printf("%d\n", dichotomie(t, 13, 0, 10));
    printf("%d\n", dichotomie(t, 13, 0, 9));
    return 0;
}

Liste chaînée

Exercice

1. Définir une structure list de liste chaînée contenant des entiers.
2. Écrire une fonction list *add(list *l, int e) permettant d'ajouter un élément (au début) d'une liste chaînée.
3. Écrire une fonction void print(list *l) permettant d'afficher les éléments d'une liste chaînée.
4. Écrire une fonction list *del(list *l) permettant de supprimer l'élément du début d'une liste chaînée.
5. Quelle est la structure de donnée abstraite que l'on vient d'implémenter ?

Indice

On pourra compléter :

typedef struct list {
    int elem;
    struct list *next;
} list;

list *add(list *l, int e) {
    ...
}
list *del(list *l) {
    ...
}
void print(list *l) {
    ...
}

Solution

#include <stdio.h>
#include <stdlib.h>

typedef struct list {
    int elem;
    struct list *next;
} list;

list *add(list *l, int e) { 
    list *new = malloc(sizeof(list));
    new->elem = e;
    new->next = l;
    return new;
}

void print(list *l) {
    while (l != NULL) {
        printf("%d\n", l->elem);
        l = l->next;
    }
}

list *del(list *l) {
    list *tmp = l->next;
    free(l);
    return tmp;
}
// on a implémenté une structure de pile

int main() {
    list *l = NULL;
    l = add(l, 1);
    l = add(l, 2);
    l = add(l, 3);
    print(l);
    l = del(l);
    print(l);
    return 0;
}

Sac à dos

Exercice

On considère le problème du sac à dos :
Entrée : un sac à dos de capacité C, des objets de poids w1, ..., wn et de valeurs v1, ..., vn .
Sortie : la valeur maximum d'objets que l’on peut mettre dans le sac (de poids total inférieur à C)

Il n'est pas possible de prendre plusieurs fois le même objet.

Pour résoudre ce problème par programmation dynamique, on peut créer une matrice dp telle que dp[i][j] soit la valeur maximum que l’on peut mettre dans un sac de capacité i en utilisant seulement les j premiers objets.

1. Donner une équation de récurrence sur dp[i][j] (et un cas de base).

Indice

Il y a deux possibilités pour obtenir dp[i][j] : soit prendre l'objet j, soit ne pas le prendre.

2. En déduire une fonction int knapsack(int C, int n, int *w, int *v) résolvant le problème du sac à dos, où C est la capacité du sac, n le nombre d'objets, w un tableau des poids des objets et v un tableau des valeurs des objets.

Indice

#include <stdio.h>
#include <stdlib.h>

int knapsack(int C, int n, int *w, int *v) {
    int **dp = malloc((C + 1) * sizeof(int*));
    for (int i = 0; i < C + 1; i++) {
        dp[i] = malloc((n + 1) * sizeof(int));
        dp[i][0] = 0;
    }
    ...
}

int main() {
    int weights[] = {2, 3, 6, 5, 8, 2, 2};
    int values[] = {1, 7, 10, 10, 13, 1, 1};
    printf("%d", knapsack(10, 7, weights, values)); // doit afficher 18
}

Solution

#include <stdio.h>
#include <stdlib.h>

int knapsack(int C, int n, int *w, int *v) {
    int **dp = malloc((C + 1) * sizeof(int*));
    for (int i = 0; i < C + 1; i++) {
        dp[i] = malloc((n + 1) * sizeof(int));
        dp[i][0] = 0;
    }

    for (int k = 0; k < n + 1; k++)
        for (int c = 0; c < C + 1; c++) {
            dp[c][k] = dp[c][k - 1];
            if (w[k] <= c && dp[c][k] <= v[k] + dp[c - w[k]][k - 1])
                dp[c][k] = v[k] + dp[c - w[k]][k - 1];
        }
    return dp[C][n];
}

int main() {
    int weights[] = {2, 3, 6, 5, 8, 2, 2};
    int values[] = {1, 7, 10, 10, 13, 1, 1};
    printf("%d", knapsack(10, 7, weights, values)); // affiche 18
    return 0;
}

Doublon et algorithme de Floyd

Exercice

Soit $t$ un tableau de taille $n$ dont les éléments sont entre $0$ et $n-1$ (inclus).
On veut déterminer si $t$ contient un doublon, c'est-à-dire un élément apparaissant plusieurs fois.

1. Écrire une fonction doublon1(int* t, int n) en complexité temporelle O($n$) pour résoudre ce problème. Quelle est la complexité spatiale ?
2. Écrire une fonction doublon2(int* t, int n) en complexité O($n$) en temps et O($1$) en mémoire. On pourra modifier $t$.

On considère un type de liste simplement chaînée impérative :

typedef struct cell {
    int elem;
    struct cell *next;
} cell;

Il est possible qu'une liste chaînée l possède un cycle, si l'on revient sur le même élément après avoir parcouru plusieurs successeurs.

3. Écrire un fonction cycle pour tester si l contient un cycle. Quelle est sa complexité en temps et en espace ?

L'algorithme de Floyd est plus efficace. Il consiste à initialiser une variable tortue au premier élément de l, une variable lievre à la case suivante, puis, tant que c'est possible :

• Si lievre et tortue font référence à la même case, affirmer que l contient un cycle.
• Sinon, avancer lievre de deux cases et tortue d'une case.

4. Montrer que cet algorithme permet bien de détecter un cycle dans l. Quelle est l'intérêt de cet algorithme par rapport à celui de la question 3 ?
5. Écrire une fonction bool cycle2(cell* l) détectant un cycle en utilisant l'algorithme du lièvre et de la tortue.

Solution

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

bool doublon1(int* t, int n) {
    bool* t2 = calloc(n, sizeof(bool)); // t2[j] = true si j est déjà apparu dans t
    // on peut aussi utiliser malloc à condition de mettre des 0
    for (int i = 0; i < n; i++) {
        int j = t[i];
        if (t2[j]) {
            free(t2);
            return true;
        }
        t2[j] = true;
    }
    free(t2);
    return false;
}

bool doublon2(int* t, int n) {
    for (int i = 0; i < n; i++) {
        int j = t[i] % n;
        if (t[j] >= n) {
            return true;
        }
        t[j] += n;
    }
    return false;
}

typedef struct cell {
    int elem;
    struct cell *next;
} cell;

bool cycle1(cell* l) {
    cell* p = l;
    while (l != NULL) {
        if (l->next == p) {
            return true;
        }
        l = l->next;
    }
    return false;
}

// si l contient un cycle alors, dans le référentiel de la tortue, le lièvre avance de 1 case à chaque itération donc arrivera sur la même case que la tortue
// l'intérêt par rapport à Q3 est d'avoir une complexité O(1) en mémoire
bool cycle2(cell* l) {
    cell* lievre = l, *tortue = l;
    while (lievre != NULL && lievre->next != NULL) {
        lievre = lievre->next->next;
        tortue = tortue->next;
        if (lievre == tortue) {
            return true;
        }
    }
    return false;
}

int main() {
    int t1[] = {0, 2, 5, 2, 1, 3};
    printf("%d\n", doublon1(t1, 6)); // Affiche 1
    printf("%d\n", doublon2(t1, 6)); // Affiche 1
    int t2[] = {0, 2, 5, 3, 1, 4};
    printf("%d\n", doublon1(t2, 6)); // Affiche 0
    printf("%d\n", doublon2(t2, 6)); // Affiche 0

    cell l1 = {.elem = 0, .next = NULL};
    cell l2 = {.elem = 1, .next = &l1};
    cell l3 = {.elem = 2, .next = &l2};
    printf("%d\n", cycle1(&l3)); // Affiche 0
    printf("%d\n", cycle2(&l3)); // Affiche 0
    l1.next = &l3;
    printf("%d\n", cycle1(&l3)); // Affiche 1
    printf("%d\n", cycle2(&l3)); // Affiche 1
    return 0; 
}