La somme des produits de toutes les combinaisons prises de 1 à n

Si vous prenez les nombres un par un de 1 à n, il peut y avoir de nombreuses combinaisons.

Par exemple, si on ne prend qu'un seul numéro à la fois, le nombre de combinaisons sera nC1.

Si nous prenons deux nombres à la fois, le nombre de combinaisons sera nC2 Par conséquent, le nombre total de combinaisons sera nC1 + nC2 +… + nCn.

Pour trouver la somme de toutes les combinaisons, nous devons utiliser une méthode efficace. Sinon, la complexité temporelle et spatiale deviendra très élevée.

Énoncé du problème

Trouver la somme des produits de toutes les combinaisons de nombres prises à chaque fois de 1 à N.

N est un nombre donné.

Exemple

Entrez

N = 4

Sortie

f(1) = 10
f(2) = 35
f(3) = 50
f(4) = 24

Explication

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 

Entrez

N = 5

Sortie

f(1) = 15
f(2) = 85
f(3) = 225
f(4) = 274
f(5) = 120

Approche par force brute

La méthode de la force brute consiste à générer toutes les combinaisons de manière récursive, à trouver leurs produits, puis à trouver la somme correspondante.

Exemple de programme C++ récursif

Ce qui suit est un programme C++ récursif pour trouver la somme des produits pris à chaque fois dans toutes les combinaisons (de 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;
}

Sortie

f(1) = 15
f(2) = 85
f(3) = 225
f(4) = 274
f(5) = 120

En créant l'arbre de récursivité de cette approche, il est visible que la complexité temporelle est exponentielle. De plus, de nombreuses étapes sont répétées, ce qui rend le programme redondant.

Approche efficace (programmation dynamique)

Une solution efficace serait d'utiliser la programmation dynamique et de supprimer les redondances.

La programmation dynamique est une technique dans laquelle un problème est divisé en sous-problèmes. Les sous-problèmes sont résolus et leurs résultats sont enregistrés pour éviter les répétitions.

Exemple de programme C++ utilisant la programmation dynamique

Vous trouverez ci-dessous un programme C++ utilisant la programmation dynamique pour trouver la somme de toutes les combinaisons prises (1 à N) à la fois .

#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;
}

Sortie

f(1) = 15
f(2) = 85
f(3) = 225
f(4) = 274
f(5) = 120

Conclusion

Dans cet article, nous avons discuté du problème de trouver la somme des produits de toutes les combinaisons de 1 à N.

Nous avons commencé avec une approche par force brute avec une complexité temporelle exponentielle, puis nous l'avons modifiée à l'aide d'une programmation dynamique. Des programmes C++ pour les deux méthodes sont également fournis.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!