Die Summe der Produkte aller Kombinationen von 1 bis n

Wenn man die Zahlen einzeln von 1 bis n nimmt, kann es viele Kombinationen geben.

Wenn wir beispielsweise jeweils nur eine Zahl nehmen, beträgt die Anzahl der Kombinationen nC1.

Wenn wir zwei Zahlen gleichzeitig nehmen, beträgt die Anzahl der Kombinationen nC2. Daher beträgt die Gesamtzahl der Kombinationen nC1 + nC2 +… + nCn.

Um die Summe aller Kombinationen zu ermitteln, müssen wir eine effiziente Methode verwenden. Andernfalls wird die zeitliche und räumliche Komplexität sehr hoch.

Problemstellung

Finden Sie die Summe der Produkte aller Zahlenkombinationen von 1 bis N.

N ist eine gegebene Zahl.

Beispiel

Eintreten

N = 4

Ausgabe

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

Erklärung

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 

Eintreten

N = 5

Ausgabe

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

Brute-Force-Ansatz

Die Brute-Force-Methode besteht darin, alle Kombinationen rekursiv zu generieren, ihre Produkte zu finden und dann die entsprechende Summe zu finden.

Rekursives C++-Programmbeispiel

Das Folgende ist ein rekursives C++-Programm, um die Summe der jeweils genommenen Produkte in allen Kombinationen (von 1 bis N) zu ermitteln

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

Ausgabe

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

Durch die Erstellung des Rekursionsbaums dieses Ansatzes wird deutlich, dass die zeitliche Komplexität exponentiell ist. Außerdem werden viele Schritte wiederholt, was das Programm äußerst ineffizient macht.

Effizienter Ansatz (Dynamische Programmierung)

Eine effektive Lösung wäre die Verwendung dynamischer Programmierung und die Beseitigung der Redundanzen.

Dynamische Programmierung ist eine Technik, bei der ein Problem in Teilprobleme unterteilt wird. Die Teilprobleme werden gelöst und ihre Ergebnisse gespeichert, um Wiederholungen zu vermeiden.

Beispiel für ein C++-Programm mit dynamischer Programmierung

Unten sehen Sie ein C++-Programm, das dynamische Programmierung verwendet, um die Summe aller Kombinationen (1 bis N) gleichzeitig zu ermitteln.

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

Ausgabe

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

Fazit

In diesem Artikel haben wir das Problem besprochen, die Summe der Produkte aller Kombinationen von 1 bis N zu finden.

Wir haben mit einem Brute-Force-Ansatz mit exponentieller Zeitkomplexität begonnen und ihn dann mithilfe dynamischer Programmierung modifiziert. Für beide Methoden stehen auch C++-Programme zur Verfügung.

Das obige ist der detaillierte Inhalt vonDie Summe der Produkte aller Kombinationen von 1 bis n. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!