Simplification de la somme de la boucle avec une instruction if

Question

Je n'arrive pas à comprendre comment simplifier ce code pour les sommations, car il contient une instruction if.

sum=0 
for (i = 1 to n){ 
    for (j = 1 to i^2){ 
     if (j % i ==0) then 
      for (k = 1 to j){ 
       sum++ 
      } 
     } 
    } 
} 

Je sais que l'instruction if s'exécutera i fois chaque boucle.

1%1 = 0 
2%2 = 0 
4%2 = 0 
3%3 = 0 
6%3 = 0 
9%3 = 0 

et ainsi de suite.

C'est ce que j'ai jusqu'ici (voir le lien ci-dessous), pardonnez la notation i^2, je ne peux pas encore afficher d'images sans rep. Encore une fois, la sommation interne est i^2 et non 2 je choisis.

http://www.HostMath.com/Show.aspx?Code=%5Csum%5Climits_%7Bi%3D1%7D%5En%5Csum%5Climits_%7Bj%3D1%7D%5Ei%5E%7B2%7D%20%5Csum%5Climits_%7Bk%3D1%7D%5Ej%0A(1)

Je veux simplifier la somme intérieure à j, mais il arrive que, i fois. Je me sens comme c'est très simple et je ne vois pas la connexion évidente.

Answer 1

La réponse que j'ai marquée comme correcte était erronée. C'était la réponse qui m'a été donnée. Je ferai de mon mieux pour le dire correctement. La somme de i = 1 à n, de la somme de j = 1 à i au carré de pair j est égale approximativement à la somme de i = 1 à n de i fois au carré i plus un entier sur 2. (ou la dernière partie à nouveau) est égale approximativement à la somme de i = 1 à n de (i^2 * [(i^2) + 1])/2 qui est Theta n^5. C'est la bonne réponse.

Answer 2

C'est ma solution proposée:

sum=0 
for (i = 1 to n) 
{ 
    for (j = i to i^2, step=i){ 
    sum = sum + j 
    } 
} 

MISE À JOUR Il ressemble à square pyramidal number, vous pouvez simplement écrire:

sum = (2*n^3 + 3*n^2 + n/6) 

Answer 3

for (k = 1 to j) { 
    sum++ 
} 

Notez que le pour-boucle au-dessus des incréments sum j fois, ce qui équivaut à la ligne suivante:

sum = sum + j 

Notez que la condition if (j % i ==0) évalue à true lorsque j est un multiple de i, de sorte que vous pouvez réellement changer votre boucle for indexé par j à incrémenter par i au lieu de 1 après chaque itération. Vous pouvez donc avoir le code équivalent suivant à la place:

sum = 0 
for (i = 1; i <= n; i++) { 
    for (j = 0; j <= i^2; j = j + i) { 
     sum = sum + j 
    } 
} 

Note: Par souci de simplicité, je l'ai changé l'indice de départ de j-0 au lieu de 1. Si nous commençons à 1, j prendra les valeurs 1 + i, 1 + 2i, ... au lieu des multiples de i.

Answer 4

solution rapide:

int sum = n * (n + 1)/2; 
    sum *= sum; 
    sum += n * (n + 1) * (2 * n + 1)/6; 
    sum /= 2; 

Quel code fait:

int sum = 0, i, j; 
    for(i = 1; i <= n; i++) 
    for(j = 1; j <= i; j++) 
     sum += i * j; 

Answer 5

Je pense que l'approche qui est plus proche de ce que vous avez, mais ne dispose pas d'un si est le suivant.

sum = 0 
for (i = 1 to n) 
    for (j = 1 to i) 
    for (k = 1 to i*j) 
     sum++ 

Fondamentalement, vous changer j de sorte qu'au lieu de boucler sur tout de 1 à i^2 et tout sauter qui est pas un multiple de i, il vous suffit boucle j sur les multiples.

Comme cela a été indiqué dans d'autres réponses, il existe des expressions beaucoup plus efficaces pour cette somme qui ne nécessitent aucune boucle.