Programme à simplifier Résolu/Fermé

Question

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)))

Utilisateur anonyme · Answer

Pour somme_liste,

def somme_liste(Q):
    if Q:
        return sum(Q)
    return None

Pour retourne_liste,

def retourne_liste(G):
    return list(G)

policier.moustachu · Answer

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_listesdef affiche_sommes(n, taille):    for i in pilepoile(n, taille):       print(i)

Programme à simplifier

2 réponses

Discussions similaires