Maison >développement back-end >C++ >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}$$
Étant donné un numéro n. Trouvez la somme des produits par paires dans la plage (1, n), y compris n et 1.
Input: n = 4
Output: 65La traduction chinoise de
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
Input: n = 10
Output: 1705La traduction chinoise de
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
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.
procedure pairwiseProduct (n) sum = 0 for i = 1 to n for j = i to n sum = sum + (i * j) end procedure
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; }
Pairwise Product = 1155
Complexité temporelle - O(n^2)
Complexité spatiale - O(1)
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,
procedure pairwiseProduct (n) sum = 0 prefixSum = 0 for i = 1 to n prefixSum = prefixSum + 1 sum = sum + i * prefixSum end procedure
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; }
Pairwise Product = 1155
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!