Skip to content

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 :

def traite_nombre(suite, type_suite, nombre):
    """ Traite le nombre donné vis à vis de la suite donnée.

    Renvoie (True, nouveau_type_suite) si suite est toujours
    une suite monotone après ajout de nombre.
    Renvoie (False, nouveau_type_suite) si la suite à changer de sens
    """
    ...

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é

star star star star star

Exercices associés