从 1 到 n 取任意个数的组合的乘积之和
如果一次取 1 到 n 个数字,那么可能会有多种组合。
例如,如果我们一次取一个数字,组合的数量将是 nC1。
如果我们一次取两个数字,组合的数量将是 nC2。因此,组合的总数将是 nC1 + nC2 +… + nCn。
要找到所有组合的总和,我们将不得不使用一种有效的方法。否则,时间和空间复杂度将变得非常高。
问题陈述
求从 1 到 N 取任意个数的组合的乘积之和。
N 是一个给定的数字。
示例
输入
N = 4
输出
f(1) = 10 f(2) = 35 f(3) = 50 f(4) = 24
解释
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
输出
f(1) = 15 f(2) = 85 f(3) = 225 f(4) = 274 f(5) = 120
暴力法
暴力法是通过递归生成所有组合,找到它们的乘积,然后找到相应的和。
示例递归 C++ 程序
下面是一个递归 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
通过创建这种方法的递归树,可以看出时间复杂度是指数级的。此外,许多步骤重复出现,这使得程序冗余。因此,它效率非常低。
高效方法(动态规划)
一个有效的解决方案是使用动态规划并消除冗余。
动态规划是一种将问题分解成子问题的方法。解决子问题并将结果保存起来以避免重复。
使用动态规划的示例 C++ 程序
下面是一个使用动态规划的 C++ 程序,用于查找从 1 到 N 取任意个数的组合的和。
#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
结论
在本文中,我们讨论了求从 1 到 N 取任意个数的组合的乘积之和的问题。
我们从时间复杂度为指数级的暴力法开始,然后使用动态规划对其进行了改进。还给出了两种方法的 C++ 程序。
广告