Programme à simplifier
Résolu
Utilisateur anonyme
-
Utilisateur anonyme -
Utilisateur anonyme -
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 :
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)))
A voir également:
- Programme à simplifier
- Programme demarrage windows - Guide
- Mettre en veille un programme - Guide
- Message programmé iphone - Guide
- Programme word gratuit - Guide
- Cette action ne peut pas être réalisée car le fichier est ouvert dans un autre programme - Guide
2 réponses
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)
Pour somme_liste,
Pour retourne_liste,
def somme_liste(Q):
if Q:
return sum(Q)
return None
Pour retourne_liste,
def retourne_liste(G):
return list(G)
@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...
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...
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)
Par exemple j'essaie d'avoir toutes les listes de 3 éléments dont la somme fait 10 :
Voilà pourquoi pilepoile s'appelle lui-même. Tu comprends ?