Exercice 3 - Partie B (Récursivité) · Bac Numérique et Sciences Informatiques Amérique du Nord 2026 (jour 1)

Partie B

On considère une route perpendiculaire à la mer et des immeubles construits le long de cette route. On dit qu'un immeuble, d'un certain nombre d'étages, bénéficie d'une vue sur la mer lorsque les immeubles situés entre lui et la mer ont moins d'étages que lui. On souhaite que les immeubles de la rue aient tous au moins un appartement avec vue sur mer en détruisant le moins d'immeubles possible.

Pour résoudre ce problème, on considère la liste des nombres d'étages de chaque immeuble de cette rue, en partant de la mer: il s'agit de trouver ce qu'on appelle une sous-séquence strictement croissante de longueur maximale de cette liste.

Une sous-séquence d'une liste est une suite d'éléments obtenue en supprimant certains éléments, éventuellement aucun, de la liste d'origine sans changer l'ordre des éléments restants.

Exemples: pour la liste L1 = [10, 22, 9, 33, 21, 50, 41, 60], les listes [22, 9, 50], [10, 22] ou [33] sont des sous-séquences.

La longueur d'une sous-séquence est son nombre d'éléments.

On appelle sous-séquence strictement croissante d'une liste une sous-séquence telle que chaque élément est strictement supérieur au précédent.

Exemples: pour la liste L1 précédente,

[10] est une sous-séquence strictement croissante de longueur 1;

[9, 33] est une sous-séquence strictement croissante de longueur 2;

[10, 22, 33, 50, 60] est une sous-séquence strictement croissante de longueur maximale de L1; elle est de longueur 5.

Pour les questions suivantes, on définit la liste L2 = [3, 1, 8, 2, 5].

Pour les questions suivantes, on définit la liste L2 = [3, 1, 8, 2, 5].

8.

Donner toutes les sous-séquences strictement croissantes de longueur 2 de la liste L2.

9.

Déterminer la plus longue sous-séquence strictement croissante de la liste L2.

10.

Écrire une fonction est_strict_croissante qui prend en paramètre une liste seq et renvoie True si la liste est strictement croissante, False sinon.

def est_strict_croissante(seq):

Récursivité

On cherche à écrire une fonction récursive qui renvoie la longueur d'une plus longue sous-séquence strictement croissante ( llsc) d'un tableau donné en paramètre. La fonction llsc_rec réalise ce calcul à l'aide d'une fonction auxiliaire appelée llsc_fin.

Principe:

pour chaque élément du tableau, on considère deux possibilités: l'inclure ou non dans la sous-séquence;

l'appel de la fonction auxiliaire llsc_fin(i) donne la longueur maximale d'une sous-séquence strictement croissante se terminant à l'indice i du tableau.

11.

Recopier et compléter les lignes 2, 3 et 6 de la fonction llsc_fin.

1 def llsc_fin(tab, i):

2 if...:

3 return...

4 max_len = 1

5 for j in range(i):

6 if tab[j] <...:

7 max_len = max(max_len, llsc_fin(tab, j)+1)

8 return max_len

9

10 def llsc_rec(tab):

11 n = len(tab)

12 return max([llsc_fin(tab, i) for i in range(n)])