Code source de X_PSI_PT__2015__minimal_solution

#! /usr/bin/env python3
# -*- coding: utf-8; mode: python -*-
"""Correction du DS de vendredi 11 décembre 2015.

Voici ci-dessous la documentation de la correction complète du sujet d'écrit d'informatique (Polytechnique et ENS, 2015), pour PSI et PT.
Ce sujet d'écrit a été posé en devoir écrit surveillé (DS) pour le cours d'informatique pour tous en prépa MP au Lycée Lakanal.


- *Date :* Vendredi 11 décembre 2015,
- *Auteur :* Lilian Besson, pour le cours d'informatique pour tous en prépa MP (http://perso.crans.org/besson/infoMP/),
- *Licence :* MIT Licence (http://lbesson.mit-license.org).


.. note::

   Cette correction ne contient aucune documentation, mais elle est plus consise.

   - Voir `le code de cette correction <_modules/X_PSI_PT__2015__minimal_solution.html>`_.
   - Voir `l'autre correction <X_PSI_PT__2015.html>`_ pour plus d'exemples et de détails.
"""

from __future__ import print_function  # Python 2 compatibility


# %% Partie 0 : Fonctions supposées données
print("\n\nPartie 0 : Fonctions supposées données")
# On donne une implémentation simple des fonctions supposées données par l'énoncé


[docs]def creerTableau(n): t = [None] * n return t
[docs]def creerTableau2D(p, q): # Ce code là était donné, tel quel. a = creerTableau(p) for i in range(p): a[i] = creerTableau(q) return a
[docs]def affiche(*args): print(*args, sep='')
# %% Partie I : Préliminaires : Listes dans redondance affiche("\n\nPartie I : Préliminaires : Listes dans redondance") affiche("Note : une liste non-ordonnée et sans redondance est exactement un set de Python, mais nous ne devons pas nous en servir.") # %% Question 1
[docs]def creerListeVide(n): liste = creerTableau(n+1) liste[0] = 0 for i in range(1, n+1): liste[i] = None return liste
# %% Question 2
[docs]def estDansListe(liste, x): n = liste[0] for i in range(1, n+1): # On ne cherche pas parmi les valeurs inutilisées if x == liste[i]: # On a trouvé x dans le tableau ! return True return False
# %% Question 3
[docs]def ajouteDansListe(liste, x): if estDansListe(liste, x): pass else: n = liste[0] capacite = len(liste) - 1 if n < capacite: liste[n+1] = x liste[0] = n + 1 else: affiche("Impossible d'ajouter l'élément x = ", x, " à la liste ", liste, " qui est déjà pleine (n = ", n, ").")
# %% Partie II. Création et manipulation de plans affiche("\n\nPartie II. Création et manipulation de plans") # %% Question 5
[docs]def creerPlanSansRoute(n): plan = creerTableau(n+1) m = 0 # Par défaut, aucune route plan[0] = [n, m] for i in range(1, n+1): plan[i] = creerListeVide(n+1) return plan
# %% Question 6
[docs]def estVoisine(plan, x, y): return estDansListe(plan[x], y) and estDansListe(plan[y], x)
# %% Question 7
[docs]def ajouteRoute(plan, x, y): if not estVoisine(plan, x, y): m = plan[0][1] # On ajoute deux nouvelles voisines : ajouteDansListe(plan[x], y) # y voisine de x ajouteDansListe(plan[y], x) # x voisine de y # Une route de plus (et pas deux, x -> y et y -> x sont identiques) plan[0][1] = m + 1
# %% Question 8
[docs]def afficheToutesLesRoutes(plan): n = plan[0][0] m = plan[0][1] longue_chaine = "" for x in range(1, n+1): for y in range(x+1, n+1): # Prendre y > x assure qu'on ajoute une route (x,y) et (y,x) une seule fois ! if estVoisine(plan, x, y): longue_chaine = longue_chaine + " (" + str(x) + "-" + str(y) + ")" affiche("Ce plan contient ", m, " route(s):", longue_chaine)
# %% Partie III. Recherche de chemins arc-en-ciel affiche("Partie III. Recherche de chemins arc-en-ciel") import random
[docs]def entierAleatoire(k): return random.randint(1, k)
# %% Question 9
[docs]def coloriageAleatoire(plan, couleur, k, s, t): couleur[s] = 0 n = plan[0][0] for i in range(1, n+1): if i != s and i != t: couleur_aleatoire = entierAleatoire(k) couleur[i] = couleur_aleatoire couleur[t] = k+1
# %% Question 10
[docs]def voisinesDeCouleur(plan, couleur, i, c): n = plan[0][0] voisines_de_i_de_couleur_c = creerListeVide(n) nb_voisines_de_i = plan[i][0] for k in range(1, nb_voisines_de_i+1): j = plan[i][k] if i != j and couleur[j] == c: ajouteDansListe(voisines_de_i_de_couleur_c, j) return voisines_de_i_de_couleur_c
# %% Question 11
[docs]def voisinesDeLaListeDeCouleur(plan, couleur, liste, c): n = plan[0][0] voisines_des_k_dans_liste_de_couleur_c = creerListeVide(n) for indice_k in range(1, liste[0]+1): k = liste[indice_k] voisines_de_k_de_couleur_c = voisinesDeCouleur(plan, couleur, k, c) for indice_j in range(1, voisines_de_k_de_couleur_c[0]+1): j = voisines_de_k_de_couleur_c[indice_j] ajouteDansListe(voisines_des_k_dans_liste_de_couleur_c, j) return voisines_des_k_dans_liste_de_couleur_c
# %% Question 12
[docs]def existeCheminArcEnCiel(plan, couleur, k, s, t): n = plan[0][0] # On se lance, en partant de s liste = creerListeVide(n) # Sommets de couleur 0 ajouteDansListe(liste, s) # Sommets de couleur 0 # Couleur courant 0 (note : c aussi = diamètre de l'exploration courante) c = 0 while not(estDansListe(liste, t)) and c <= t: # On n'est pas arrivé c += 1 # On passe à la couleur d'après # On filtre les voisines des villes dans liste qui sont de couleurs c bonnes_voisines = voisinesDeLaListeDeCouleur(plan, couleur, liste, c) # Et ou bien on peut continuer à explorer, ou bien on doit arrêter if bonnes_voisines[0] == 0: # On doit s'arrêter return False else: # On peut continuer, et désormais on part des villes suivantes liste = bonnes_voisines # On a t dans la liste, donc on a un chemin partant de s jusqu'à t return True
# %% Partie IV. Recherche de chemin passant par exactement k villes intermédiaires distinctes affiche("Partie IV. Recherche de chemin passant par exactement k villes intermédiaires distinctes") # %% Question 13
[docs]def existeCheminSimple(plan, k, s, t): n = plan[0][0] nombre_executions = k ** k for _ in range(nombre_executions): # On génère un coloriage aléatoire couleur = creerTableau(n+1) # Tableau vide coloriageAleatoire(plan, couleur, k, s, t) # On espère qu'il convient pour trouver un chemin arc-en-ciel if existeCheminArcEnCiel(plan, couleur, k, s, t): return True return False
# %% Question 14 affiche(""" Question 14 : Le programme a modifier est existeCheminArcEnCiel. Il faut faire en sorte de garder en mémoire les listes liste successives. """) # Fin de X_PSI-PT_2015__minimal_solution.py