#! /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 `_ 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é def creerTableau(n): t = [None] * n return t 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 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 def creerListeVide(n): liste = creerTableau(n+1) liste[0] = 0 for i in range(1, n+1): liste[i] = None return liste # %% Question 2 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 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 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 def estVoisine(plan, x, y): return estDansListe(plan[x], y) and estDansListe(plan[y], x) # %% Question 7 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 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 def entierAleatoire(k): return random.randint(1, k) # %% Question 9 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 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 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 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 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