Algorithme en Python.

Bonjour,

Voilà, je voudrais un coup de pouce pour démarrer le problème suivant :

Soit T un tableau contenant n entiers. Les nombres « a₁, a₂, … , a_k » forment une séquence alternante de T de longueur k si : — ces k nombres appartiennent à T et apparaissent dans cet ordre (mais pas nécessairement consécutivement) dans T ; — a₁ < a₂ > a₃ < a₄ > . . . a_k (notez l’alternance des signes).

Étant donné un tableau T , on cherche à déterminer la plus grande longueur possible d’une séquence alternante de T.

Exemple. Pour le tableau T=[12, 37, 6, 23, 21, 32, 40, 17, 18, 21, 33, 28, 21, 5, 4], la plus longue séquence alternante est de longueur 9 (12 < 37 > 6 < 23 > 21 < 40 > 17 < 33 > 5).

1. Proposez un code Python pour ce problème.

Salut,

Ça ressemble fortement à un devoir/exercice d’apprentissage. Il n’est pas dans l’objectif du forum de te donner des solutions toutes cuites, nous sommes là pour t’aider à apprendre et te débloquer sur des points précis.

Qu’as tu essayé ? Quel code as tu écrit ? Si tu n’arrives vraiment pas à écrire du code, explique avec tes mots comment tu trouverais une solution au problème posé.

Merci de ta compréhension.

On nous précise que pour simplifier, le premier signe sera <. D’où mon idée :

Pour le tableau T=[12, 37, 6, 23, 21, 32, 40, 17, 18, 21, 33, 28, 21, 5, 4] : Je pose i = 1, j = 2 je compare T[i] et T[j] (donc 37 et 6). Puisque 37 > 6, je mets 37 dans ma sous-séquence de résultat. Ensuite j’affecte à i la valeur de j et à j la valeur de j+1. Et je recommence.

Si je trouve après 2 comparaisons deux signes identiques consécutifs, i ne change pas de valeur, et j prend la valeur j+1.

Peut-être que c’est une bonne piste, peut-être pas. Impossible à dire.

En fait, tu parles dans une langue qui est un peu du Python ( i, j … ) et un peu du français. Pourquoi pas… Ecrire un algorithme, c’est un peu ça. Mais tes variables i et j, pour qu’on te comprenne, tu saurais leur donner un autre nom (Debut_alternance ?? non ça ne doit pas être ça. )

Tes variables i et j augmentent, mais tu ne sais pas toi-même ce qu’elles mesurent.

On de demande la plus grande longueur possible. Donc je verrais bien des variables qui s’appelleraient PlusGrandeLongueurDejaTrouvee , et LongueurSérieEnCours par exemple. Ca me parle plus que i et j.

Et si c’est trop long à écrire, tu abrèges en PGLDT et LSEC, en expliquant les noms des variables.

Et il faudra sûrement d’autres variables.