25-NSIJ2G11-3

  Énoncé   Sujet

1. Le chemin 3 → 9 → 1 → 2 → 4 → 8 est non prolongeable.

2. Lors de l'appel creer_jeu(9), la variable valeur prendra successivement les valeurs de 1 à 9 (inclus).

3. Une fois le code exécuté, l'expression jeu_9[0].valeur renvoie 1.

4. La condition s != self évite qu'un sommet soit relié à lui-même et la condition self.valeur % s.valeur == 0 vérifie que le sommet s est un diviseur du sommet self, ou de manière équivalente que self est un multiple de s.

5. Après exécution de jeu_9[5].relier_diviseurs(jeu), la liste jeu_9[5].diviseurs contient les sommets dont la valeur divise 6, plus précisement [jeu_9[0], jeu_9[1], jeu_9[2]].

6. La ligne manquante est sommet.relier_diviseur(jeu).

7. def lister_diviseurs(self):
       return [sommet.valeur for sommet in self.diviseurs]
   

8. l_div_3  = jeu_9[2].lister_diviseurs()
   l_mult_3 = jeu_9[2].lister_multiples()
   assert 1 in l_div_3
   assert 6 in l_mult_3
   assert 9 in l_mult_3
   

9. La ligne assert not self.est_vide() lève une erreur si l'on tente de défiler une file vide.

10. def taille(self):
        return len(self.donnees) - self.decalage
    

11. f = File()
    f.enfiler(1)
    f.enfiler(2)
    f.enfiler(3)
    assert f.taille() == 3
    assert f.defiler() == 1
    assert f.defiler() == 2
    assert f.defiler() == 3
    assert f.est_vide()
    

12. def rechercher_chemins(jeu):
        chemins_np = []
        f = File()
        for sommet in jeu :
            f.enfiler([sommet])
        while not f.est_vide():
            chemin = f.defiler()
            dernier = chemin[-1]
            voisins = dernier.diviseurs + dernier.multiples
            prolongeable = False
            for voisin in voisins:
                if voisin not in chemin:
                    prolongeable = True
                    f.enfiler(chemin + [voisin])
            if not prolongeable:
                chemins_np.append(chemin)
        return chemins_np
    

13. def valeurs_chemin(chemin):
        return [sommet.valeur for sommet in chemin]
    

14. chemins = []
    for chemin in rechercher_chemins(jeu_9):
        chemins.append(valeurs_chemin(chemin))
    

15. def extraire_plus_longs_chemins(L_chemins):
        if not L_chemins:
            return []
        lmax = len(L_chemins[0])
        for chemin in L_chemins:
            if len(chemin) > lmax:
                lmax = len(chemin)
        return [chemin for chemin in L_chemins if len(chemin) == lmax]
    

16. Les premiers essais montrent que le nombre de chemins non prolongeables croît très rapidement avec le nombre de sommets. Le nombre de chemins considérés semble suivre une croissance exponentielle, voire factorielle. L'algorithme devient vite inefficace, et il faudra envisager une stratégie plus efficace que cette simple recherche exhaustive pour aborder un grand nombre de sommets.