Jumlah hasil darab semua kombinasi yang diambil dari 1 hingga n

Kalau ambil nombor satu persatu dari 1 hingga n, mungkin ada banyak kombinasi.

Sebagai contoh, jika kita mengambil hanya satu nombor pada satu masa, bilangan gabungan akan menjadi nC1.

Jika kita mengambil dua nombor pada satu masa, bilangan gabungan ialah nC2 Oleh itu, jumlah bilangan gabungan ialah nC1 + nC2 +… + nCn.

.

Untuk mencari jumlah semua kombinasi kita perlu menggunakan kaedah yang cekap. Jika tidak, kerumitan masa dan ruang akan menjadi sangat tinggi.

Pernyataan Masalah

Cari hasil tambah semua gabungan nombor yang diambil setiap kali dari 1 hingga N.

N ialah nombor yang diberi.

Contoh

Masuk

N = 4

Output

f(1) = 10
f(2) = 35
f(3) = 50
f(4) = 24

Penjelasan

f(x) is the sum of the product of all combinations taken x at a time.
f(1) = 1 + 2+ 3+ 4 = 10
f(2) = (1*2) + (1*3) + (1*4) + (2*3) + (2*4) + (3*4) = 35
f(3) = (1*2*3) + (1*2*4) +(1*3*4) + (2*3*4) = 50
f(4) = (1*2*3*4) = 24 

Masuk

N = 5

Output

f(1) = 15
f(2) = 85
f(3) = 225
f(4) = 274
f(5) = 120

Pendekatan Brute Force

Kaedah brute force adalah untuk menjana semua kombinasi secara rekursif, mencari produknya, dan kemudian mencari jumlah yang sepadan.

Contoh program C++ rekursif

Berikut ialah program C++ rekursif untuk mencari jumlah produk yang diambil setiap kali dalam semua kombinasi (dari 1 hingga N)

#include <bits/stdc++.h>
using namespace std;
//sum of each combination
int sum = 0;
void create_combination(vector<int>vec, vector<int>combinations, int n, int r, int depth, int index) {
   // if we have reached sufficient depth
   if (index == r) {
      //find the product of the combination
    	int prod = 1;
    	for (int i = 0; i < r; i++)
    	prod = prod * combinations[i];
    	// add the product to sum
    	sum += prod;
    	return;
   }
   // recursion to produce a different combination
   for (int i = depth; i < n; i++) {
      combinations[index] = vec[i];
   	  create_combination(vec, combinations, n, r, i + 1, index + 1);
   }
}
//Function to print the sum of products of
//all combinations taken 1-N at a time
void get_combinations(vector<int>vec, int n) {
   for (int i = 1; i <= n; i++) {
      // vector for storing combination
         //int *combi = new int[i];
    	vector<int>combinations(i);
    	// call combination with r = i
    	// combination by taking i at a time
    	create_combination(vec, combinations, n, i, 0, 0);
    	// displaying sum of the product of combinations
    	cout << "f(" << i << ") = " << sum << endl;
        sum = 0;
    }
}
int main() {
   int n = 5;
   //creating vector of size n
   vector<int>vec(n);
   // storing numbers from 1-N in the vector
   for (int i = 0; i < n; i++)
   	vec[i] = i + 1;
   //Function call
   get_combinations(vec, n);
   return 0;
}

Output

f(1) = 15
f(2) = 85
f(3) = 225
f(4) = 274
f(5) = 120

Dengan mencipta pepohon rekursi pendekatan ini, kelihatan bahawa kerumitan masa adalah eksponen Selain itu, banyak langkah diulang yang menjadikan program itu berlebihan.

Pendekatan Cekap (Pengaturcaraan Dinamik)

Penyelesaian yang berkesan ialah menggunakan pengaturcaraan dinamik dan menghapuskan lebihan.

Pengaturcaraan dinamik ialah teknik di mana masalah dibahagikan kepada submasalah diselesaikan, dan keputusannya disimpan untuk mengelakkan pengulangan.

Contoh Program C++ menggunakan Pengaturcaraan Dinamik

Di bawah ialah Program C++ menggunakan Pengaturcaraan Dinamik untuk mencari jumlah semua gabungan yang diambil (1 hingga N) pada satu masa .

#include <bits/stdc++.h>
using namespace std;
//Function to find the postfix sum array
void postfix(int a[], int n) {
for (int i = n - 1; i > 0; i--)
   a[i - 1] = a[i - 1] + a[i];
}
//Function to store the previous results, so that the computations don't get repeated
void modify(int a[], int n) {
   for (int i = 1; i < n; i++)
      a[i - 1] = i * a[i];
}
//Function to find the sum of all combinations taken 1 to N at a time
void get_combinations(int a[], int n) {
   int sum = 0;
   // sum of combinations taken 1 at a time is simply the sum of the numbers 
   // from 1 - N
   for (int i = 1; i <= n; i++)
   	  sum += i;
   cout << "f(1) = " << sum <<endl;
      // Finding the sum of products for all combination
   for (int i = 1; i < n; i++) {
   	  //Function call to find the postfix array
   	  postfix(a, n - i + 1);
      // sum of products taken i+1 at a time
   	  sum = 0;
      for (int j = 1; j <= n - i; j++) {
         sum += (j * a[j]);
      }
      cout << "f(" << i + 1 << ") = " << sum <<endl;
      //Function call to modify the array for overlapping problem
      modify(a, n);
   }
}
int main() {
   int n = 5;
  int *a = new int[n];
   // storing numbers from 1 to N
   for (int i = 0; i < n; i++)
	  a[i] = i + 1;
   //Function call
   get_combinations(a, n);
   return 0;
}

Output

f(1) = 15
f(2) = 85
f(3) = 225
f(4) = 274
f(5) = 120

Kesimpulan

Dalam artikel ini, kami membincangkan masalah mencari jumlah produk semua kombinasi dari 1 hingga N.

Kami bermula dengan pendekatan brute force dengan kerumitan masa eksponen dan kemudian mengubah suai menggunakan pengaturcaraan dinamik. Program C++ untuk kedua-dua kaedah juga disediakan.

Atas ialah kandungan terperinci Jumlah hasil darab semua kombinasi yang diambil dari 1 hingga n. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!