Séquence de somme (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2)

Dans cet article, nous examinerons différentes façons de calculer la somme d'une séquence - (n^2 - 1^2) + 2(n^2 - 2^2) + n(n^2 - n^2 ). Dans la première méthode, nous calculerons la somme de séquence pour chaque i compris dans la plage 1 à n un par un et l'ajouterons à la somme finale.

Dans la deuxième méthode, nous dériverons une formule mathématique pour calculer la somme d'une série donnée, ce qui réduira la complexité temporelle du programme de O(n) à O(1).

Énoncé du problème - On nous donne un nombre « n » et notre tâche est de calculer la somme de la séquence donnée (n^2 - 1^2) + 2(n^2 - 2^2) +…. (n^2 - n^2).

Exemple

Entrée − nombre = 5

Sortie - Lorsque n = 5, la somme de la série (n^2 - 1^2) + 2(n^2 - 2^2) + …. .

Entrée − nombre = 3

Sortie - Pour n = 3, la somme de la série (n^2 - 1^2) + 2(n^2 - 2^2) + ….n(n^2 - n^2) est 18 .

Méthode 1

Il s'agit de la méthode de force brute la plus simple pour résoudre le problème de la somme de séquence.

Après une analyse minutieuse de cette séquence, nous pouvons conclure : pour tout nombre n, nous avons

Somme = ∑ i*(n^2 - i^2) pour i = 1 à i = n.

Donc, pour la méthode de force brute, nous pouvons utiliser la formule ci-dessus dans une boucle avec i de 1 à n pour générer la somme requise.

Exemple

Le code de cette méthode est le suivant :

#include <bits/stdc++.h>
using namespace std;
int main () {
   int num = 3;
   long long sum=0;
   for (int i=1  ; i<num ; i++ ) {
      sum = sum+i*( num*num - i*i );
   }
   cout<< " The sum of the series (n^2 - 1^2) + 2(n^2 - 2^2) + …. n(n^2 - n^2) for n = " << num << " is " <<sum;
   return 0;
}

Sortie

The sum of the series (n^2 - 1^2) + 2(n^2 - 2^2) + …. n(n^2 - n^2) for n = 3 is 18

Complexité

Complexité temporelle - O(n) lorsque nous parcourons la boucle de 1 à n.

Complexité spatiale - Puisque nous n'utilisons aucun espace externe, la complexité spatiale de cette méthode est O(1).

Méthode 2

Dans cette méthode, nous dériverons une formule qui obtiendra directement la somme de séquence requise, donc aucune itération n'est requise, cette méthode résoudra le problème donné avec une complexité temporelle constante.

Comme mentionné précédemment, nous obtenons la version générale de la série, donnée sous la forme

Sum = ∑ i*(n^2 - i^2) for i = 1 to i = n.

La même série peut s'écrire ainsi :

Sum =  n^2∑ i - ∑ i^3

Nous connaissons déjà les formules pour calculer la somme de tous les nombres de 1 à n et la formule pour calculer la somme des cubes de tous les nombres de 1 à n, respectivement :

La somme de tous les nombres de 1 à n

n* ( n+1 )/2 

Où n est le nombre donné.

Maintenant, trouvez la somme des cubes de tous les nombres de 1 à n

(n*( n+1 )/2)^2

La série donnée peut donc être écrite comme-

Sum = n^2 * ( n*( n+1 )/2 ) – ( n*( n+1 )/2 )^2

La somme peut être encore simplifiée en -

Sum = ( n * (n+1)/2 )*( n^2 - ( n * (n+1)/2 ))
Sum = n^2 * ( n+1 )/2 * ( n^2 – (n * ( n+1))/2)
Sum = n^2 * ( n+1 ) * ( n-1 )/4
Sum = n^2 * ( n^2 -1 )/4
Sum = (n^4)/4 – (n^2)/4

Il suffit donc de calculer Somme = (n^4)/4 - (n^2)/4, pour tout n, pour obtenir la somme des séquences souhaitées.

Exemple

Le code de cette méthode est le suivant :

#include <bits/stdc++.h>
using namespace std;
int main () {
   int num = 5;
   long long sum = 0;
   sum = num*num*(num*num-1)/4;
   cout<< " The sum of the series (n^2-1^2) + 2(n^2-2^2) + …. n(n^2-n^2) for n = " << num << " is " <<sum;
   return 0;
}

Sortie

The sum of the series (n^2-1^2) + 2(n^2-2^2) + …. n(n^2-n^2) for n = 5 is 150

Complexité

Complexité temporelle - O(1) puisque nous calculons simplement la somme requise en utilisant la formule que nous avons dérivée.

Complexité spatiale - Puisque nous n'utilisons aucun espace externe, la complexité spatiale de cette méthode est O(1).

Conclusion - Dans cet article, nous avons discuté de deux méthodes pour calculer la somme requise d'une série et dans la deuxième méthode, nous avons réduit la complexité temporelle à une constante.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!