Jumlah hasil darab setiap pasangan

Darab berpasangan bagi set X = {a, b, c} boleh ditakrifkan sebagai hasil tambah semua pasangan set yang mungkin. Pasangan set ialah Y = {a * a, a * b, a *c, b * b, b * c, c * c}, di mana hasil darabnya adalah komutatif. Oleh itu, hasil darab berpasangan bagi set X ialah hasil tambah unsur-unsur set Y, iaitu aa + ab + ac + bb + bc + cc.

Dalam istilah matematik, jumlah produk berpasangan yang mungkin boleh dinyatakan sebagai:

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

Pernyataan Masalah

Diberi nombor n. Cari hasil tambah hasil berpasangan dalam julat (1, n), termasuk n dan 1.

Contoh Contoh 1

Input: n = 4

Output: 65

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

i berjulat dari 1 hingga 4, j berjulat dari i hingga 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

Contoh Contoh 2

Input: n = 10

Output: 1705

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

i berjulat dari 1 hingga 10, j berjulat dari i hingga 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

Kaedah 1: Kaedah brute force cracking

Penyelesaian brute force untuk masalah ini adalah dengan menggunakan dua gelung untuk mengulang semua pasangan nombor yang mungkin dalam julat, di mana gelung pertama berulang daripada 1 hingga n dan gelung kedua berulang daripada nombor pertama kepada n.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam program berikut kami mencari semua pasangan yang mungkin dan kemudian mencari jumlah produk.

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

Output

Pairwise Product = 1155

Kerumitan masa - O(n^2)

Kerumitan ruang - O(1)

Kaedah 2

Ambil n = 4 sebagai contoh,

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

Dalam memudahkan perkara di atas,

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

Ambil prefix_sum[1] = 1,

Jumlah awalan[2] = 1+2,

Jumlah awalan[3] = 1+2+3,

Jumlah awalan[2] = 1+2,

pseudokod

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

Contoh: Pelaksanaan C++

Dalam atur cara di bawah, kami mencari jumlah setiap lelaran, jumlah awalan, dan mendarabkannya dengan bilangan lelaran dan kemudian menambah kepada jumlah akhir pada setiap langkah.

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

Output

Pairwise Product = 1155

Kesimpulan

Ringkasnya, untuk menyelesaikan hasil tambah nombor berpasangan dalam julat 1 hingga n, kita boleh menggunakan salah satu daripada dua kaedah yang dinyatakan di atas, kaedah pertama ialah kaedah brute force, dan kerumitan masa ialah O(n^ 2), kaedah kedua ialah kaedah pengoptimuman yang menggunakan jumlah awalan untuk mengira jumlah dua produk, dan kerumitan masa ialah O(n).

Atas ialah kandungan terperinci Jumlah hasil darab setiap pasangan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!