TP9. Sous-suite monotone
Énoncé
On souhaite effectuer une analyse sur un fichier texte contenant une suite de nombres. Le fichier est composé de chiffres, d"espaces et de retours chariot. On cherche à trouver quelle est la plus grande sous-suite monotone de termes consécutifs du fichier.
Votre programme devra en outre récupérer le nom du fichier à lire sur la ligne de commande à l’aide du module sys
.
Par exemple dans le fichier suite1.txt
, la plus grande sous-suite monotone de termes consécutifs est : [1, 2, 3, 4]
.
Dans le fichier suite2.txt
, la plus grande sous-suite monotone de termes consécutifs est : [1, 2, 4, 7, 9]
.
Enfin, dans le fichier suite3.txt
, la plus grande sous-suite monotone de termes consécutifs est : [90, 53, 53, 52, 30, 2, 1]
.
Reflechissez à votre algorithme sur le papier avant de vous lancer dans le code.
On se propose d’arriver au résultat final en trois étapes.
Étape 1
Écrire une première boucle qui parcours tous les nombres du fichier (à l'aide de split
).
Étape 2
Écrire une fonction qui traite un nombre :
1 2 3 4 5 6 7 8 |
|
Et utiliser cette fonction dans la boucle de l'étape numéro 1 pour construire une liste de sous-suites monotones.
Étape 3
Comparer de la taille de toutes les sous-suites monotones, éventuellement avec l'aide de la fonction max
.
Notes
Pour simplifier le problème vous pouvez éventuellement commencer en consommant les éléments au fur et à mesure (pas d'éléments communs entre les suites).
Si plusieurs suites ont la même taille maximale, vous pouvez renvoyer n'importe laquelle lors du calcul de la suite de taille maximale.
Difficulté