La Star

Star dE LA NORMALE:

1) ÉNONCÉ

A normale nous avons un groupe de N étudiants (numérotées de 1 à N pour les distinguer), une star est quelqu’un qui ne connait personne mais que tous les autres connaissent.

Pour démasquer une star, s’il en existe une, vous avez juste le droit de poser des questions, à n’importe quel étudiant i du groupe, du type : “est-ce que vous connaissez j ?” (note “i → j ?”), on suppose que les étudiants répondent la vérité.

On veut un algorithme qui trouve une Star celle du rattrapage, s’il en existe, ou sinon qui garantit qu’il n’y a pas de star dans le groupe, en posant le moins de questions possibles.

Questions :

Combien peut-il y avoir de stars dans le groupe ?
Écrire le meilleur algorithme que vous pouvez pour trouver cette Star du rattrapage ou pas.

2) SOLUTION - Question 1

Réponse : 1 Star (au maximum).

Pourquoi ?
S’il y avait deux stars A et B :

A est une star donc A ne connaît personne ⇒ A ne connaît pas B.
B est une star donc tout le monde connaît B ⇒ A doit connaître B.

Contradiction ! Donc il ne peut pas y avoir 2 stars. Il y 1 star.

3) SOLUTION - Question 2

3.1) Algorithme proposé (celui donné)

Algorithme TrouverStar;
var
n, i, candidat : entier;
Début
ecrire("Entrez le nombre d'étudiants : ");
lire(n);

// Étape 1 : Trouver un candidat potentiel
candidat <- 1;
pour i de 2 à n faire
  ecrire("Est-ce que ", candidat, " connaît ", i, " ? (1 pour Oui, 0 pour Non) : ");
  lire(reponse);
  si (reponse = 1) alors
    candidat <- i;
  fsi
fpour

// Étape 2 : Vérifier si le candidat est réellement une star
pour i de 1 à n faire
  si (i <> candidat) alors
    ecrire("Est-ce que ", i, " connaît ", candidat, " ? (1 pour Oui, 0 pour Non) : ");
    lire(reponse1);
    ecrire("Est-ce que ", candidat, " connaît ", i, " ? (1 pour Oui, 0 pour Non) : ");
    lire(reponse2);
    si (reponse1 = 0 OU reponse2 = 1) alors
      ecrire("Il n’y a pas de star");
      arrêter;
    fsi
  fsi
fpour

ecrire("L'étudiant ", candidat, " est la star");
fin

3.2) AVANT / APRÈS :

AVANT : l’idée générale

L’algorithme fait 2 grandes étapes :

Étape 1 : trouver un candidat qui pourrait être la star.
Étape 2 : vérifier si ce candidat est vraiment une star.

APRÈS : pourquoi cet algorithme est “le meilleur”

Il est “meilleur” car il évite de poser toutes les questions possibles (qui seraient énormes). Ici, on élimine rapidement des étudiants.

4)

4.1) Étape 1 : Trouver un candidat (élimination)

On commence avec candidat = 1. Ensuite, on parcourt i = 2 jusqu’à n et on pose cette question :

Question : “Est-ce que candidat connaît i ?”

Deux cas :

Cas 1 : réponse = 1 (Oui)
Si candidat connaît i, alors candidat ne peut pas être une star, car une star ne connaît personne. Donc on élimine candidat et on met : candidat ← i

Cas 2 : réponse = 0 (Non)
Si candidat ne connaît pas i, alors i ne peut pas être une star, car une star doit être connue par tout le monde. Ici on sait déjà que candidat ne connaît pas i, donc i n’est pas connu par tout le monde. Donc on garde candidat.

Résultat important : à chaque question on élimine au moins 1 personne. Donc après avoir parcouru tout le monde, il reste un seul candidat possible.

4.2) Étape 2 : Vérifier le candidat

Maintenant on a un candidat, mais il faut vérifier qu’il respecte exactement la définition d’une star :

Condition A : tout étudiant i ≠ candidat connaît candidat.
Condition B : candidat ne connaît aucun étudiant i ≠ candidat.

Donc pour chaque i différent du candidat, l’algorithme pose 2 questions :

Question 1 : “Est-ce que i connaît candidat ?”
Si la réponse est 0 (Non), alors candidat n’est pas connu par tout le monde ⇒ pas de star.

Question 2 : “Est-ce que candidat connaît i ?”
Si la réponse est 1 (Oui), alors candidat connaît quelqu’un ⇒ pas de star.

Si on finit toutes les vérifications sans contradiction, alors : candidat est la star.

5) EXEMPLE COMPLET

Exemple avec N = 4. On va juste suivre la logique de l’algorithme. (On imagine que les réponses données par les étudiants sont cohérentes.)

Étape 1 : trouver le candidat

Départ : candidat = 1
On demande : 1 connaît 2 ?
Si réponse = 1 ⇒ candidat devient 2.
On demande : 2 connaît 3 ?
Si réponse = 0 ⇒ 3 n’est pas star ⇒ candidat reste 2.
On demande : 2 connaît 4 ?
Si réponse = 1 ⇒ candidat devient 4.