Corrigé CCINP 2025 Informatique PC-PSI — Partie II.3 (Q15 à Q21) : Altitudes de référence : tri fusion récursif et recherche dichotomique du plus proche

Sujet officiel du concours CCINP, session 2025, épreuve Informatique PC-PSI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Le globe est quadrillé par une liste de latitudes et une liste de longitudes ; l'altitude de chaque nœud de la grille est stockée dans le dictionnaire dem, de clés les couples (lat, long) et de valeurs les altitudes. On construit lat_ref et long_ref en partant de listes vides et en ajoutant, pour chaque clé (lat, long) de dem, lat à la première et long à la seconde. On suppose que $- 90$ et $90$ sont dans lat_ref, $- 180$ et $180$ dans long_ref.

Q15. Type et contenu de lat_ref et long_ref.

Le sujet définit ensuite deux fonctions récursives. auxiliaire(x, y) renvoie y si x == [], x si y == [] ; sinon elle retire par pop() le dernier élément de y si celui de x lui est strictement inférieur, celui de x sinon, le range dans val, calcule z = auxiliaire(x, y), fait z.append(val) et renvoie z. principal(x) renvoie x si len(x) <= 1 ; sinon, avec m = len(x)//2, elle renvoie auxiliaire(principal(x[0:m]), principal(x[m:len(x)])).

Q16. Signatures de auxiliaire et principal, justifiées.
Q17. Cocher sur le DR le ou les types de programmation utilisés par principal.
Q18. Justifier que principal(x) termine.
Q19. principal(x) trie dans l'ordre croissant : nommer ce tri, en justifiant.

On suppose désormais lat_ref et long_ref triées. La fonction ref(valeur, liste_ref) (liste non vide triée, valeur strictement comprise entre son premier et son dernier élément) renvoie l'élément de liste_ref le plus proche de valeur : une dichotomie (lignes 5 à 12) maintient liste_ref[ind_deb] < valeur <= liste_ref[ind_fin] tant que ind_deb < ind_fin - 1, en testant valeur <= liste_ref[k] ; puis les lignes 14 à 17 renvoient la plus proche des deux valeurs encadrantes.

Q20. Compléter les lignes 5, 6, 8, 10, 12, 15 et 17 de ref.
Q21. Écrire standardise(liste_parcours) : nouvel itinéraire où l'altitude de chaque point est remplacée par celle du nœud $(ϕ_{r}, λ_{r})$ de dem, $ϕ_{r}$ (resp. $λ_{r}$ ) étant la latitude (resp. longitude) de référence la plus proche de celle du point. lat_ref, long_ref et dem sont des variables globales.

Corrigé

Q15. lat_ref et long_ref sont de type list : des listes de flottants. La boucle parcourt les clés de dem (des couples, déballés en (lat, long)) : pour le $k$ -ième nœud de la grille dans l'ordre de parcours du dictionnaire, lat_ref[k] est sa latitude et long_ref[k] sa longitude. Les deux listes ont donc len(dem) éléments, autant que de nœuds de la grille de référence.

Ce sont les latitudes et longitudes des points de référence du dictionnaire dem, avec deux particularités à voir :

elles contiennent des répétitions : la grille étant le produit d'une liste de latitudes par une liste de longitudes, chaque latitude de la grille figure dans lat_ref autant de fois qu'il y a de longitudes, et réciproquement ;
elles ne sont pas triées a priori (ordre d'insertion dans dem) ; d'où le tri des questions suivantes.

Test : sur une grille au pas de $0, 5^{\circ}$ ( $361$ latitudes, $721$ longitudes), les deux listes ont $260281$ éléments et lat_ref commence par $- 90.0$ répété.

Q16. auxiliaire(x:list, y:list) -> list et principal(x:list) -> list, les listes contenant des éléments comparables par < (ici des flottants, latitudes ou longitudes).

Justification : dans auxiliaire, x et y sont comparés à [], mesurés par len, indexés et vidés par la méthode pop() : ce sont des listes ; la fonction renvoie y, x ou z, sur lequel on appelle append : une liste. Leurs éléments sont comparés par <. Dans principal, x est mesuré par len et découpé en tranches x[0:m] : c'est une liste ; la fonction renvoie x ou le résultat de auxiliaire, donc une liste.

Q17. La liste exacte des cases du DR n'est pas publiée avec le sujet ; les cases à cocher sont celles qui décrivent

la programmation récursive : principal s'appelle elle-même (deux fois) sur des listes plus courtes, avec un cas de base len(x) <= 1 ; auxiliaire est elle aussi récursive ;
la stratégie diviser pour régner : découper le problème en deux sous-problèmes de taille moitié, les résoudre récursivement, combiner les deux solutions (auxiliaire).

Ce n'est ni de la programmation itérative (aucune boucle), ni un algorithme glouton, ni de la programmation dynamique (les sous-problèmes sont disjoints, rien n'est mémorisé). Le jury prévoit des points négatifs pour les cases cochées au hasard.

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →