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 -Wall nom_fichier.c

L'option Wall sert à afficher davantage de warnings.

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

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

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) {
    ...
}

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
}

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.