je dois écrire un script Python qui, à l'aide des fonction Liste, boucle for et itérateur range(), et à partir d'une liste non trié d'entiers qu’un utilisateur du programme fournira, affiche la somme maximale d’une sous séquence contiguë présente dans la liste. De plus, je dois retourner les indices du début et de la fin de la sous séquence dans la liste. Les éléments de la liste peuvent être positifs ou négatifs. Par exemple si la liste contient les éléments suivants : 11, 13, -4, 3, -26, 7, -13, 25, -2, 17, 5, -8, 1
La sous séquence 3, -26, 7, -13, 25 a pour somme -4, par contre, la sous séquence de somme maximale est 25, -2, 17, 5 (de somme 45). Votre script devra afficher par conséquence : 45 7 10.
Est-ce que quelqu'un a une piste pour m'éclairer un peu sur ce problème car c'est la folie je ne sais pas par ou commencer.
Merci d'avance.
Je te conseille de réfléchir avec la suite cumulée croissante.
Ainsi tu fais quelques additions au début, ensuite, tu ne feras qu'une seule addition pour calculer ta somme.
Si S(n) est la somme a(0)+a(1)+a(2)+...+a(n)
alors a(5)+a(6)+...+a(10) = S(10) - S(4)
Fait attention aux indices !!!
Ensuite, tu bourrines, avec toutes les différences de i à j (pour i allant de 0 à j-1), pour j allant de 1 au max, et pi c tout.
(On peut faire mieux, mais ça ira en premier jet).
L'algo est en O(n²), et la constante est sympa, faire mieux est déjà plus dur.
Juste une idée (si j'ai bien compris le problème):
Il faut balayer la liste pour trouver toutes les séquences contigües possibles. Donc avoir un indice de début i1 qui ira de 0 à len(liste)-1 et un indice de fin i2 qui ira de i1 à len(liste).
Pour chacune des séquences liste[i1:i2], on calcule la somme, et on regarde si c'est une somme plus grande que la plus grande qu'on a déjà trouvée avant (et qu'on a donc conservée!). Si c'est le cas, il faut remplacer les infos précédentes (somme, i1 et i2) par les nouvelles.
Pour conserver les valeurs, il faudra donc créer au début les 3 variables, par exemple smax, ind1 et ind2. La variable smax devra être initialisée à une valeur suffisamment faible pour qu'on puisse trouver au moins une somme plus forte dans les séquences.
A la fin, on sait qu'on a trouvé la plus forte somme, et qu'elle correspond à la séquence liste[i1:i2]
Il ne faut pas se planter dans les indices de fin: la liste=[20, 21, 22] de longueur 3 correspond à range(0,3) et à liste[0:3], mais l'indice de la dernière valeur est 2 (liste[2] ==> 22).
Ce n'est qu'une idée: il y a d'autres façons de faire. Par exemple, conserver tous les résultats [somme, i1, i2] dans une liste, l'ordonner (trier) et ne garder que la dernière.
Bon le PO devra donc coder un truc bien propre comme il y a déjà les 3/4 de la soluce donnée,
Attention, pour les indices, il peut y avoir plusieurs couples de solutions.
Doit-on donner ceux de plus petits indices (il me semble que l'ordre est total parmi les solutions), ou tous ?
Oui Francky_laH l'ordre reste exemple séquence := [a,b,c] les sous séquence sont a;b;c;a,b;,b,c et a,b,c .... a,c ne fais pas partie des sous séquence. J'espère que j'ai répondu à ta question si c'était bien ça.
De plus, j'ai pondu un petit brouillon. J'ai cogiter un peu et je pensais commencer comme ça, pour l'utilisateur:
while True:
print("\n\nEntrez votre séquence séparée par une virgule\n")
try:
lst = list(eval(input()))
except NameError:
print("Vous n'avez pas entré des nombres entiers")
continue
except SyntaxError: # oui on peut prévoir un autre except, autant qu'on aura besoin
print("Vous n'avez pas respecté le format: des nombres séparés par des virgules!")
continue
break
print(lst)
ensuite c'est de calculer ses sous-séquences et c'est ce qui me bloque. Personellement j'ai trouvé qu'il y avait en tout N + (N+1) + (N+2) ... +1 sous-liste. Soit N*(N+1)/2. Est-ce que il y a moyen de jouer avec ça ? J'ai l'impression que je peux rien faire avec ça car je vois seulement le fait que ça m'indique le nombre de sous séquence possible lol.
Cependant je n'arrive pas a voir comment je pourrais le faire répéter pour toute la séquence :
i=0
lst=[9, 3, -2, 4, -15, 1] #exemple de liste
i = 0 #on commence par le début de la liste)
maximum = 0 # valeur par défaut
while i<len(lst):
cumul_lst = 0 # on initialise le cumule à 0
for e in range(i, len(lst)):
cumul_lst += lst[e]
if maximum < cumul_lst:
j'ai commencé comme ça mais encore la mon cerveau saigne. J'ai pondu ça a mon prof et il ma dit que c'était parfait et que je n'était pas loin mais j'sais pas comment finir mon bloc if ça plante tjs. Si vous avez des conseil ce serais vrmt gentil.
Merci bcp pour toute vos réponse encore ça maide beaucoup.Je passe tellement d'heure sur python c'est incroyable. Si seulement j'étudiais en informatique lol.
Bref merci.
1- puisque le programme devra restituer la somme maxi, mais aussi le début et la fin de la séquence concernée, il faut stocker non seulement la somme maxi (MAXIMUM) mais aussi l'indice début (ideb par exemple) et fin (ifin). A noter que la valeur initiale de MAXIMUM n'est pas zéro, puisque cette somme pourrait être négative à cause des nombres négatifs de la liste. Il suffirait de faire la somme des valeurs négatives de la liste. Mais ne compliquons pas: avec MAXIMUM=-100 tu es tranquille avec les exemples fournis.
2- il est important d'être sûr que ta boucle trouve toutes les séquences possibles. C'est facile en mettant un "print" au bon endroit:
lst = [9, 3, -2, 4, -15, 1] #exemple de liste
i = 0 #on commence par le début de la liste)
while i<len(lst):
for e in range(i, len(lst)):
print lst[i:e+1]
i += 1 # on passe au i suivant
Si tu utilises Python 3, il faut mettre des parenthèses: print(lst[i:e+1])
Manifestement, toutes les séquences contigües sont trouvée!
Il ne te reste plus qu'à compléter ce code avec le calcul de la somme à chaque nouveau 'e', à la comparer à MAXIMUM, et à prendre les décisions en conséquence.
Pour ceux qui veulent tenter le speed, ce sera en C, Python sera trop lent, et c'est là que ça se passe.
En sortie : somme maxi, puis nombre d’occurrence de ce maxi.
(Python) Sous séquence contigues
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.