如果從1到n逐一取數，可能會有多種組合。
例如，如果我們一次只取一個數字，組合的數量將為 nC1。
If we take two numbers at a time, the number of combinations will be nC2. Hence, the total number of combinations will be nC1 nC2 … nCn.
要找到所有組合的總和，我們必須使用一個有效率的方法。否則，時間和空間複雜度會變得非常高。
找出從1到N中每次取出的數字的所有組合的乘積總和。
N is a given number.
輸入
N = 4
Output
#f(1) = 10 f(2) = 35 f(3) = 50 f(4) = 24
Explanation
#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
輸入
N = 5
Output
#f(1) = 15 f(2) = 85 f(3) = 225 f(4) = 274 f(5) = 120
暴力法是透過遞歸來產生所有組合，找出它們的乘積，然後找到對應的和。
下面是一個遞歸的C 程序，用於找到所有組合中（從1到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;
}
f(1) = 15 f(2) = 85 f(3) = 225 f(4) = 274 f(5) = 120
By creating the recursion tree of this approach, it is visible that the time complexity is exponential. Also, many steps get repeated which makes the program redundant. Hence, it is highly in inefficient.##.
Efficient Approach (Dynamic Programming)Dynamic programming is a technique in which a problem is divided into subproblems. The subproblems are solved, and their results are saved to avoid repetitions.
Example C Program using Dynamic Programming
#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
我們從指數時間複雜度的暴力方法開始，然後使用動態規劃進行了修改。同時也提供了兩種方法的C 程序。
以上是所有從1到n中取出的組合的乘積總和的詳細內容。更多資訊請關注PHP中文網其他相關文章！
