Exercice 3 - Graphes · Bac Numérique et Sciences Informatiques Centres étrangers (Afrique) 2025 (jour 2)

Exercice 3 (8 points)

Cet exercice porte sur les graphes, la programmation objet et la récursivité.

On considère un jeu où les nombres entiers de 1 à 9 sont placés autour d’un cercle. Le but du jeu est de relier le plus de nombres possibles en partant de l’un d’entre eux et en appliquant la règle suivante: le nombre suivant est un multiple ou un diviseur du précédent, sans jamais utiliser deux fois le même nombre.

Par exemple, en partant du nombre 4 nous pouvons aller:

soit au nombre 8 (qui est un multiple de 4);

soit au nombre 2 (qui est un diviseur de 4);

soit au nombre 1 (qui est un diviseur de 4).

Bien que 4 soit à la fois multiple et diviseur de 4, nous ne pouvons pas relier 4 à 4. C’est pourquoi dans la suite nous appellerons diviseur (respectivement multiple) d’un entier ses diviseurs (respectivement ses multiples) différents de lui-même. On dira donc que les seuls diviseurs de 4 sont 1 et 2, et que son seul multiple (entre 1 et 9) est 8.

Depuis le nombre 4, on peut donc choisir d’aller en 8, puis en 2 qui est diviseur de 8, puis 6 qui est multiple de 2. On construit ainsi le chemin 4, 8, 2, 6 de longueur 3. Mais puisque le but du jeu est de trouver un chemin le plus long possible, on a tout intérêt à prolonger ce chemin: on peut encore aller en 1 qui est diviseur de 6, puis en 7 qui est multiple de 1. On obtient ainsi le chemin 4, 8, 2, 6, 1, 7 représenté sur la figure 1.

Ce chemin n’est pas prolongeable: en effet, ce chemin finit par le nombre 7, or 7 n’a aucun multiple entre 1 et 9, et un seul diviseur, 1, qui figure déjà dans le chemin.

1.

Donner un chemin non prolongeable qui commence par $3 \to 9 \to 1 \to 2$.

Partie A: Modélisation du jeu par un graphe

Afin de représenter le jeu, nous allons construire le graphe à 9 sommets représentant les nombres entiers de 1 à 9, où chacun d'eux est relié à tous ses diviseurs et à tous ses multiples. Ce graphe non orienté est représenté en figure 4.

Nous allons implémenter ce graphe en Python en définissant tout d'abord une classe Sommet dont la méthode d'initialisation est donnée ci-dessous:

class Sommet:

def __init__(self, valeur):

"""Crée un sommet qui n'est relié à aucun autre"""

self.valeur = valeur

self.diviseurs = []

self.multiples = []

Afin de créer un tel graphe de jeu, on utilise la fonction creer_jeu qui prend en paramètre un nombre entier positif n:

1 def creer_jeu(n):

2 """Renvoie le graphe du jeu à n sommets"""

3 jeu = []

4 for valeur in range(1, n+1):

5 sommet = Sommet(valeur)

6 jeu.append(sommet)

7 return jeu

8

9 jeu_9 = creer_jeu(9)

2.

Donner les valeurs prises par la variable locale valeur lors de l'exécution de creer_jeu(9).

3.

Une fois ce code exécuté, donner la valeur de jeu_9[0].valeur.

Pour relier chaque sommet à tous ses diviseurs, nous ajoutons à la classe Sommet la méthode relier_diviseurs:

1 def relier_diviseurs(self, jeu):

2 """Relie ce sommet à tous les sommets de jeu

3 qui représentent des diviseurs de ce sommet"""

4 for s in jeu:

5 if s != self and self.valeur % s.valeur == 0:

6 self.diviseurs.append(s)

7 s.multiples.append(self)

4.

Expliquer le test réalisé à la ligne 5 de la fonction relier_diviseurs.

5.

Donner le contenu de jeu_9[5].diviseurs après l'exécution de jeu_9[5].relier_diviseurs(jeu).

6.

Écrire la ligne 6 manquante dans le code ci-dessous de la nouvelle version de la fonction creer_jeu:

1 def creer_jeu(n):

2 """ renvoie le graphe du jeu à n sommets"""

3 jeu = []

4 for valeur in range(1, n+1):

5 sommet = Sommet(valeur)

6...

7 jeu.append(sommet)

8 return jeu

7.

Recopier et compléter la ligne 3 du code de la méthode lister_diviseurs:

1 def lister_diviseurs(self):

2 """Renvoie la liste des diviseurs de ce sommet"""

3 return [... for sommet in...]

8.

Recopier et compléter le jeu de tests ci-dessous qui a pour but de vérifier que le sommet représentant le nombre 3 est bien relié à tous ses voisins dans le graphe jeu:

1 l_div_3 =...

2 l_mult_3 =...

3 assert 1 in l_div_3

4 assert... in...

5 assert... in...

Partie C: Résolution du jeu

On dispose d'une classe File implémentant une file avec les méthodes est_vide(), enfiler(element) et defiler(). Voici le code incomplet de la fonction rechercher_chemins:

1 def rechercher_chemins(jeu):

2 chemins_np = []

3 f = File()

4 for sommet in jeu:

5 f.enfiler([sommet])

6 while...:

7 chemin =...

8 dernier =...

9 voisins = dernier.diviseurs + dernier.multiples

10 prolongeable =...

11 for voisin in voisins:

12 if voisin not in chemin:

13 prolongeable =...

14 f.enfiler(...)

15 if not prolongeable:

16 chemins_np.append(chemin)

17 return chemins_np

12.

Compléter les lignes de code manquantes de la fonction rechercher_chemins:

13.

Écrire une fonction valeurs_chemin qui prend en paramètre chemin une liste de sommets et renvoie la liste de leurs valeurs.

14.

Recopier et compléter, à l'aide des fonctions rechercher_chemins et valeurs_chemin, les lignes de code suivantes:

1 chemins =...

2 for chemin in...:

3 chemins.append(...)

15.

Écrire le code de la fonction extraire_plus_longs_chemins qui prend en paramètre une liste de chemins L_chemins et qui renvoie la liste des chemins de L_chemins de longueur maximale.

16.

Nous avons testé l'ensemble de notre programme sur différentes tailles de jeu. Voici le nombre de chemins (non prolongeables) obtenus en fonction du nombre de sommets dans le graphe du jeu:

Nombre de sommets

len(L_chemins)

9 · 377

10 · 800

11 · 925

12 · 5279

13 · 5935

14 · 9896

Dire si l'on peut, à l'aide de notre programme, résoudre le jeu pour un nombre de sommets aussi grand que l'on souhaite. Justifier.