25-NSIJ1G11-1

  Énoncé   Sujet

1. balise12 = Balise(12, ['vert', 'noir'])
   

2. balise9.voisines = [balise8, balise11, balise12]
   

3. L'expression renvoie [2, 5, 6].

4. La suite d'instructions renvoie ['noir', 'vert'].

5. def itineraire(balise_debut, balise_fin, couleur):
       assert couleur in balise_debut.couleurs_balise
       assert couleur in balise_fin.couleurs_balise
       balise = balise_debut
       chemin = [balise]
       while balise.num_balise != balise_fin.num_balise :
           for b in balise.voisines:
               if (couleur in b.couleurs_balise) and (b not in chemin):
                   balise = b
                   chemin.append(balise)
   
       return [b.num_balise for b in chemin]
   

6. L'odre des sommets visités est 1 – 2 – 4 – 5 – 10 – 7 – 6 – 3 – 11 – 9 – 8 – 12.

7. balise4.voisines = [(balise2, 13), (balise5, 21), (balise6, 15)]
   

8. Cette instruction renvoie 5.

9. Le sportif rencontre dans l'ordre les balises 1 – 2 – 4 – 6 – 11 – 9 – 12.

10. def itineraire_trail(balise_debut, balise_fin):
        balise_debut.visitee = True
        balise = balise_debut
        chemin = [balise]
        while balise_fin not in chemin:
            prochaine = mystere(balise)
            if prochaine != None:
                balise = prochaine
                chemin.append(balise)
            else:
                return None
        return [b.num_balise for b in chemin]
    

11. Proposition A : algorithme glouton.

12. Les avantages de la stratégie gloutonne sont :

    • Sa compréhension est souvent intuitive.
    • Facile à implémenter.
    • Son exécution est rapide grâce à une faible complexité en temps.

    Et ses inconvénients :

    • Elle ne garantit pas de trouver la solution optimale (sauf cas particuliers).
    • Elle peut conduire à une impasse, en enchaînant des choix locaux qui conduisent vers une solution incomplète (comme lorsque itineraire_trail renvoie None dans notre cas).