Aller au contenu

DM de Pâques (MP2I 2021-2022) — Chasseurs de fantômes

Devoir à la maison · MP2I · 2021-2022 · C · partie II du devoir des vacances de Pâques

Cours : Diviser pour régner

Autres parties : I. Dessin de graphes · III. Manipulation d'expressions

Source

D'après le sujet d'informatique de Centrale 2009 (« La chasse aux fantômes »).

Un groupe de \(n\) chasseurs de fantômes combat un groupe de \(n\) fantômes. Chaque chasseur est armé d'un canon à ions, capable d'éradiquer un fantôme d'un coup de rayon. Un rayon se propage en ligne droite et termine sa course en touchant le fantôme. Les chasseurs sont confrontés à deux problèmes : il est nécessaire d'éliminer tous les fantômes en même temps, sinon ils se multiplient pour revenir au nombre initial de \(n\) fantômes ; il est très dangereux que deux rayons se croisent, cela ne doit donc pas se produire. Le combat se déroule dans une grotte cylindrique creuse, dont la base est un disque. Les déplacements (chasseurs et fantômes) ne sont possibles que sur un rebord confondu avec la circonférence, mais les tirs se font entre deux points de la circonférence, selon des cordes du cercle.

A

Les \(2n\) protagonistes sont représentés par des points distincts \(P_1, P_2, \dots, P_{2n}\) répartis dans l'ordre des indices croissants sur la circonférence d'un cercle parcouru dans le sens trigonométrique ; \(n\) sont des chasseurs, \(n\) des fantômes, mais, dans cette section, on cherche les liens possibles entre les \(P_i\) sans s'occuper de qui est chasseur et qui est fantôme. Les points doivent être reliés deux à deux par une corde du cercle selon une stratégie gagnante pour les chasseurs. Pour cela, il faut donc respecter les deux conditions :

  1. chaque point est une extrémité d'une et une seule corde,
  2. les différentes cordes ne doivent pas se couper.

Dans toute la suite on fixe un entier \(n > 0\) et on appelle stratégie de taille \(n\) un \(2n\)-uplet \((c_1,c_2,\dots,c_{2n})\) tel que pour tout entier \(i\) vérifiant \(1 \le i \le 2n\) on ait :

\[ 1 \le c_i \le 2n, \qquad c_{c_i} = i, \qquad c_i \neq i. \]

Cette notation exprime bien le lien entre les points \(P_i\) et \(P_{c_i}\).

En C, on représente le \(2n\)-uplet avec un tableau de int. Les éléments seront donc numérotés de \(0\) à \(N-1\). Pour simplifier, on prendra des tableaux de taille \(2n+1\) et on ignorera la valeur à l'indice \(0\). Ainsi c[i] contiendra \(c_i\).

On considère des stratégies où les points d'une paire sont reliés par des segments de droites situés dans un même plan. Une stratégie est dite « admissible » si les segments ainsi formés ne se coupent pas. On admet que cette propriété ne dépend pas de la position des points sur la circonférence mais seulement de la stratégie.

Par exemple, pour les stratégies de taille 4, \(c_1\) et \(c_2\) données dans le tableau, on présente les figures correspondantes, \(c_1\) admissible à gauche, et \(c_2\) non admissible à droite :

Stratégies c1 et c2

Question 1

Dans le cas \(n = 3\), donner le nombre de stratégies possibles, admissibles ou non.

Question 2

Préciser le nombre de stratégies de taille 3 qui sont admissibles. Les représenter sur une figure.

Question 3

Déterminer le nombre de stratégies de taille \(n\) entier positif (qu'elles soient ou non admissibles).

B

Soit \(i, j, k, l\) quatre entiers distincts tels que : \(1 \le i < j \le 2n\) et \(1 \le k < l \le 2n\).

Question 4

Donner une condition nécessaire et suffisante, portant uniquement sur ces entiers, pour que les segments \([P_i P_j]\) et \([P_k P_l]\) se croisent.

Question 5

Écrire une fonction croise prenant les quatre entiers pour paramètres et renvoyant un booléen dont le résultat est true si et seulement si les segments \([P_iP_j]\) et \([P_kP_l]\) se croisent. On suppose que les paramètres donnés à la fonction satisfont les conditions données en introduction de cette partie.

Corrigé 
int croise(int i, int j, int k, int l)
{
    return (i < k && k < j && j < l)
        || (k < i && i < l && l < j);
}

Question 6

En utilisant la fonction croise, écrire une fonction estAdmissible qui prend en paramètre le tableau et le nombre \(n\) de chasseurs, et renvoie un booléen dont le résultat est true si la stratégie est admissible.

Corrigé 
int estAdmissible(int *c, int n)
{
    int p = 2 * n + 1;
    for (int i = 1; i < p; i++)
    {
        for (int k = i+1; k < c[i]; k++)
        {
            if (k < c[k] && croise(i, c[i], k, c[k]))
                return false;
            if (k >= c[k] && croise(i, c[i], c[k], k))
                return false;
        }
    }

    return true;
}

Question 7

Donner, en la justifiant, la complexité de cette méthode, en terme de temps de calcul (on se contentera d'une évaluation du type \(O(n^\alpha)\), en précisant la valeur de \(\alpha\)).

C

On souhaite tester la stratégie de façon plus efficace. Pour cela on utilise une fonction evalue qui prend deux entiers \(i\) et \(j\) comme paramètres (\(i\) et \(j\) étant compris entre 1 et \(2n\)) et dont le résultat est true si et seulement si les deux propositions suivantes sont vraies :

  • \((i\le k \le j) \Rightarrow (i \le c_k \le j)\)
  • les segments ayant leurs extrémités dans l'arc (fermé) \([P_i P_j]\) ne se croisent pas.

Question 8

Donner la valeur de evalue(i,j) dans les trois cas particuliers \(a,b\) et \(c\) suivants :

\[a)\ j < i; \quad b)\ j\ge i \text{ et } c_i < i ; \quad c)\ j \ge i \text{ et } c_i > j\]

Question 9

Pour \(i < c_i < j\), montrer que evalue(i,j) se déduit de evalue(i+1,c[i]-1) et de evalue(c[i]+1,j).

Question 10

Écrire une fonction testStrategie qui prend en paramètre un tableau et le nombre \(n\) de chasseurs, et renvoie un booléen dont la valeur est true si la stratégie est admissible. Cette fonction devra être de complexité \(O(n)\).

Corrigé 
bool evalue(int *c, int i, int j)
{
    if (j < i)
        return true;
    if (c[i] < i || c[i] > j)
        return false;
    return evalue(c, i+1, c[i]-1)
        && evalue(c, c[i]+1, j);
}

bool testStrategie(int *c, int n)
{
    return evalue(c, 1, 2*n);
}

Question 11

Démontrer avec soin que la fonction testStrategie est bien de complexité \(O(n)\).

D

La méthode précédente teste si une stratégie est admissible. On souhaite maintenant, le statut (chasseur ou fantôme) des points étant donné, déterminer directement une stratégie admissible, de façon également efficace.

Question 12

Montrer que si \(P_i\) est un chasseur (\(1 \le i \le 2n\)), alors il existe \(j \neq i\), avec \(1 \le j \le 2n\) tel que \(P_j\) est un fantôme et tel que le nombre de chasseurs soit égal au nombre de fantômes de chaque côté de l'axe \(P_i P_j\).

Question 13

En déduire un algorithme simple pour construire une stratégie admissible.

Question 14

On se propose d'évaluer la complexité de cette méthode.

  1. Déterminer la complexité dans le pire des cas.
  2. Évaluer, sans démonstration, la complexité moyenne.

Question 15

Un tableau \(p\) contient la nature des points \(P_i\) : p[i] vaut \(1\) pour un chasseur et \(-1\) pour un fantôme (\(1 \le i \le 2n\)). On a donc \(\sum_{i=1}^{2n} p[i] = 0\) puisqu'il y a autant de fantômes que de chasseurs. Écrire une fonction cibles qui prend en paramètre le tableau \(p\) et le nombre \(n\) de chasseurs, et renvoie un tableau \(T\) de \(2n+1\) valeurs représentant les couples d'une stratégie admissible où le chasseur \(T[2i+1]\) cible le fantôme \(T[2i+2]\) (on ignore ici aussi la première case du tableau).

Corrigé 
// renvoie k tel qu'il y ait autant de fantômes que de chasseurs
// dans PiPk
int coupe(int *p, int n, int i)
{
    int k = i;
    int s = p[i];
    while (s != 0)
    {
        k++;
        s += p[k];
    }
    return k;
}

// Remplit récursivement le tableau t
void tir(int *p, int *t, int i, int j, int nbTir)
{
    if (p[i] == 1)
    {
        t[2*nbTir+1] = i;
        t[2*nbTir+2] = j;
    }
    else
    {
        t[2*nbTir+1] = j;
        t[2*nbTir+2] = i;
    }
}

int remplit(int *p, int n, int *t, int i, int j, int nbTir)
{
    if (j <= i)
        return nbTir;
    if (j == i+1)
    {
        tir(p, t, i, j, nbTir);
        return nbTir+1;
    }

    int k = coupe(p, n, i);
    nbTir = remplit(p, n, t, i+1, k-1, nbTir);
    nbTir = remplit(p, n, t, k+1, j, nbTir);
    tir(p, t, i, k, nbTir);

    return nbTir+1;
}

int *cibles(int *p, int n)
{
    int *t = malloc(sizeof(int) * (2*n+1));
    remplit(p, n, t, 1, 2*n, 0);
    return t;
}

Exemple d'utilisation :

int main(void)
{
    int p[] = { 0, 1, -1, 1, 1, -1, -1, 1, -1 };
    int n = 4;

    int *t = cibles(p, n);

    for (int i = 1; i <= n; i++)
    {
        printf("%d -> %d\n", t[2*i-1], t[2*i]);
    }
    free(t);
}