NSI (terminale) · Chapitre 7 · Exercice d'entraînement
Problème — Retrouver une plus longue sous-séquence commune
La programmation dynamique · Séquences et ensembles · niveau 3 (difficile)
Énoncé
Problème — Retrouver une plus longue sous-séquence commune.
La fonction plsc(X, Y) du cours calcule la longueur d'une plus longue sous-séquence commune (PLSC) à deux chaînes, à l'aide d'un tableau table où table[i][j] est la longueur d'une PLSC de X[:i] et Y[:j].
- Calculer la longueur d'une PLSC de
X = "ABCBDAB"etY = "BDCABA". - Écrire une fonction
plsc_mot(X, Y)qui remplit le même tableau puis remonte detable[n][m]jusqu'à une case de la ligne ou de la colonne pour reconstruire une PLSC. - La PLSC est-elle unique ?
Un exercice à chercher : son corrigé n'est pas publié. Sur Adloun, le tuteur guide par questions, sans donner la réponse.