例如，如果我们一次只取一个数字，组合的数量将为 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.
要找到所有组合的总和，我们必须使用一种高效的方法。否则，时间和空间复杂度会变得非常高。
Problem Statement
找出从1到N中每次取出的数字的所有组合的乘积之和。
N is a given number.
示例
输入
N = 4
登录后复制
Output
f(1) = 10f(2) = 35f(3) = 50f(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 = 10f(2) = (1*2) + (1*3) + (1*4) + (2*3) + (2*4) + (3*4) = 35f(3) = (1*2*3) + (1*2*4) +(1*3*4) + (2*3*4) = 50f(4) = (1*2*3*4) = 24
登录后复制
输入
N = 5
登录后复制
Output
f(1) = 15f(2) = 85f(3) = 225f(4) = 274f(5) = 120
登录后复制
Brute Force Approach
暴力法是通过递归生成所有组合，找出它们的乘积，然后找到相应的和。
递归C++程序示例
下面是一个递归的C++程序，用于找到所有组合中（从1到N）每次取的乘积的和
#include using namespace std;//sum of each combinationint sum = 0;void create_combination(vectorvec, vectorcombinations, 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 vec, int n) { for (int i = 1; i 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 vec(n); // storing numbers from 1-N in the vector for (int i = 0; i Output
f(1) = 15f(2) = 85f(3) = 225f(4) = 274f(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 inefficient.
Efficient Approach (Dynamic Programming)
An effective solution would be to use dynamic programming and remove the redundancies.
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
Below is a C++ Program using Dynamic Programming to find the sum of all combinations taken (1 to N) at a time .
#include using namespace std;//Function to find the postfix sum arrayvoid 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 repeatedvoid modify(int a[], int n) { for (int i = 1; i Output
f(1) = 15f(2) = 85f(3) = 225f(4) = 274f(5) = 120
登录后复制
结论
在这篇文章中，我们讨论了找到从1到N中所有组合的乘积之和的问题。
我们从指数时间复杂度的暴力方法开始，然后使用动态规划进行了修改。同时还提供了两种方法的C++程序。
以上就是所有从1到n中取出的组合的乘积之和的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2583389.html
