Sujet NSI — Terminale — Métropole — Bac 2024

EXERCICE 1 (6 points) Cet exercice porte sur la notion de listes, la récursivité et la programmation dynamique. Pour extraire de l’eau dans des zones de terrain instable, on souhaite forer un conduit dans le sol pour réaliser un puits tout en préservant l’intégrité du terrain. Pour représenter cette situation, on va considérer qu’en forant à partir d’une position en surface, on s’enfonce dans le sol en allant à gauche ou à droite à chaque niveau, jusqu’à atteindre le niveau de la nappe phréatique. Le sol pourra donc être représenté par une pyramide d’entiers où chaque entier est le score de confiance qu’on a dans le forage de la zone correspondante. Une telle pyramide est présentée sur la figure 1, à gauche, les flèches indiquant les différents déplacements possibles d’une zone à une autre au cours du forage. Un conduit doit partir du sommet de la pyramide et descendre jusqu’au niveau le plus bas, où se situe l’eau, en suivant des déplacements élémentaires, c’est-à-dire en choisissant à chaque niveau de descendre sur la gauche ou sur la droite. Le score de confiance d’un conduit est la somme des nombres rencontrés le long de ce conduit. Le conduit gris représenté à droite sur la figure 1 a pour score de confiance 4+2+5+1+3=15. Figure 1. On va utiliser un ordinateur pour chercher à résoudre ce problème. Pour cela, on représente chaque niveau par la liste des nombres de ce niveau et une pyramide par une liste de niveaux. La pyramide ci-dessus est donc représentée par la liste de listes ex1 = 1. Dessiner la pyramide représentée par la liste de listes ex2 = 2. Déterminer un conduit de score de confiance maximal dans la pyramide ex2 et donner son score. Page : 2 / 14 On souhaite déterminer le score de confiance maximal pouvant être atteint pour une pyramide quelconque. Une première idée consiste à énumérer tous les conduits et à calculer leur score pour déterminer les meilleurs. 3. Énumérer les conduits dans la pyramide de trois niveaux représentée sur la figure 2. Figure 2. Afin de compter le nombre de conduits pour une pyramide de n niveaux, on remarque qu’un conduit est uniquement représenté par une séquence de n déplacements gauche ou droite. 4. En considérant un codage binaire d’un tel conduit, où gauche est représenté par 0 et droite par 1, déterminer le nombre de conduits dans une pyramide de