[Python] Plus longue sous-suite croissante

Discutez d'informatique ici !
Charmander
Membre Naturel
Messages: 90
Enregistré le: 13 Oct 2013, 18:22

[Python] Plus longue sous-suite croissante

par Charmander » 29 Déc 2013, 18:45

Bonjour,

Je dois coder en Python un programme qui prend en entrée un tableau u non trié de longueur n et qui me renvoie la plus longue sous-suite croissante. Voici le sujet :

Pour tout i ;) [0, n ;) 1], on note la longueur maximale des sous-suites croissantes de u dont le dernier terme est
a. Programmer une fonction tabLongueurMax(u) qui calcule , ..., de proche en proche (et les renvoie sous forme d’un tableau). En déduire une fonction longueurMax(u) déterminant la longueur maximale des sous-suites croissantes de u.
b. À l’aide des fonctions précédentes, écrire une fonction plssc(u) qui détermine une plus longue sous-suite croissante de u.


J'ai réussi à coder les deux programmes demandés par la question a) , mais je ne sais pas comment les utiliser pour obtenir la plus longue sous-suite croissante... Si vous aviez une idée, pas nécessairement en langage python mais juste l'idée de l'algorithme... merci d'avance !



Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6518
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 29 Déc 2013, 18:54

slt,

ben tu sais calculer pour i donné la longueur de la sous suite croissante,
donc t'as mettons n sous suites croissantes dont tu connais leur longueur.
Tu sais que la longueur max c'est M.
T'as juste à chercher parmi tes n sous suites croissantes une qui a pour longueur M.
la vie est une fête :)

Charmander
Membre Naturel
Messages: 90
Enregistré le: 13 Oct 2013, 18:22

par Charmander » 29 Déc 2013, 19:02

fatal_error a écrit:slt,

ben tu sais calculer pour i donné la longueur de la sous suite croissante,
donc t'as mettons n sous suites croissantes dont tu connais leur longueur.
Tu sais que la longueur max c'est M.
T'as juste à chercher parmi tes n sous suites croissantes une qui a pour longueur M.


D'accord mais je ne vais pas chercher toutes les suites croissantes pour un n donné, si ? Rien que pour mettons n=5, il y a 5!=120 suites possibles se terminant à n, et je dois tester si elles sont croissantes, puis regarder si elle sont à la longueur maximale, ça en fait beaucoup pour la complexité non?

LeJeu
Membre Irrationnel
Messages: 1129
Enregistré le: 24 Jan 2010, 23:52

par LeJeu » 29 Déc 2013, 19:11

Charmander a écrit:D'accord mais je ne vais pas chercher toutes les suites croissantes pour un n donné, si ? Rien que pour mettons n=5, il y a 5!=120 suites possibles se terminant à n, et je dois tester si elles sont croissantes, puis regarder si elle sont à la longueur maximale, ça en fait beaucoup pour la complexité non?


comme dit Fatal ( que j esalue)

c'est pour ca que l'exo te demande de remplir un tableau intermédiaire de 5 valeurs
qui sont les longueurs des plus grandes suites qui se terminent en 0 en 1 en en .4

ensuite tu n'as plus qu'a chercher le plus grand nb de ces n ( 5) valeurs ca te donne la position du dernier élément de la suite

t'as plus qu'a afficher les max termes de la suite qui se termine à cet endroit

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 2 invités

cron

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite