La somme des produits de chaque paire

Le produit par paire de l'ensemble X = {a, b, c} peut être défini comme la somme des produits de toutes les paires d'ensembles possibles. Les paires d'ensembles sont Y = {a * a, a * b, a *c, b * b, b * c, c * c}, où les produits sont commutatifs. Par conséquent, le produit par paire d’un ensemble X est la somme des éléments de l’ensemble Y, qui est aa + ab + ac + bb + bc + cc.

En termes mathématiques, la somme des produits possibles par paire peut être exprimée comme suit :

$$mathrm{displaystylesumlimits_{i=1,j=i}^{ileq n,jleq n}:(i,j)=itime j}$$

Énoncé du problème

Étant donné un numéro n. Trouvez la somme des produits par paires dans la plage (1, n), y compris n et 1.

Exemple Exemple 1

Input: n = 4

Output: 65

La traduction chinoise de

Explication

est :

Explication

i va de 1 à 4, j va de i à 4.

1*1 + 1*2 + 1*3 + 1*4 + 2*2 + 2*3 + 2*4 + 3*3 + 3*4 + 4*4 = 1 + 2 + 3 + 4 + 4 + 6 + 8 + 9 + 12 + 16 = 65

Exemple Exemple 2

Input: n = 10

Output: 1705

La traduction chinoise de

Explication

est :

Explication

i va de 1 à 10, j va de i à 10.

1*1 + 1*2 + … + 1*10 + 2*2 + 2*3 + … + 2*10 + 3*3 + 3*4 + … + 3*10 + 4*4 + 4*5 + … 4*10 + 5*5 + 5*6 + … + 5*10 + 6*6 + 6*7 + … 6*10 + 7*7 + 7*8 + … 7*10 + 8* 8 + 8*9 + 8*10 + 9*9 + 9*10 + 10*10 = 1705

Méthode 1 : Méthode de fissuration par force brute

La solution par force brute à ce problème consiste à utiliser deux boucles for pour parcourir toutes les paires de nombres possibles dans la plage, où la première boucle parcourt de 1 à n et la deuxième boucle parcourt du premier nombre à n.

pseudocode

procedure pairwiseProduct (n)
   sum = 0
   for i = 1 to n
      for j = i to n
         sum = sum + (i * j)
end procedure

Exemple : implémentation C++

Dans le programme suivant, nous trouvons toutes les paires possibles puis trouvons la somme des produits.

#include <bits/stdc++.h>
using namespace std;

// Function to find pairwise product over the range 1 to n, 1 and n inclusive
unsigned long long pairwiseProduct(unsigned int n){
   unsigned long long sum = 0;
   
   // First number: 1 <= i <= n
   for (unsigned int i = 1; i <= n; i++){
   
      // Second number: i <= j <= n
      for (unsigned int j = i; j <= n; j++){
         sum += i * j;
      }
   }
   return sum;
}
int main(){
   unsigned long long n = 9;
   cout << "Pairwise Product = " << pairwiseProduct(n);
   return 0;
}

Sortie

Pairwise Product = 1155

Complexité temporelle - O(n^2)

Complexité spatiale - O(1)

Méthode 2

Prenons n = 4 comme exemple,

I = 1*1 + 1*2 + 1*3 + 1*4 + 2*2 + 2*3 + 2*4 + 3*3 + 3*4 + 4*4

En simplifiant ce qui précède,

I = 1*1 + (1+2)*2 + (1+2+3)*3 + (1+2+3+4)*4

Prenons prefix_sum[1] = 1,

Somme du préfixe[2] = 1+2,

Somme des préfixes[3] = 1+2+3,

Somme du préfixe[2] = 1+2,

pseudocode

procedure pairwiseProduct (n)
   sum = 0
   prefixSum = 0
   for i = 1 to n
      prefixSum = prefixSum + 1
      sum = sum + i * prefixSum
end procedure

Exemple : implémentation C++

Dans le programme ci-dessous, on trouve la somme de chaque itération, la somme des préfixes, et on la multiplie par le nombre d'itérations puis on l'ajoute à la somme finale à chaque étape.

#include <bits/stdc++.h>
using namespace std;

// Function to find pairwise product over the range 1 to n, 1 and n inclusive
unsigned long long pairwiseProduct(unsigned int n){
   unsigned long long sum = 0;
   unsigned long long prefixSum = 0;
   for (unsigned int i = 1; i <= n; i++){
      prefixSum += i;
      sum += i * prefixSum;
   }
   return sum;
}
int main(){
   unsigned long long n = 9;
   cout << "Pairwise Product = " << pairwiseProduct(n);
   return 0;
}

Sortie

Pairwise Product = 1155

Conclusion

En bref, pour résoudre la somme des produits par paires de nombres compris entre 1 et n, nous pouvons utiliser l'une des deux méthodes mentionnées ci-dessus, la première méthode est la méthode de la force brute et la complexité temporelle est O(n^ 2) , la deuxième méthode est une méthode d'optimisation qui utilise la somme des préfixes pour calculer la somme de deux produits, et la complexité temporelle est O(n).

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!