Die Summe der Produkte jedes Paares

Das paarweise Produkt der Menge X = {a, b, c} kann als Summe der Produkte aller möglichen Mengenpaare definiert werden. Die Mengenpaare sind Y = {a * a, a * b, a *c, b * b, b * c, c * c}, wobei die Produkte kommutativ sind. Daher ist das paarweise Produkt einer Menge X die Summe der Elemente der Menge Y, also aa + ab + ac + bb + bc + cc.

Mathematisch kann die Summe möglicher paarweiser Produkte ausgedrückt werden als:

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

Problemstellung

Gegeben eine Zahl n. Ermitteln Sie die Summe der paarweisen Produkte im Bereich (1, n), einschließlich n und 1.

Beispiel Beispiel 1

Input: n = 4

Output: 65

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

i reicht von 1 bis 4, j reicht von i bis 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

Beispiel Beispiel 2

Input: n = 10

Output: 1705

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

i reicht von 1 bis 10, j reicht von i bis 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

Methode 1: Brute-Force-Cracking-Methode

Die Brute-Force-Lösung für dieses Problem besteht darin, zwei for-Schleifen zu verwenden, um alle möglichen Zahlenpaare im Bereich zu iterieren, wobei die erste Schleife von 1 bis n und die zweite Schleife von der ersten Zahl bis n iteriert.

Pseudocode

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

Beispiel: C++-Implementierung

Im folgenden Programm finden wir alle möglichen Paare und ermitteln dann die Summe der Produkte.

#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;
}

Ausgabe

Pairwise Product = 1155

Zeitkomplexität – O(n^2)

Raumkomplexität – O(1)

Methode 2

Nehmen Sie n = 4 als Beispiel,

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

Um das oben Gesagte zu vereinfachen:

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

Nehmen Sie prefix_sum[1] = 1,

Präfixsumme[2] = 1+2,

Summe der Präfixe[3] = 1+2+3,

Präfixsumme[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

Beispiel: C++-Implementierung

Im folgenden Programm ermitteln wir die Summe jeder Iteration, die Präfixsumme, multiplizieren sie mit der Anzahl der Iterationen und addieren sie dann bei jedem Schritt zur Endsumme.

#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;
}

Ausgabe

Pairwise Product = 1155

Fazit

Kurz gesagt, um die Summe der paarweisen Produkte von Zahlen im Bereich von 1 bis n zu lösen, können wir eine der beiden oben genannten Methoden verwenden, die erste Methode ist die Brute-Force-Methode und die Zeitkomplexität beträgt O(n^). 2) Die zweite Methode ist eine Optimierungsmethode, die die Präfixsumme verwendet, um die Summe zweier Produkte zu berechnen, und die Zeitkomplexität beträgt O (n).

Das obige ist der detaillierte Inhalt vonDie Summe der Produkte jedes Paares. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!