C++ 每次取出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++程序。