#! /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