Aller au contenu

DS 1 — Programmation OCaml et C

MP2I, année 2021-2022. Devoir surveillé 1 du 2 octobre 2021. Durée totale 4h.

Tout document interdit. Tout dispositif électronique interdit.

On vous demande d'écrire lisiblement et de bien présenter. Les programmes en particulier doivent être bien indentés et lisibles.

Bon courage et Don't panic! Le barème et les indications de temps sont purement indicatifs.

Reprise des TPs - 10pts

On demande ici de redonner les programmes correspondant plus ou moins directement à des questions posées dans les TP1 à 4.

OCaml - 5pts

Les programmes à donner en réponse ici doivent être écrits en OCaml.

Attention

On utilise ici les types par défaut de OCaml. C'est particulièrement important pour les listes.

Q1. (OCaml - 5 min - 1/2 pt) Écrire une fonction pow2 : int -> int telle que pow2 n renvoie \(2^n\) où \(n \ge 0\) (c'est acquis que \(n\) ne sera jamais négatif donc ne vous en préoccupez pas dans les questions).

Corrigé 
let rec pow2 n =
  if n = 0
  then 1
  else 2 * pow2 (n-1)

Q2. (OCaml - 5 min - 1/2 pt) Écrire une fonction suplog2 : int -> int telle que suplog2 n renvoie le plus petit \(d \in \N\) tel que \(n < 2^d\). On supposera \(n \ge 0\).

Corrigé 
let rec suplog2 n =
  if n = 0
  then 0
  else 1 + suplog2 (n/2)

Q3. (OCaml - 5 min - 1/2 pt) Écrire une fonction comb : int -> int -> int telle que comb n k calcule \(\binom{n}{k}\) avec la relation du triangle de Pascal :

\[ \forall n \in \N^*, \forall k \in \{1,\dots,n\}, \quad \binom{n}{k} =\binom{n-1}{k-1} + \binom{n-1}{k} \]

On rappelle que \(\binom{n}{0}=\binom{n}{n} = 1\) et \(\binom{n}{k} = 0\) par convention quand \(k \not \in \{0,\dots,n\}\).

Corrigé 
let rec comb n k =
  if k > n || k < 0
  then 0
  else if k = n
  then 1
  else comb (n-1) (k-1) + comb (n-1) k

Q4. (OCaml - 5 min - 1/2 pt) Écrire une fonction trib : int -> int telle que trib n calcule \(T_n\) où \(T_0=T_1=0\), \(T_2 = 1\) et

\[ \forall n \in \N, T_{n+3} = T_{n+2} - T_n T_{n+1} \]
Corrigé 
let rec trib n =
  if n <= 1
  then 0
  else if n = 2
  then 1
  else trib (n-1) - trib (n-2) * trib (n-3)

Q5. (10 min - 3/4 pt) On considère \(C_n\) le nombre de noeuds dans l'arbre d'appels récursifs de la fonction trib.

Déterminer une relation de récurrence satisfaite par la suite \((C_n)_{n\in\N}\).

Corrigé

On a \(C_0 = C_1 = C_2 = 1\) et si \(n > 2\),

\[ C_n = 1 + C_{n-1} + C_{n-2} + C_{n-3} \]

Q6. (OCaml - 10 min - 3/4 pt) Écrire une fonction applique : 'a list -> ('a -> 'b) -> 'b list telle que l'appel à applique l f renvoie la liste obtenue en appliquant à chaque élément de l la fonction f.

Exemple :

applique [1;2;3] (fun x -> 4 + x)
(* renvoie *)
[5;6;7]
Corrigé 
let rec applique l f =
  match l with
  | [] -> []
  | t::q -> f t :: applique q f

Q7. (OCaml - 10 min - 3/4 pt) Écrire une fonction nieme : 'a list -> int -> 'a option telle que l'appel à nieme l n renvoie Some x où x est le n-ième élément de l ou None s'il n'y en a pas.

Corrigé 
let rec nieme l n =
  match l, n with
  | [], _ -> None
  | t::_, 0 -> Some t
  | _::q, _ -> nieme q (n-1)

Q8. (OCaml - 10 min - 3/4 pt) Écrire une fonction pourtout : 'a list -> ('a -> bool) -> bool telle que l'appel à pourtout l f renvoie true si et seulement si tous les éléments x de l sont tels que f x soit égale à true.

Corrigé 
let rec pourtout l f =
  match l with
  | [] -> true
  | t::q -> f t && pourtout q f

C - 5pts

Les programmes à donner en réponse ici doivent être écrits en C.

Q9. (C - 5 min - 1/2 pt) Écrire une fonction de signature int suplog2(int n) qui renvoie le plus petit entier \(d \ge 0\) tel que \(0 \le n < 2^d\).

Corrigé 
int suplog2(int n)
{
    int p = 1;
    int d = 0;
    while (n >= p)
    {
        p = p*2;
        d = d+1;
    }
    return d;
}

Q10. (C - 5 min - 1/2 pt) Écrire une fonction de signature int factorielle(int n) qui renvoie \(n!\).

Attention

On ne fera pas de fonction récursive.

Corrigé 
int factorielle(int n)
{
    int p = 1;
    for (int i = 1; i <= n; i++)
    {
        p = p*i;
    }
    return p;
}

Q11. (C - 5 min - 1/2 pt) Écrire une fonction de signature int somme_cubes(int t[], int nb_elts) qui calcule la somme des cubes des éléments du tableau donné en arguments.

Corrigé 
int somme_cubes(int t[], int nb_elts)
{
    int s = 0;
    for (int i = 0; i < nb_elts; i++)
    {
        s = s + t[i]*t[i]*t[i];
    }
    return s;
}

Q12. (C - 2 min - 1/4 pt) Écrire une fonction de signature void swap(int t[], int i, int j) qui échange les valeurs aux indices i et j dans le tableau t.

Corrigé 
void swap(int t[], int i, int j)
{
    int v = t[i];
    t[i] = t[j];
    t[j] = v;
}

Q13. (C - 10 min - 1 pt) Écrire une fonction de signature int indice_minimum(int t[], int i, int j) qui renvoie l'indice du plus petit élément situé entre les indices \(i\) et \(j\) (inclus).

On supposera que la fonction sera toujours appelée avec \(0 \le i < j < n\) où \(n\) est le nombre d'éléments du tableau.

Corrigé 
int indice_minimum(int t[], int i, int j)
{
    int val_min = t[i];
    int indice_min = i;

    for (int k = i+1; k <= j; k++)
    {
        if (val_min > t[k])
        {
            val_min = t[k];
            indice_min = k;
        }
    }

    return indice_min;
}

Q14. (C - 10 min - 1 pt) En déduire une fonction de signature void tri(int t[], int nb_elts) qui trie le tableau donné en argument à l'aide des deux fonctions précédentes.

Corrigé 
void tri(int t[], int nb_elts)
{
    for (int i = 0; i < nb_elts-1; i++)
    {
        int j = indice_minimum(t, i, nb_elts-1);
        swap(t, i, j);
    }
}

Q15. (2 min - 1/4 pt) Comment s'appelle ce tri ?

Corrigé

C'est un tri par sélection car on sélectionne le minimum des éléments non triés pour le placer à la bonne position.

Q16. (C - 10 min - 1 pt) Écrire une fonction de signature int recherche_motif(char s[], char m[]) qui renvoie l'indice de la première occurrence de la chaine m dans la chaîne s si elle s'y trouve, ou \(-1\) dans le cas contraire.

Corrigé 
int recherche_motif(char s[], char m[])
{
    int n = strlen(s);
    int p = strlen(m);
    for (int i = 0; i <= n-p; i++)
    {
        int j;
        for (j = 0; j < p; j++)
        {
            if (s[i+j] != m[j])
            {
                break;
            }
        }
        if (j == p)
        {
            return i;
        }
    }

    return -1;
}

Autour du crible d'Eratosthène - 2pts

On cherche ici à déterminer tous les nombres premiers \(\le N\) où \(N\) est une limite qu'on se fixe à l'avance.

L'idée du crible d'Eratosthène consiste à aligner tous les nombres de \(2\) à \(N\), puis d'effectuer le processus suivant :

  1. Déterminer le plus petit entier \(n\) non barré et non encore étudié.
  2. Barrer tous les multiples de \(n\) qui sont \(> n\).
  3. S'il reste des nombres non barrés \(> n\) retourner à l'étape 1.
  4. Les nombres non barrés sont premiers.

Par exemple pour \(N = 9\) :

  • a) initialisation : \(2~3~4~5~6~7~8~9\)
  • b) étape 1 -- \(n = 2\) on barre donc \(4,6,8\) : \(2~3~\not{4}~5~\not{6}~7~\not{8}~9\)
  • c) étape 2 -- \(n = 3\) on barre donc \(6,9\) (mais \(6\) est déjà barré) : \(2~3~\not{4}~5~\not{6}~7~\not{8}~\not{9}\)
  • d) étape 3 -- \(n = 5\) mais il n'y a pas de multiples : \(2~3~\not{4}~5~\not{6}~7~\not{8}~\not{9}\)
  • e) étape 4 -- \(n = 7\) mais il n'y a pas de multiples : \(2~3~\not{4}~5~\not{6}~7~\not{8}~\not{9}\)
  • f) étape 5 -- il n'y a plus de nombres non barrés, on a donc trouvé les premiers \(\le 9\) : \(2~3~5~7\)

Q17. (C - 20 min - 2 pt) Écrire, en C, une fonction de signature void crible(int p[], int N) qui prend en entrée un tableau de \(N+1\) valeurs entières (non initialisées) et les remplit de sorte que p[i] contienne \(1\) si \(i\) est premier et \(0\) sinon.

On appliquera la méthode précédente.

On essaiera de faire en sorte que la fonction n'utilise que des additions ou des multiplications par deux (ni multiplication, ni division, ni modulo). Si vous n'y arrivez pas, écrivez tout de même la fonction avec ces opérations (mais vous aurez moins de points).

Corrigé 
void crible(int p[], int N)
{
    int i;
    p[0] = 0;
    p[1] = 0;
    for (i = 2; i <= N; i++)
    {
        p[i] = 1;
    }

    for (i = 2; i <= N; i++)
    {
        if (p[i] == 1)
        {
            int m = 2*i;
            while (m <= N)
            {
                p[m] = 0;
                m = m + i;
            }
        }
    }
}

Tours de Hanoi - 3pts

Le but de cet exercice est de résoudre le casse-tête suivant :

Tours de Hanoi

On a trois poteaux, numérotés 1, 2 et 3, sur lesquels on peut enfiler des disques.

Le but du jeu est de partir de la situation décrite sur la photo : tous les disques empilés sur le poteau 1 (à gauche) et d'aboutir aux disques empilés dans le même ordre mais sur le poteau 3 (à droite). Pour cela on ne peut faire qu'un seul coup : déplacer le disque au sommet d'un poteau vers un autre poteau. Par contre, il est interdit de placer un disque sur un disque plus petit.

Par exemple les coups suivants sont licites :

Deux coups licites : le disque déplacé est en orange. Deux coups licites : le disque déplacé est en orange.
Deux coups licites : le disque déplacé est en orange.

Mais celui-ci ne l'est pas :

Un coup illicite : le disque déplacé (en rouge) est posé sur un disque plus petit. Un coup illicite : le disque déplacé (en rouge) est posé sur un disque plus petit.
Un coup illicite : le disque déplacé (en rouge) est posé sur un disque plus petit.

On considère qu'au départ on dispose de \(n\) disques de tailles toutes différentes sur le poteau 1 et que les deux poteaux 2 et 3 sont vides. On cherche à déplacer tous les disques sur le poteau 3. Le poteau 2 joue un rôle crucial, il sert d'espace de travail pour déplacer les disques.

Q18. (5 min - 1/2 pt) Pour quelle(s) valeur(s) de \(n\) peut-on se contenter de deux poteaux ?

Corrigé

Uniquement pour \(n=1\) (ou 0 mais c'est un cas extrême) car si on a au moins deux disques, seul le plus petit peut bouger entre les deux poteaux et on se retrouve bloqué.

Q19. (10 min - 1/2 pt) On suppose qu'on sait déplacer \(n-1\) disques d'un poteau à un autre en utilisant un troisième poteau comme pivot, donner une stratégie pour résoudre le problème à \(n\) disques.

Corrigé

On déplace les \(n-1\) premiers disques sur le poteau du milieu en utilisant le poteau final comme espace temporaire. On se retrouve alors dans la configuration suivante : le premier poteau contient le plus grand disque, le deuxième les \(n-1\) premiers, et le dernier est vide. On place le plus grand disque sur le troisième poteau. On peut alors déplacer les \(n-1\) disques du milieu sur le poteau final.

Le point clé à remarquer c'est qu'un poteau ait le plus grand disque ou pas dessus ne change rien vis-à-vis des \(n-1\) disques restants : ils sont tous plus petits.

On suppose définie une fonction C void deplace(int src, int dst) qui déplace le disque du poteau numéroté src (un int) vers celui numéroté dst. Ainsi deplace(1, 2) déplace un disque du poteau 1 vers le poteau 2.

On indique également qu'il est possible d'écrire des fonctions récursives en C comme en Python en appelant juste la fonction comme dans :

unsigned int fact(unsigned int n)
{
    if (n == 0)
    {
        return 1;
    }
    else
    {
        return n * fact(n-1);
    }
}

Q20. (C - 10 min - 1 pt) Écrire une fonction void hanoi(int n, int src, int dst, int inter) qui résout Hanoi pour \(n\) disques en partant de src pour atteindre dst et utilisant inter comme pivot.

Corrigé 
void hanoi(int n, int src, int dst, int inter)
{
    if (n != 0)
    {
        hanoi(n-1, src, inter, dst);
        deplace(src, dst);
        hanoi(n-1, inter, dst, src);
    }
}

Q21. (10 min - 1 pt) Soit \(D_n\) le nombre de déplacements effectués pour déplacer \(n\) disques avec la fonction précédente. Déterminer une relation de récurrence satisfaite par \(D_n\) et en déduire l'expression de \(D_n\) en fonction de \(n\).

Corrigé

\(D_0 = 0\) car on ne fait rien et si \(n > 0\), \(D_n = 2 D_{n-1} + 1\) car on a fait deux appels récursifs et un déplacement.

On a donc \(D_n = 1 + 2 + \cdots + 2^{n-1} = 2^n-1\).

Couvertures - 5pts

On considère une ligne de \(n\) cases carrées :

que l'on souhaite recouvrir complètement avec des tuiles de différentes longueurs.

Par exemple, si on dispose de tuiles de longueur \(1\) ou \(2\), voici une couverture valide avec deux tuiles de longueur \(1\) et deux de longueur \(2\) :

Q22. (OCaml - 10 min - 1 pt) Écrire une fonction OCaml couvertures12 : int -> int telle que couvertures12 n calcule le nombre de couvertures de \(n\) cases avec des tuiles de longueurs \(1\) ou \(2\).

Indication : on pourra raisonner sur la tuile la plus à gauche d'une telle couverture.

Corrigé

Dans le cas dégénéré \(n = 0\) il n'y a qu'une couverture : c'est l'ensemble vide. Dans le cas \(n=1\) on ne peut placer qu'une tuile de taille 1.

Sinon on place une tuile de taille 1 et on couvre les \(n-1\) restants ou on place une tuile de taille 2 et on couvre les \(n-2\) restants.

let rec couvertures12 n =
  if n = 0 || n = 1
  then 1
  else couvertures12 (n-1) + couvertures12 (n-2)

Q23. (2 min - 1/4 pt) En relisant la fonction précédente, reliez ce nombre de couvertures à une suite classique.

Corrigé

Il s'agit de la suite de Fibonacci !

Q24. (5 min - 1/2 pt) Montrer qu'il est équivalent de couvrir \(n\) cases ainsi et de couvrir un échiquier de \(2 \times n\) cases avec des dominos.

Rappel : un domino est un rectangle de deux cases de long, on peut donc le placer verticalement ou horizontalement pour couvrir deux cases de l'échiquier.

Corrigé

Pour couvrir un échiquier \(2 \times n\) on a le choix sur la position du premier domino : vertical ou horizontal. Si on le place verticalement, il ne reste comme espace libre que de quoi placer un domino parallèle exactement à côté. Le choix que l'on fait est donc entre un domino horizontal ou deux dominos verticaux. C'est exactement le même choix qu'avec les tuiles précédentes. D'ailleurs on passe de l'un à l'autre en coupant l'échiquier en deux.

Q25. (10 min - 3/4 pt) Déterminer une condition sur \(n\) et \(m\) pour qu'un échiquier de \(n \times m\) cases puisse être recouvert par des dominos.

Corrigé

Si on colorie l'échiquier comme aux échecs, chaque domino est à cheval sur une case blanche et une case noire. Il faut donc que le nombre de cases blanches de l'échiquier soit égal au nombre de cases noires.

Si \(n = 2p+1\), les lignes sont tantôt à \(p\) cases noires et \(p+1\) cases blanches, tantôt l'inverse. Pour que cela s'équilibre, il faut que le nombre de lignes soit pair.

Si \(n\) est pair, l'équilibre est automatique.

La condition est donc d'avoir \(n\) ou \(m\) pair. Dans ce cas on peut découper l'échiquier en bandes de tailles \(2 \times m\) ou \(n \times 2\) et on sait que l'échiquier restant est couvrable (par exemple uniquement avec des dominos parallèles).

On a donc \(n\times m\) admet une couverture \(\iff\) \(nm\) pair (car \(n\) ou \(m\) pair \(\iff nm\) pair).

Q26. (OCaml - 20 min - 2 pt) (difficile) Écrire une fonction OCaml couvertures : int list -> int -> int telle que couvertures l n calcule le nombre de couvertures de \(n\) cases avec des tuiles de longueur données par la liste \(l\).

Par exemple, la fonction précédente correspondra à couvertures [1;2].

On ne suppose rien sur \(l\). Si un nombre est présent plusieurs fois, c'est comme si on considérait des tuiles de même longueur mais de couleurs différentes, ce qui augmente le nombre de couvertures.

Corrigé 
let rec couvertures tl n =
  let rec aux l = match l with
    | [] -> 0
    | t::q -> (if n >= t then couvertures tl (n-t) else 0) + aux q
  in if n = 0 then 1 else aux tl

Q27. (5 min - 1/2 pt) Calculer le nombre de couvertures pour la liste [1;1;1;1] qui contient donc quatre fois une tuile de longueur 1 pour quatre couleurs différentes.

Corrigé

Ici on a quatre tuiles identiques de longueur 1, donc on a quatre choix par case. Ainsi, s'il y a \(n\) cases alors on a \(4^n\) couvertures distinctes.

xkcd : tail recursion Gru et la récursivité