DS 1 (MP2I 2021-2022) — Tours de Hanoï et couvertures

Devoir surveillé · MP2I · 2021-2022 · partie II du DS 1 (4 h au total)

Cours : Récursivité

Autres parties : I. Reprise des TP et crible d'Ératosthène

Tours de Hanoi - 3pts

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

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.

Mais celui-ci ne l'est pas :

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.

Question 18

(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é.

Question 19

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

Question 20

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

Question 21

(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\) :

Question 22

(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)

Question 23

(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 !

Question 24

(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.

Question 25

(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).

Question 26

(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

Question 27

(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.