Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
- Accueil
- » Programmation
- » [Python]Plus longue sous-suite croissante
- » Répondre
Répondre
Résumé de la discussion (messages les plus récents en premier)
- yoshi
- 13-01-2014 16:09:10
Salut,
Merci, c'est sympa.
Si les éléments des sous-suites sont consécutifs, ce n'est pas "méchant", d'accord ...
Le problème que j'ai rencontré est le cas : pas forcément consécutifs.
Ça, c'est une autre paire de manches : c'est la première fois, en programmation, que j'ai failli renoncer...
J'ai pourtant écrit, il y a longtemps un logiciel de conjugaison française : je me suis acharner à ce qu'il puisse trouver de lui-même le groupe des verbes, et plus précisément celui des verbes en "ir" qui sont soit du 2e, soit du 3e et ce, sans lexique de verbes.
J'ai fini par trouver une astuce en 4/5 lignes avec quand même une douzaine d'exceptions.
Mais là avec sous-suites, j'ai bien cru devoir capituler...
@+
- miq
- 13-01-2014 15:42:57
Bonjour,
@yoshi: apparemment les éléments des sous-suites ne sont pas nécessairement consécutifs.
Voilà comment j'ai codé la seconde question du problème :
tlm=tabLongueurMax(u)
iCur=iPrev=longueurMax(u)
r=[]
while iPrev>=0:
r.insert(0,u[iCur])
iPrev=iCur-1
while iPrev>=0 and tlm[iPrev]!=tlm[iCur]-1:
iPrev-=1
iCur=iPrev
avec u=[2, 0, 1, 5, 4, 6, 7, 3]
on obtient tlm=[1, 1, 2, 3, 3, 4, 5, 3]
puis iCur=6
et enfin r=[0, 1, 4, 6, 7]
L'idée est de partir de l'indice de la fin de la sous-liste et de remonter chercher quel est l'indice du précédent le plus proche.
- totomm
- 30-12-2013 19:36:42
Bonsoir,
Ainsi avec ces deux fonctions, je connais:
- La longueur de la plus longue sous-suite croissante
- L'indice à laquelle termine cette plus longue sous-suiteEt maintenant j'aimerais connaître à partir de ces informations la dite plus longue sous-suite. J'espère avoir été clair..
Outre ce que pose yoshi, il faudrait dire :
" - La longueur des plus longues sous-suites croissantes, car par exemple :
U : [0,1,7,8,9,2,5,6,3,4] contient 3 sous suites croissantes de longueurs 5 se terminant en 4, 7 et 9 !
Même pour ne redonner que la première des trois, il faut reprendre le tableau u …?!
Il n'est pas dit non plus que le tableau contient des entiers "tous différents"
Si des entiers peuvent apparaître plusieurs fois, gare aux pièges dans la programmation de tabLongueurMax(u)
- yoshi
- 30-12-2013 14:26:19
Salut,
Avec la liste u= [2,0,1,5,4,6,7,3], si j'ai bien compris l'énoncé, les listes des sous-suites croissantes sont
[2],[0],[1],[5],[4],[6],[7],[3]
[0,1],[1,5],[4,6],[6,7]
[0,1,5]
avec des indices consécutifs...
Je ne vois donc pas à quelle sous-suite tu te réfères en disant que la longueur max est 5...
Cela dit, puisque tu as écrit :
je connais:
- La longueur de la plus longue sous-suite croissante
- L'indice auquel se termine cette plus longue sous-suite
Tu crées une 3e fonction à qui tu passes en paramètre ta liste u.
Dans cette fonction
tu commences par chercher n = len(u)
Ensuite, comme je ne sais pas comment tu as construit tes fonctions, j'en suis réduit aux généralités.
Tu récupères, en appelant tour à tour les 2 fonctions précédentes, ta LongMax et ton indice_fin...
Pour extraire la sous-suite
- si les indices sont consécutifs, tu demandes u[indice_fin+1-LongMax:Indice_fin+1]
- si les indices ne sont pas consécutifs, tu es préalablement obligée (dans la la recherche de la longueur max) obligée de stocker aussi les indices de tous les éléments d'une sous-suite.
Par ex pour la sous-suite [0,1,4,6,7], la longueur mas m'importe peu si j'ai stocké les indices correspondant :
IndicesListeMax=[1,2,4,5,6]
Dans ce cas :
print u[i],
t'affiche : 0 1 4 6 7
@+
- totomm
- 30-12-2013 12:15:33
re,
ce n'est donc pas ce que j'avais supposé...j'ai eu tort de faire mes propres suppositions sur un énoncé insuffisamment précis !
- Marie-Josephe
- 30-12-2013 11:33:59
Voici une partie de l'énoncé que j'aurais dû copier :
On considère une suite finie (un tableau) [tex]u = [u_0, u_1, ..., u_{n−1}][/tex] d’entiers. Une sous-suite de u est une suite finie de la forme [tex][u_{i1}, u_{i2}, ..., u_{ip}][/tex] telle que [tex] 0 \leq i_1 < i_2 < ... < i_p \leq n − 1[/tex] et [tex]u_{i1} \leq u_{i2} \leq ... \leq u_{ip}[/tex]
- Marie-Josephe
- 30-12-2013 11:27:36
Oui c'est ça, ce sont des tableaux contenant des entiers naturels dans le desordre
Par exemple, on prend le tableau "u" : [2,0,1,5,4,6,7,3]
Alors la plus longue sous-suite croissante est [0,1,4,6,7].
Le programme tabLongueurMax me renvoie [1, 1, 2, 3, 3, 4, 5, 3] qui regroupe les valeurs de m (qui sont la longueur de la plus longue sous-suite terminant à cet indice). Puis longueurMax renvoie alors 5.
Ainsi avec ces deux fonctions, je connais:
- La longueur de la plus longue sous-suite croissante
- L'indice à laquelle termine cette plus longue sous-suite
Et maintenant j'aimerais connaître à partir de ces informations la dite plus longue sous-suite. J'espère avoir été clair..
- yoshi
- 30-12-2013 11:21:25
Ave,
Ah...
La liste u contiendrait donc une suite de nombres... entiers ? naturels ? relatifs ? nombres décimaux ? Autre chose ?
Conditionné, j'avais interprété suites comme les Suites arithmétiques, géométriques, récurrentes...
Cela n'aurait donc rien à voir ?
@+
- totomm
- 30-12-2013 10:44:26
rebonjour,
merci yoshi pour les questions que j'aurais dû poser, je m'étais fait un petit exemple "a priori" :
u : [1,3,4,2,5,7,9,2,3]
i : 0,1,2,3,4,5,6,7,8
3 sous-suites croissantes :
[1,3,4] de début i=0 et de longueur 3
[2,5,7,9] de début i=3 et de longueur 4
[2,3] de début i=7 et de longueur 2
Cela est-il bien conforme au problème à programmer ?
- yoshi
- 30-12-2013 10:16:54
Bonjour,
Le "bon" connaisseur de Python serait bien déjà intervenu s'il comprenait de quoi il retourne...
Or, la lecture de l'énoncé me laisse perplexe :
Pour tout i ∈ [0, n − 1], on note [tex]m_i[/tex] la longueur maximale des sous-suites croissantes de u dont le dernier terme est [tex]u_i[/tex]
Qu'est-ce que le tableau u ? Que contient-il ? sa définition existe-t-elle ? Que contient-il au juste ?
Au passage, pour utiliser des tableaux en Python, il faut faire appel au module numpy, sinon, ce sont des listes...
Que sont des sous-suites d'une liste ? Jamais entendu ce terme...
Comment aurais-je pu répondre à quelqu'un qui a passé le cap de la 1ere question, alors que je ne comprends même pas de quoi on y parle, donc qui est meilleur que moi ?
Peut-être que la suggestion - à demi-mot - de totomm de poster les programmes déjà écrits permettrait de faire un peu de lumière ?
@+
[EDIT]
Si j'ai une liste L, non triée, composée de n éléments numériques, je peux en extraire le grand le plus petit sans écrire de fonctions supplémentaires via les fonctions natives max() et min() :
>>> L=[1,0,-1,7,20,4,3,5]
>>> max(L),min(L)
(20, -1)
>>>
Mais cela ne fait pas avancer le schmilblick comme disait Coluche...
- totomm
- 30-12-2013 10:03:08
Bonjour,
Je suis navré que mon commentaire n'ait pas été assez clair.
yoshi est un bon connaisseur de Python, Son intervention serait bonne pour améliorer ou compléter les programmes qui seraient montrés.
- Marie-Josephe
- 29-12-2013 21:24:46
Bonjour,
Ben non justement, les u_i ne sont PAS triés pas ordre croissant
- totomm
- 29-12-2013 17:47:34
Bonjour,
Je suppose que pour i de 0 à n-1 vous avez rangé les i tels que [tex]u_i > u_{1+1}[/tex] (> ou =)
Reste à exploiter les différences entre les i rangés successivement : Ce sont les[tex] m_i[/tex]
La plus grande différence correspond à la plus longue sous-suite croissante…et vous en avez les deux bouts
Ai-je bien compris le problème ?
- Marie-Josephe
- 29-12-2013 16:48:21
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 [tex]m_i[/tex] la longueur maximale des sous-suites croissantes de u dont le dernier terme est [tex]u_i[/tex]
a. Programmer une fonction tabLongueurMax(u) qui calcule [tex]m_0[/tex], ..., [tex]m_{n-1}[/tex] 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.
[tex]b.[/tex] À 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 !