兩兩乘積之和

集合X = {a, b, c}的成對乘積可以定義為所有可能的集合對乘積的和。集合的成對為Y = {a * a, a * b, a *c, b * b, b * c, c * c}，其中乘積是可交換的。因此，集合X的成對乘積是集合Y的元素總和，即aa ab ac bb bc cc。

在數學術語中，可能的配對乘積的總和可以表示為：

$$\mathrm{\displaystyle\sum\limits_{i=1,j=i}^{i\leq n,j\leq n}\:(i,j)=i\time j}$$

問題陳述

給定一個數字n。在範圍（1，n）內，包括n和1，找到成對乘積的總和。

範例範例1

Input: n = 4

Output: 65

Explanation

的中文翻譯為：

解釋

i的範圍從1到4，j的範圍從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

範例範例2

Input: n = 10

Output: 1705

Explanation

的中文翻譯為：

解釋

i的範圍從1到10，j的範圍從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

方法一：暴力破解方法

解決這個問題的蠻力解法是使用兩個for循環迭代範圍內的所有可能的數對，其中第一個循環從1到n迭代，第二個循環從第一個數迭代到n。

虛擬程式碼

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

範例：C 實作

在以下程式中，我們找到所有可能的配對，然後找到乘積的和。

#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

時間複雜度 - O(n^2)

空間複雜度 - O(1)

方法二

以n = 4為例，

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

在簡化上述內容時，

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

取prefix_sum[1] = 1，

前綴總和[2] = 1 2，

前綴總和[3] = 1 2 3，

前綴總和[2] = 1 2，

虛擬程式碼

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

範例：C 實作

在下面的程式中，我們找到每次迭代的和，即前綴和，並乘以迭代次數，然後在每一步中加到最終和中。

#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

結論

總之，對於在範圍1到n內的數字的兩兩乘積之和的求解，我們可以採用上述兩種方法之一，其中第一種方法是暴力法，時間複雜度為O(n^ 2)，第二種方法是使用前綴和來計算兩兩乘積總和的最佳化方法，時間複雜度為O(n)。

以上是兩兩乘積之和的詳細內容。更多資訊請關注PHP中文網其他相關文章！