Se connecter / S'enregistrer
Votre question

(Python) Sous séquence contigues

Tags :
  • Python
  • Sequence
  • Script
  • Programmation
Dernière réponse : dans Programmation
26 Septembre 2012 02:34:11

Bonjour,

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.

J'aimerais si possible que quelqu'un m'éclair sur ce problème car c'est la folie je ne sais pas par ou commencer.
Merci d'avance.

Autres pages sur : python sequence contigues

a c 232 L Programmation
26 Septembre 2012 09:17:25

Salut,

Je pense que ton énoncé est clair, c'est dans la première phrase que c'est expliqué ce que tu devras faire. Utiliser des fonctions liste, boucle for et itérateur range().

Déjà il va falloir que tu demandes des nombres et que tu les stockes dans une liste.
Ensuite, tu feras une boucle sur les éléments pour calculer la somme des sous-séquences. C'est là que ça risque d'être un peu plus compliqué, le plus simple j'imagine que ça va être de calculer toutes les sous-séquences possibles en regardant quelle est la plus grande.
Donc dans ta liste, tu calculerais la somme de :

  • 11
  • 11 + 13
  • 11 + 13 - 4
  • 11 + 13 - 4 + 3
  • ...
  • 13
  • 13 - 4
  • ...


  • Certainement pas la solution la plus rapide d'exécution, mais bon...
    27 Septembre 2012 21:17:19

    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 ?

    Merci encore.

    Je ne sais pas l'écrire en python, mais il doit suffire de deux boucle imbriquées.
    Contenus similaires
    a c 232 L Programmation
    28 Septembre 2012 09:39:17

    Je ne connais pas le python donc je ne peux pas te dire exactement quoi écrire, mais normalement 2 boucles imbriquées suffisent oui.

    Ca doit donner quelque chose dans ce genre dans un autre langage... :
    1. int maxSum = 0;
    2. for (int i = 0; i < lst.Length; i++) {
    3. int currentSum = lst[i];
    4. maxSum = currentSum > maxSum ? currentSum : maxSum;
    5. for (int j = i+1; j < lst.Length; j++) {
    6. currentSum = currentSum + lst[j];
    7. maxSum = currentSum > maxSum ? currentSum : maxSum;
    8. }
    9. }


    Il restera à récupérer les indices qui ont servis à récupérer le maxSum.
    a b L Programmation
    28 Septembre 2012 22:19:43

    En python, l'indentation sert pour la sémantique des blocs, alors il faut utiliser les tag pour le poster le code python. :) 

    Ce genre de chose est très simple en python, car:
    - pour faire une boucle par indice, il suffit de faire:
    1. for i in range(len(lst)):

    - pour récupérer une sous-liste (d'indice i à l'indice ,) à partir d'une liste, il suffit de faire:
    1. subLst = lst[i:j]

    - pour calculer la somme des éléments d'une liste, il suffit de faire:
    1. currentSum = sum(subLst)

    - pour calculer un max entre 2 valeurs, il suffit de faire:
    1. maxSum = max(maxSum, currentSum)

    J'ai bien mâché le travail non? :) 

    Et comme j'aime bien donner les réponses avec une ligne de code, voici la réponse qui trouve toutes les solutions (bon ok, il serait plus propre de faire une seconde liste pour le calcul du max, mais ça fait une joli guirlande ;)  )
    1. l=[11, 13, -4, 3, -26, 7, -13, 25, -2, 17, 5, -8, 1]
    2. [{'Indice de début':i,'Indice de fin':j,'Liste':l[i:j],'Somme':sum(l[i:j])} for i in range(len(l)) for j in range(i+1,len(l)+1) if sum(l[i:j])==max([sum(l[i:j]) for i in range(len(l)) for j in range(i+1,len(l)+1)])]

    Ce qui me donne comme résultat:
    [{'Indice de début': 7, 'Liste': [25, -2, 17, 5], 'Indice de fin': 11, 'Somme': 45}]
    29 Septembre 2012 23:36:28

    wow merci tous le monde vous êtes vraiment fort!

    C'est parfait CRicky tu m'a vraiment bien éclairé. Cependant je n'arrive pas a voir comment je pourrais le faire répéter pour toute la séquence :

    1. i=0
    2. lst=[9, 3, -2, 4, -15, 1] #exemple de liste
    3. i = 0 #on commence par le début de la liste)
    4. maximum = 0 # valeur par défaut
    5.  
    6. while i<len(lst):
    7. cumul_lst = 0 # on initialise le cumule à 0
    8. for e in range(i, len(lst)):
    9. cumul_lst += lst[e]
    10.  
    11. 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. J'ai fait un peu dans le même sens que OmaR mais je connais pas son language. Reste qu'à finir mon block quelqu'un a une piste sous python ?
    a b L Programmation
    30 Septembre 2012 15:37:55

    Ton premier while, tu peux en faire un for (puisque c'est l'énoncé), mais je n'insiste pas dessus car c'est pareil (voire mieux).

    Ce que tu veux faire, c'est avant tout générer une sous-liste (ce que j'ai indiqué avec subLst = lst[i:j] pour extraire une sous-liste d'une liste).
    Fais ça étape par étape : ne cherche pas à tout faire d'un coup, donc ne pense pas encore à calculer le cumul ni le max tant que tu n'as pas généré l'ensemble de tes sous-listes.
    Tom's guide dans le monde
    • Allemagne
    • Italie
    • Irlande
    • Royaume Uni
    • Etats Unis
    Suivre Tom's Guide
    Inscrivez-vous à la Newsletter
    • ajouter à twitter
    • ajouter à facebook
    • ajouter un flux RSS