Niveau algorithmique

[Python] Plus longue sous-suite croissante

Posté par
charmander 29-12-13 à 16:44

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 :

Citation :

Pour tout i ∈ [0, n − 1], on note $m_i$ la longueur maximale des sous-suites croissantes de u dont le dernier terme est $u_i$
a. Programmer une fonction tabLongueurMax(u) qui calcule $m_0$ , ..., $m_{n-1}$ 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 !

Posté par re : [Python] Plus longue sous-suite croissante 29-12-13 à 18:28

Bonsoir,

Au lieu d'une fonction longueurMax(u), j'aurais programmé une fonction
idxLongueurMax(m) qui aurait renvoyé l'indice de la plus longue sous-suite
ce qui aurait donné directement la plus longue sous-suite.

Voici ce que cela donne en QB64:

CONST BorneA = 10
CONST BorneB = 20

CONST nbU = 15
DIM SHARED u(nbU) AS INTEGER, ssc(nbU) AS INTEGER, x AS INTEGER
CLS
CALL Init
PRINT SeeU$
CALL tabLongMax
PRINT SeeSsc$
x = ssc(idxlongMax%)
PRINT ssc(x)
PRINT SeeOneSsc$(x)

END

SUB Init
SHARED u() AS INTEGER
DIM i AS INTEGER
RANDOMIZE TIMER
FOR i = 0 TO nbU - 1
    u(i) = BorneA + INT(RND * (BorneB - BorneA + 1))
NEXT i
END SUB

FUNCTION idxlongMax%
SHARED ssc() AS INTEGER
DIM ret AS INTEGER, i AS INTEGER
ret = 0
FOR i = 1 TO nbU - 1
    IF ssc(ret) < ssc(i) THEN
        ret = i
    END IF
NEXT i
idxlongMax% = ret
END FUNCTION

SUB tabLongMax
SHARED ssc() AS INTEGER
DIM i AS INTEGER
FOR i = 0 TO nbU - 1
    ssc(i) = SscLong%(i)
NEXT i
END SUB

FUNCTION SscLong% (p AS INTEGER)
SHARED u() AS INTEGER
DIM i AS INTEGER, n AS INTEGER
n = 1
FOR i = p TO 1 STEP -1
    IF u(i - 1) > u(i) THEN
        EXIT FOR
    END IF
    n = n + 1
NEXT i
SscLong% = n
END FUNCTION

FUNCTION SeeOneSsc$ (p AS INTEGER)
SHARED u() AS INTEGER, ssc() AS INTEGER
DIM f AS STRING, i AS INTEGER, j AS INTEGER
f = ""
i = p
f = f + "(" + STR$(i) + ")" + STR$(u(i)) + "[" + STR$(ssc(i)) + "]:"
FOR j = ssc(i) TO 1 STEP -1
    f = f + STR$(u(1 + i - j)) + "|"
NEXT j
f = f + CHR$(13)
SeeOneSsc$ = f
END FUNCTION

FUNCTION SeeSsc$
SHARED u() AS INTEGER, ssc() AS INTEGER
DIM f AS STRING, i AS INTEGER, j AS INTEGER
f = ""
FOR i = 0 TO nbU - 1
    f = f + "(" + STR$(i) + ")" + STR$(u(i)) + "[" + STR$(ssc(i)) + "]:"
    FOR j = ssc(i) TO 1 STEP -1
        f = f + STR$(u(1 + i - j)) + "|"
    NEXT j
    f = f + CHR$(13)
NEXT i
SeeSsc$ = f
END FUNCTION

FUNCTION SeeU$
SHARED u() AS INTEGER
DIM f AS STRING, i AS INTEGER
f = ""
FOR i = 0 TO nbU - 1
    f = f + STR$(u(i)) + "|"
NEXT i
SeeU$ = f
END FUNCTION

sauf étourderie

Posté par re : [Python] Plus longue sous-suite croissante 06-01-14 à 15:24

Si tu sais que la plus longue sous suite est la suite qui termine à $u_i$ et qui a pour longueur $m_i$ , alors tu sais que c'est la suite qui va de $u_{i-m_i+1}$ à $u_i$ compris.

@fontaine6140 : Je pense qu'en python c'est quand même bien plus simple et clair qu'en QB64

def plssc(u) :
   i_max, m_max, m = 0,0,1
   for i in range(1,len(u)) :
      if m > m_max :
         i_max, m_max = i,m
      if u[i] >= u[i-1] :
         m += 1
      else :
         m = 1
   return u[i_max-m_max+1:i_max+1]

Posté par re : [Python] Plus longue sous-suite croissante 06-01-14 à 18:30

Bonjour LittleFox,

Il est vrai qu'en QB64, il faut chaque fois réinventer la roue. (langage de plus bas niveau, pas de listes ).

Je pense qu'il y a une redondance algorithmique dans les fonctions
1) de recherche des longueurs de listes
2) et plssc(u).

On programme toujours dans le langage que l'on connaît le mieux (1979 sur Tandy modèle I 4k de mem).

Posté par re : [Python] Plus longue sous-suite croissante 06-01-14 à 20:08

Je suis d'accord, il y a redondance mais c'est à mon avis pour approcher la solution pas à pas.

Vu que charmander commence à apprendre les algorithmes par le python je me suis permis de sortir la solution en python ^^.

Posté par re : [Python] Plus longue sous-suite croissante 06-01-14 à 20:36

Si j'avais posté le programme, c'était pour illustrer l'idée de l'index de la plus longue liste et non la plus longue liste elle-même (pour éviter la redondance).
C'était uniquement mon intention