给定N，我们必须求所有的乘积之和 组合 每次服用1至N。简单地说，我们必须找到所有组合的乘积之和，每次取1，然后每次取2，然后每次取3，直到每次取N。 如果仔细考虑这个问题，N的一个大值可能会导致产生许多组合。 例如：
null
Input : N = 3Output : f(1) = 6 f(2) = 11 f(3) = 6Explanation: f(x) is sum of products of all combination taken x at a time 1 + 2 + 3 = 6 f(2) = (1*2) + (1*3) + (2*3) = 11 f(3) = (1*2*3) Input : N = 4Output : f(1) = 10 f(2) = 35 f(3) = 50 f(4) = 24Explanation: 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
A. 蛮力 方法是产生所有的组合，然后找到它们的乘积和总和。 递归可以一次生成x的组合。 例子： N=4次，每次3次
![图片[1]-一次获得的所有组合的乘积之和（1到n）-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_permutation-1-1024x690.jpg)
C++
// Program to find SOP of all combination taken // (1 to N) at a time using brute force #include <iostream> using namespace std; // to store sum of every combination int sum = 0; void Combination( int a[], int combi[], int n, int r, int depth, int index) { // if we have reached sufficient depth if (index == r) { // find the product of combination int product = 1; for ( int i = 0; i < r; i++) product = product * combi[i]; // add the product into sum sum += product; return ; } // recursion to produce different combination for ( int i = depth; i < n; i++) { combi[index] = a[i]; Combination(a, combi, n, r, i + 1, index + 1); } } // function to print sum of products of // all combination taken 1-N at a time void allCombination( int a[], int n) { for ( int i = 1; i <= n; i++) { // creating temporary array for storing // combination int *combi = new int [i]; // call combination with r = i // for combination taken i at a time Combination(a, combi, n, i, 0, 0); // displaying sum cout << "f(" << i << ") --> " << sum << "" ; sum = 0; // free from heap area free (combi); } } // Driver's code int main() { int n = 5; int *a = new int [n]; // storing numbers from 1-N in array for ( int i = 0; i < n; i++) a[i] = i + 1; // calling allCombination allCombination(a, n); return 0; } |
JAVA
// Program to find SOP of // all combination taken // (1 to N) at a time using // brute force import java.io.*; class GFG { // to store sum of // every combination static int sum = 0 ; static void Combination( int []a, int []combi, int n, int r, int depth, int index) { // if we have reached // sufficient depth if (index == r) { // find the product // of combination int product = 1 ; for ( int i = 0 ; i < r; i++) product = product * combi[i]; // add the product into sum sum += product; return ; } // recursion to produce // different combination for ( int i = depth; i < n; i++) { combi[index] = a[i]; Combination(a, combi, n, r, i + 1 , index + 1 ); } } // function to print sum of // products of all combination // taken 1-N at a time static void allCombination( int []a, int n) { for ( int i = 1 ; i <= n; i++) { // creating temporary array // for storing combination int []combi = new int [i]; // call combination with // r = i for combination // taken i at a time Combination(a, combi, n, i, 0 , 0 ); // displaying sum System.out.print( "f(" + i + ") --> " + sum + "" ); sum = 0 ; } } // Driver code public static void main(String args[]) { int n = 5 ; int []a = new int [n]; // storing numbers // from 1-N in array for ( int i = 0 ; i < n; i++) a[i] = i + 1 ; // calling allCombination allCombination(a, n); } } // This code is contributed by // Manish Shaw(manishshaw1) |
Python3
# Python3 Program to find SOP of all combination # taken (1 to N) at a time using brute force # to store sum of every combination def Combination(a, combi, n, r, depth, index): global Sum # if we have reached sufficient depth if index = = r: # find the product of combination product = 1 for i in range (r): product = product * combi[i] # add the product into sum Sum + = product return # recursion to produce different # combination for i in range (depth, n): combi[index] = a[i] Combination(a, combi, n, r, i + 1 , index + 1 ) # function to print sum of products of # all combination taken 1-N at a time def allCombination(a, n): global Sum for i in range ( 1 , n + 1 ): # creating temporary array for # storing combination combi = [ 0 ] * i # call combination with r = i # for combination taken i at a time Combination(a, combi, n, i, 0 , 0 ) # displaying sum print ( "f(" , i, ") --> " , Sum ) Sum = 0 # Driver Code Sum = 0 n = 5 a = [ 0 ] * n # storing numbers from 1-N in array for i in range (n): a[i] = i + 1 # calling allCombination allCombination(a, n) # This code is contributed by PranchalK |
C#
// Program to find SOP of // all combination taken // (1 to N) at a time using // brute force using System; class GFG { // to store sum of // every combination static int sum = 0; static void Combination( int []a, int []combi, int n, int r, int depth, int index) { // if we have reached // sufficient depth if (index == r) { // find the product // of combination int product = 1; for ( int i = 0; i < r; i++) product = product * combi[i]; // add the product into sum sum += product; return ; } // recursion to produce // different combination for ( int i = depth; i < n; i++) { combi[index] = a[i]; Combination(a, combi, n, r, i + 1, index + 1); } } // function to print sum of // products of all combination // taken 1-N at a time static void allCombination( int []a, int n) { for ( int i = 1; i <= n; i++) { // creating temporary array // for storing combination int []combi = new int [i]; // call combination with // r = i for combination // taken i at a time Combination(a, combi, n, i, 0, 0); // displaying sum Console.Write( "f(" + i + ") --> " + sum + "" ); sum = 0; } } // Driver code static void Main() { int n = 5; int []a = new int [n]; // storing numbers // from 1-N in array for ( int i = 0; i < n; i++) a[i] = i + 1; // calling allCombination allCombination(a, n); } } // This code is contributed by // Manish Shaw(manishshaw1) |
Javascript
<script> // JavaScript program to find sum of all combination taken // (1 to N) at a time using brute force // to store sum of // every combination let sum = 0; function Combination(a, combi, n, r, depth, index) { // if we have reached // sufficient depth if (index == r) { // find the product // of combination let product = 1; for (let i = 0; i < r; i++) product = product * combi[i]; // add the product into sum sum += product; return ; } // recursion to produce // different combination for (let i = depth; i < n; i++) { combi[index] = a[i]; Combination(a, combi, n, r, i + 1, index + 1); } } // function to print sum of // products of all combination // taken 1-N at a time function allCombination(a, n) { for (let i = 1; i <= n; i++) { // creating temporary array // for storing combination let combi = []; // call combination with // r = i for combination // taken i at a time Combination(a, combi, n, i, 0, 0); // displaying sum document.write( "f(" + i + ") --> " + sum + "<br/>" ); sum = 0; } } // Driver code let n = 5; let a = []; // storing numbers // from 1-N in array for (let i = 0; i < n; i++) a[i] = i + 1; // calling allCombination allCombination(a, n); </script> |
输出：
f(1) --> 15f(2) --> 85f(3) --> 225f(4) --> 274f(5) --> 120
这个 时间复杂性 当N的值较大时，上述代码的值是指数的。 一 有效方法 就是使用动态规划的概念。我们不必每次都求乘积的和。我们可以利用以前的结果。 让我们举一个例子：N=4
![图片[2]-一次获得的所有组合的乘积之和（1到n）-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_permutation2.jpg)
C++
// CPP Program to find sum of all combination takne // (1 to N) at a time using dynamic programming #include <iostream> using namespace std; // 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]; } // modify the array such that we don't have to // compute the products which are obtained before void modify( int a[], int n) { for ( int i = 1; i < n; i++) a[i - 1] = i * a[i]; } // finding sum of all combination taken 1 to N at a time void allCombination( int a[], int n) { int sum = 0; // sum taken 1 at time is simply sum of 1 - N for ( int i = 1; i <= n; i++) sum += i; cout << "f(1) --> " << sum << "" ; // for sum of products for all combination for ( int i = 1; i < n; i++) { // finding 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 << "" ; // modify the array for overlapping problem modify(a, n); } } // Driver's Code 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; // calling allCombination allCombination(a, n); return 0; } |
JAVA
// Java Program to find sum of all combination takne // (1 to N) at a time using dynamic programming import java.util.*; class GFG { // find the postfix sum array static void postfix( int a[], int n) { for ( int i = n - 1 ; i > 0 ; i--) { a[i - 1 ] = a[i - 1 ] + a[i]; } } // modify the array such that we don't // have to compute the products which // are obtained before static void modify( int a[], int n) { for ( int i = 1 ; i < n; i++) { a[i - 1 ] = i * a[i]; } } // finding sum of all combination // taken 1 to N at a time static void allCombination( int a[], int n) { int sum = 0 ; // sum taken 1 at time is simply sum of 1 - N for ( int i = 1 ; i <= n; i++) { sum += i; } System.out.println( "f(1) --> " + sum); // for sum of products for all combination for ( int i = 1 ; i < n; i++) { // finding 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]); } System.out.println( "f(" + (i + 1 ) + ") --> " + sum); // modify the array for overlapping problem modify(a, n); } } // Driver's Code public static void main(String[] args) { 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 ; } // calling allCombination allCombination(a, n); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 Program to find # sum of all combination takne # (1 to N) at a time using # dynamic programming # Find the postfix sum array def postfix(a, n): for i in range (n - 1 , 1 , - 1 ): a[i - 1 ] = a[i - 1 ] + a[i] # Modify the array such # that we don't have to # compute the products # which are obtained before def modify(a, n): for i in range ( 1 , n): a[i - 1 ] = i * a[i]; # Finding sum of all combination # taken 1 to N at a time def allCombination(a, n): sum = 0 # sum taken 1 at time is # simply sum of 1 - N for i in range ( 1 , n + 1 ): sum + = i print ( "f(1) --> " , sum ) # for sum of products for # all combination for i in range ( 1 , n): # finding postfix array postfix(a, n - i + 1 ) # sum of products taken # i+1 at a time sum = 0 for j in range ( 1 , n - i + 1 ): sum + = (j * a[j]) print ( "f(" , i + 1 , ") --> " , sum ) # modify the array for # overlapping problem modify(a, n) # Driver's Code if __name__ = = "__main__" : n = 5 a = [ 0 ] * n # storing numbers # from 1 to N for i in range (n): a[i] = i + 1 # calling allCombination allCombination(a, n) # This code is contributed by Chitranayal |
C#
// C# Program to find sum of all combination takne // (1 to N) at a time using dynamic programming using System; class GFG { // find the postfix sum array static void postfix( int []a, int n) { for ( int i = n - 1; i > 0; i--) { a[i - 1] = a[i - 1] + a[i]; } } // modify the array such that we don't // have to compute the products which // are obtained before static void modify( int []a, int n) { for ( int i = 1; i < n; i++) { a[i - 1] = i * a[i]; } } // finding sum of all combination // taken 1 to N at a time static void allCombination( int []a, int n) { int sum = 0; // sum taken 1 at time is simply sum of 1 - N for ( int i = 1; i <= n; i++) { sum += i; } Console.WriteLine( "f(1) --> " + sum); // for sum of products for all combination for ( int i = 1; i < n; i++) { // finding 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]); } Console.WriteLine( "f(" + (i + 1) + ") --> " + sum); // modify the array for overlapping problem modify(a, n); } } // Driver's Code public static void Main(String[] args) { 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; } // calling allCombination allCombination(a, n); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript Program to find sum of all combination takne // (1 to N) at a time using dynamic programming // find the postfix sum array function postfix(a,n) { for (let i = n - 1; i > 0; i--) { a[i - 1] = a[i - 1] + a[i]; } } // modify the array such that we don't // have to compute the products which // are obtained before function modify(a,n) { for (let i = 1; i < n; i++) { a[i - 1] = i * a[i]; } } // finding sum of all combination // taken 1 to N at a time function allCombination(a,n) { let sum = 0; // sum taken 1 at time is simply sum of 1 - N for (let i = 1; i <= n; i++) { sum += i; } document.write( "f(1) --> " + sum+ "<br>" ); // for sum of products for all combination for (let i = 1; i < n; i++) { // finding postfix array postfix(a, n - i + 1); // sum of products taken i+1 at a time sum = 0; for (let j = 1; j <= n - i; j++) { sum += (j * a[j]); } document.write( "f(" + (i + 1) + ") --> " + sum+ "<br>" ); // modify the array for overlapping problem modify(a, n); } } // Driver's Code let n = 5; let a = new Array(n); // storing numbers from 1 to N for (let i = 0; i < n; i++) { a[i] = i + 1; } // calling allCombination allCombination(a, n); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
f(1) --> 15f(2) --> 85f(3) --> 225f(4) --> 274f(5) --> 120
这个 时间复杂性 上述方法中的O（n^2）远比蛮力法好。 对于较大的N值，您还可以找到这两种方法的执行时间，并且可以自己看到差异。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
