Heim > Artikel > Backend-Entwicklung > 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.
Finden Sie die Summe der Produkte aller Zahlenkombinationen von 1 bis N.
N ist eine gegebene Zahl.
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
Die Brute-Force-Methode besteht darin, alle Kombinationen rekursiv zu generieren, ihre Produkte zu finden und dann die entsprechende Summe zu finden.
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; }
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.
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.
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; }
f(1) = 15 f(2) = 85 f(3) = 225 f(4) = 274 f(5) = 120
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!