Sujet Précédent Sujet Suivant

Programme à simplifier

Résolu/Fermé
Utilisateur anonyme - 8 août 2014 à 20:40
 Utilisateur anonyme - 12 août 2014 à 19:16
Bonjour,

J'ai crée un programme qui prend en entrée un entier et qui ressort l'ensemble des listes d'une taille fixée dont la somme de ses éléments vaut l'entier.

J'ai choisi de créer un compteur qui s'incrémente pour générer les nombres entiers croissants puis de les convertir dans une base qui est la base de l'entier + 1. Ainsi, il convertit à chaque fois le compteur en une liste de chiffre qui est la conversion de cet entier en la base voulue.

Le problème est la rapidité. Il semblerait que 90% de mes listes générées sont fausses (leur somme ne vaut pas l'entier).

Voici mon bout de code : 

def somme_liste(Q):
    S=0
    if len(Q)==0:
        return(False)
    for cpt in range(0,len(Q)):
        S=S+Q[cpt]
    return(S)

def retourne_liste(G):
    cpt=len(G)-1
    S=[]
    while len(S)<len(G):
        S.append(G[cpt])
        cpt=cpt-1
    return(S)

def base(nombre,base,taille):
    G=[]
    mem=nombre
    if nombre<base:
        G.append(nombre)
    else:
        while mem>0:
            G.append(mem%base)
            mem=mem//base
    while len(G)<taille:
        G.append(0)
    return(retourne_liste(G))

def liste(n,taille):
    i=0
    C=base(i,n+1,taille)
    cpt=0 #compte le nombre de liste affichée
    while len(C)<=taille:
        if somme_liste(C)==n:
            cpt=cpt+1
            print(C)
        C=base(i,n+1,taille)
        i=i+1
    print("Il y a %s listes affichées alors que %s se sont générées (%s pourcent de perte)" %(cpt,i,round((1-(cpt/i))*100,2)))

2 réponses

Réponse 1 / 2
policier.moustachu
Modifié par policier.moustachu le 11/08/2014 à 11:53
Les modifications de fred1599 sont judicieuses. Par contre à la base ton algorithme n'est pas optimal. Tu génères toutes les combinaisons imaginables et à la fin tu vérifies que la somme est bonne. Du coup ç a fait énormément de calculs pour rien. Je te proposes un algorithmes par récurrence qui calcule directement toutes les bonnes combinaisons : 

def pilepoile(n, taille):
    if taille == 1:
        return [[n]]
    else:
        toutes_les_listes = []
        for i in range(n + 1):
            intermediates = pilepoile(n-i, taille -1)
            for l in intermediates:
                l.insert(0,i)
            toutes_les_listes.extend(intermediates)
        return toutes_les_listes


def affiche_sommes(n, taille):
    for i in pilepoile(n, taille):
       print(i)
1
Utilisateur anonyme
11 août 2014 à 12:22
Je ne comprend pas à quoi ça sert d'appeler à la fonction pilepoile sachant qu'on est déjà dedans. J'ai pas trop compris le principe
0
policier.moustachu
Modifié par policier.moustachu le 11/08/2014 à 12:35
Le seul problème de cet algo c'est qu'il va calculer toutes les listes avant de les afficher. Ca peut prendre du temps.
Et il va tout garder en mémoire aussi.
Donc ça risque de faire crier ta machine si tu lui demandes un gros calcul du style affice_somme(1000,10)
0
policier.moustachu
11 août 2014 à 16:27
C'est un exemple d'algorithme récursif.

Par exemple j'essaie d'avoir toutes les listes de 3 éléments dont la somme fait 10 : 
pilepoile(10,3)
- J'essaie avec le premier élément égal à 1. Je dois maintenant trouver une liste de 2 éléments dont la somme est égal à 9. J'appelle pilepoile(9,2)
         -  J'essaie avec le premier élément égal à 1. Je dois trouver une liste de 1 élément dont la somme est égal à 8. J'appelle pilepoile(8,1)
                 - Une liste de 1 élément dont la somme est égal à 8 : [8]
           [1, 8]
        -  Maintenant j'essaie avec le premier élément égal à 2. Je dois trouver une liste de 1 élément dont la somme est égal à 7. J'appelle pilepoile(7,1) qui me renvoie 7
           [2, 7]
        - etc ......
   [1, 1, 8] [1,2,7] [1,3,6][1,4,5] ................[1,9,0]

- J'essaie avec le premier élément égal à 2.   Je dois maintenant trouver une liste de 2 éléments dont la somme est égal à 8. J'appelle pilepoile(8,2)
   [.....]
   [2, 1, 7] [2,2,6] [2,3,5][2,4,4] ......[2,8,0]


Voilà pourquoi pilepoile s'appelle lui-même. Tu comprends ?
0
Utilisateur anonyme
11 août 2014 à 17:40
Oui je comprend un peu mieux. Quand la fonction fini par chercher une liste d'un élément alors elle le trouve forcément car c'est cet élément.
0
policier.moustachu
11 août 2014 à 17:50
Exactement.
0
Réponse 2 / 2
Utilisateur anonyme
8 août 2014 à 21:52
Pour somme_liste, 

def somme_liste(Q):
    if Q:
        return sum(Q)
    return None


Pour retourne_liste, 

def retourne_liste(G):
    return list(G)
0
Utilisateur anonyme
11 août 2014 à 12:16
J'ai pas compris pourquoi dans somme_liste, on test Q et si c'est faux alors on renvoie None. Pourquoi ne pas renvoyer direct sum(Q) ? (qui au final ne mérite même pas une fonction).
Et pourquoi dans retourne_liste, on renvoie la même liste ?
0
policier.moustachu
11 août 2014 à 16:14
oui tu as raison Help-Jason, tu peux carrément remplacer somme_liste par la fonction sum.
Et tu n'as pas besoin d'utiliser retourne_liste.
0
Utilisateur anonyme
12 août 2014 à 19:16
@Help-Jason, j'ai donné tout simplement l'équivalent de tes fonctions, qui ne méritent en elles mêmes pas de se compliquer la vie comme tu le fais. En fait ta fonction somme_liste, est la fonction sum en python. Je teste Q pour savoir si elle est vide, si c'est le cas, je renvoie None. Dans le cas où je ne testais pas, la somme serait de 0 pour une liste vide.

retourne_liste que je te présente est là encore pour t'annoncer que tu travailles dans le vide, et que son équivalent est le retour de list(G), pourquoi se compliquer la vie ?

Bref tout cela pour dire qu'il y a des fonctions nettement simplifiables, voir peut-être même inutiles...
0

Discussions similaires

programme qui n'affiche pas le mot secret
EMy.chev -
yg_be -

3 réponses
Pourquoi Program files (x86) et Programmes?
peer_at -
abdelhak -

7 réponses
"BONJOUR" : utilité de ce programme???
sunbeep -
onizukaille -

5 réponses
TV LG affiche le carré non programmé
Chantal Joubert -
Evancarreaujoho -

4 réponses
GWXUX a cessé de fonctionner
ikam -
Adakhum -

9 réponses