Python - Somme des nombres

J'essaye de faire la somme de tous les nombres jusqu'à une gamme, avec tous les nombres jusqu'à la même gamme.Python - Somme des nombres

J'utilise python:

limit = 10 
sums = [] 
for x in range(1,limit+1): 
    for y in range(1,limit+1): 
     sums.append(x+y)

Cela fonctionne très bien, cependant, à cause des boucles imbriquées, si la limite est trop grand, il faudra beaucoup de temps pour calculer les sommes.

Y at-il un moyen de le faire sans une boucle imbriquée?

(Ceci est juste une simplification de quelque chose que je dois faire pour résoudre un problème de Project Euler. Il consiste à obtenir la somme de tous les nombres abondants.)

Source

2010-08-13 AlexBrand

voir aussi Python 'xrange' généralement, mais la récapitulation de aaronasterling de la prétendue simplification de Gauss a la complexité O (1) pour le problème spécifique et O (1) <<< O (m * n). – msw

@msw Je pense que nous sommes à la fois mal interpréter le problème ici. J'ai édité ma réponse – aaronasterling

voulez-vous une somme simple ou une liste de «sommes» –

[x + y for x in xrange(limit + 1) for y in xrange(x + 1)]

Cela effectue toujours autant de calculs, mais ils faites-le à peu près deux fois plus vite qu'une boucle for.

from itertools import combinations 

(a + b for a, b in combinations(xrange(n + 1, 2)))

Ceci évite beaucoup de sommes en double. Je ne sais pas si vous voulez garder la trace de ceux-ci ou non.

Si vous voulez juste chaque somme sans représentation de la façon dont vous l'avez obtenu alors xrange(2*n + 2) vous donne ce que vous voulez sans doublons ou en boucle du tout.

En réponse à la question:

[x + y for x in set set1 for y in set2]

Source

2010-08-13 02:11:54 aaronasterling

cela fonctionnera si ce sont des numéros consécutifs non? Mais disons que j'ai une liste de 1000 nombres aléatoires, et je veux la somme de tous ces nombres les uns avec les autres ... Y at-il un moyen d'éviter une boucle imbriquée? – AlexBrand

Je suppose que c'est la bonne façon de le faire, mais cela prend encore beaucoup de temps à calculer ... est-ce toujours dans l'ordre O (n^2)? – AlexBrand

Alex: étant donné n nombres aléatoires, il y aura dans le pire des cas O (n^2) sommes différentes. Pour calculer toutes les sommes, vous aurez besoin d'une boucle imbriquée ou de quelque chose qui fait autant de travail qu'une boucle imbriquée. Si le problème est la vitesse, la réponse ne sera pas de calculer ces sommes O (n^2) d'une manière différente; la réponse sera de trouver une solution qui n'implique pas de calculer O (n^2) sommes différentes. –

J'essaie de résumer tous les chiffres jusqu'à à une gamme, avec tous les numéros jusqu'à la même gamme.

Donc, vous voulez calculer limit**2 sommes.

en raison des boucles imbriquées, si la limite est trop grand, il faudra beaucoup de temps pour calculer les sommes.

Faux: il est pas « à cause des boucles imbriquées » - c'est parce que vous calculer un nombre quadratique de sommes, et faisant donc une quantité quadratique de travail.

Y a-t-il un moyen de le faire sans une boucle imbriquée?

Vous pouvez masquer l'imbrication, comme dans @ la réponse de aaron, et vous pouvez réduire de moitié le nombre de sommes que vous calculer en raison de simmetry du problème (bien que cela ne fait pas la même chose que votre code), mais, pour préparer une liste avec un nombre quadratique d'éléments, il n'y a absolument aucun moyen d'éviter de faire une quantité quadratique de travail.

Cependant, votre objectif déclaré

obtenir la somme de tous les nombres abondants.

vous avez besoin d'une quantité infinie de travail, car il y a une infinité de nombres abondants ;-).

Je pense que vous avez dans le problème de l'esprit 23, qui est en fait très différente: il demande la somme de tous les nombres qui ne peuvent être exprimée comme la somme des deux nombres abondants. La façon dont la question que vous posez vous aiderait à vous rapprocher de cette solution m'échappe vraiment.

Source

2010-08-13 02:27:31

Merci pour l'info. Le seul moyen (je suis sûr qu'il y a un meilleur moyen: P) qui me vient à l'esprit est de générer toutes les sommes possibles des nombres abondants inférieurs à 28124, puis de parcourir la liste des sommes avec une limite de 28124, en ajoutant tous les nombres qui n'apparaissent pas dans la liste des sommes à une liste de réponses. – AlexBrand

@alexBrand, quel serait le but du projet Euler si les solutions naïves de force brute étaient assez bonnes? -) Je ne veux pas gâcher votre plaisir en donnant juste la solution, bien sûr, juste un indice: et si vous avez juste besoin de la somme des sommes paires de toutes les paires de nombres abondants jusqu'à N? Cela ne serait-il pas plus rapide à calculer? Et comment le savoir aiderait-il dans votre quête ...? –

hmmm! J'y penserai! Merci beaucoup pour votre aide – AlexBrand

Je ne suis pas sûr s'il y a un bon moyen de ne pas utiliser les boucles imbriquées.

Si je mets sur vos chaussures, je vais écrire comme suit:

[x + y pour x dans la plage (1, limite + 1) pour y dans la plage (1, limite + 1)]

Source

2010-08-13 02:33:44

Python - Somme des nombres

Répondre

Questions connexes