Variantes du pplstc — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 11)

Variantes du pplstc

Programmes justes : logique de Hoare et invariants · niveau 2

Énoncé

On reprend la fonction pplstc du cours et l'invariant $I (d, f, j, k)$ .

La modifier pour qu'elle retourne le dernier plus long sous-tableau croissant. Quelle implication de la progression change ?
La modifier pour qu'elle retourne le premier plus long sous-tableau strictement croissant. Quelle implication change ?
Donner les résultats sur $T = [3, 2, 1, 1, 2, 4, 1, 2, 2, 4]$ .

Corrigé

L'invariant devient « $T [d : f]$ est le dernier plus long sous-tableau croissant du $k$ -préfixe ». Seule change la comparaison des longueurs : le suffixe devient le meilleur s'il est au moins aussi long, $I \land k \neq = n \land (k = 0 \lor T [k - 1] \leq T [k]) \land k + 1 - j \geq f - d \Rightarrow I (j, k + 1, j, k + 1)$ . Dans le programme, k - j > f - d devient k - j >= f - d.
Le suffixe strictement croissant est cassé par une égalité : la condition de prolongement devient $k = 0 \lor T [k - 1] < T [k]$ , et l'implication de remise à zéro s'applique dès que $T [k - 1] \geq T [k]$ . Dans le programme, T[k-1] > T[k] devient T[k-1] >= T[k].
Le dernier plus long sous-tableau croissant est $T [6 : 10] = [1, 2, 2, 4]$ ; le premier plus long sous-tableau strictement croissant est $T [3 : 6] = [1, 2, 4]$ .


nom : T
valeurs : 3 2 1 1 2 4 1 2 2 4
colorier : 2..5
vert : 6..9
zone : 2..5 premier
zone : 6..9 dernier
legende : T[2:6] et T[6:10], de longueur 4 : avec ≥, le dernier l'emporte


nom : T
valeurs : 3 2 1 1 2 4 1 2 2 4
vert : 3..5
zone : 3..5 strictement croissant
legende : les égalités cassent la croissance stricte : T[3:6] est le premier