Suma del promedio de todos los subconjuntos
Pruébalo en GfG Practice 
#practiceLinkDiv { mostrar: ninguno !importante; }
#practiceLinkDiv { mostrar: ninguno !importante; } Dada una matriz arr[] de N elementos enteros, la tarea es encontrar la suma del promedio de todos los subconjuntos de esta matriz.
Ejemplo:
Input : arr[] = [2 3 5]
Output : 23.33
Explanation : Subsets with their average are
[2] average = 2/1 = 2
[3] average = 3/1 = 3
[5] average = 5/1 = 5
[2 3] average = (2+3)/2 = 2.5
[2 5] average = (2+5)/2 = 3.5
[3 5] average = (3+5)/2 = 4
[2 3 5] average = (2+3+5)/3 = 3.33
Sum of average of all subset is
2 + 3 + 5 + 2.5 + 3.5 + 4 + 3.33 = 23.33 Recommended Practice Suma del promedio de todos los subconjuntos ¡Pruébalo!Enfoque ingenuo: Una solución ingenua es iterar a través de todos los subconjuntos posibles para obtener un promedio de todos ellos y luego agregarlos uno por uno, pero esto llevará un tiempo exponencial y no será factible para matrices más grandes.
Podemos obtener un patrón tomando un ejemplo.arr = [a0 a1 a2 a3]
sum of average =
a0/1 + a1/1 + a2/2 + a3/1 +
(a0+a1)/2 + (a0+a2)/2 + (a0+a3)/2 + (a1+a2)/2 +
(a1+a3)/2 + (a2+a3)/2 +
(a0+a1+a2)/3 + (a0+a2+a3)/3 + (a0+a1+a3)/3 +
(a1+a2+a3)/3 +
(a0+a1+a2+a3)/4
If S = (a0+a1+a2+a3) then above expression
can be rearranged as below
sum of average = (S)/1 + (3*S)/2 + (3*S)/3 + (S)/4El coeficiente con numeradores se puede explicar de la siguiente manera, supongamos que estamos iterando sobre subconjuntos con K elementos, entonces el denominador será K y el numerador será r*S donde 'r' denota el número de veces que se agregará un elemento de matriz particular mientras se itera sobre subconjuntos del mismo tamaño. Por inspección, podemos ver que r será nCr(N - 1 n - 1) porque después de colocar un elemento en la suma debemos elegir (n - 1) elementos de (N - 1) elementos para que cada elemento tenga una frecuencia de nCr (N - 1 n - 1) mientras consideramos subconjuntos del mismo tamaño, ya que todos los elementos participan en la suma el mismo número de veces, esto también será la frecuencia de S y será el numerador en la expresión final.
En el siguiente código nCr se implementa mediante un método de programación dinámica puedes leer más sobre eso aquí
C++Java// C++ program to get sum of average of all subsets #includeusing namespace std ; // Returns value of Binomial Coefficient C(n k) int nCr ( int n int k ) { int C [ n + 1 ][ k + 1 ]; int i j ; // Calculate value of Binomial Coefficient in bottom // up manner for ( i = 0 ; i <= n ; i ++ ) { for ( j = 0 ; j <= min ( i k ); j ++ ) { // Base Cases if ( j == 0 || j == i ) C [ i ][ j ] = 1 ; // Calculate value using previously stored // values else C [ i ][ j ] = C [ i - 1 ][ j - 1 ] + C [ i - 1 ][ j ]; } } return C [ n ][ k ]; } // method returns sum of average of all subsets double resultOfAllSubsets ( int arr [] int N ) { double result = 0.0 ; // Initialize result // Find sum of elements int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) sum += arr [ i ]; // looping once for all subset of same size for ( int n = 1 ; n <= N ; n ++ ) /* each element occurs nCr(N-1 n-1) times while considering subset of size n */ result += ( double )( sum * ( nCr ( N - 1 n - 1 ))) / n ; return result ; } // Driver code to test above methods int main () { int arr [] = { 2 3 5 7 }; int N = sizeof ( arr ) / sizeof ( int ); cout < < resultOfAllSubsets ( arr N ) < < endl ; return 0 ; } C#// java program to get sum of // average of all subsets import java.io.* ; class GFG { // Returns value of Binomial // Coefficient C(n k) static int nCr ( int n int k ) { int C [][] = new int [ n + 1 ][ k + 1 ] ; int i j ; // Calculate value of Binomial // Coefficient in bottom up manner for ( i = 0 ; i <= n ; i ++ ) { for ( j = 0 ; j <= Math . min ( i k ); j ++ ) { // Base Cases if ( j == 0 || j == i ) C [ i ][ j ] = 1 ; // Calculate value using // previously stored values else C [ i ][ j ] = C [ i - 1 ][ j - 1 ] + C [ i - 1 ][ j ] ; } } return C [ n ][ k ] ; } // method returns sum of average of all subsets static double resultOfAllSubsets ( int arr [] int N ) { // Initialize result double result = 0.0 ; // Find sum of elements int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) sum += arr [ i ] ; // looping once for all subset of same size for ( int n = 1 ; n <= N ; n ++ ) /* each element occurs nCr(N-1 n-1) times while considering subset of size n */ result += ( double )( sum * ( nCr ( N - 1 n - 1 ))) / n ; return result ; } // Driver code to test above methods public static void main ( String [] args ) { int arr [] = { 2 3 5 7 }; int N = arr . length ; System . out . println ( resultOfAllSubsets ( arr N )); } } // This code is contributed by vt_mJavaScript// C# program to get sum of // average of all subsets using System ; class GFG { // Returns value of Binomial // Coefficient C(n k) static int nCr ( int n int k ) { int [ ] C = new int [ n + 1 k + 1 ]; int i j ; // Calculate value of Binomial // Coefficient in bottom up manner for ( i = 0 ; i <= n ; i ++ ) { for ( j = 0 ; j <= Math . Min ( i k ); j ++ ) { // Base Cases if ( j == 0 || j == i ) C [ i j ] = 1 ; // Calculate value using // previously stored values else C [ i j ] = C [ i - 1 j - 1 ] + C [ i - 1 j ]; } } return C [ n k ]; } // method returns sum of average // of all subsets static double resultOfAllSubsets ( int [] arr int N ) { // Initialize result double result = 0.0 ; // Find sum of elements int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) sum += arr [ i ]; // looping once for all subset // of same size for ( int n = 1 ; n <= N ; n ++ ) /* each element occurs nCr(N-1 n-1) times while considering subset of size n */ result += ( double )( sum * ( nCr ( N - 1 n - 1 ))) / n ; return result ; } // Driver code to test above methods public static void Main () { int [] arr = { 2 3 5 7 }; int N = arr . Length ; Console . WriteLine ( resultOfAllSubsets ( arr N )); } } // This code is contributed by Sam007PHP< script > // javascript program to get sum of // average of all subsets // Returns value of Binomial // Coefficient C(n k) function nCr ( n k ) { let C = new Array ( n + 1 ); for ( let i = 0 ; i <= n ; i ++ ) { C [ i ] = new Array ( k + 1 ); for ( let j = 0 ; j <= k ; j ++ ) { C [ i ][ j ] = 0 ; } } let i j ; // Calculate value of Binomial // Coefficient in bottom up manner for ( i = 0 ; i <= n ; i ++ ) { for ( j = 0 ; j <= Math . min ( i k ); j ++ ) { // Base Cases if ( j == 0 || j == i ) C [ i ][ j ] = 1 ; // Calculate value using // previously stored values else C [ i ][ j ] = C [ i - 1 ][ j - 1 ] + C [ i - 1 ][ j ]; } } return C [ n ][ k ]; } // method returns sum of average of all subsets function resultOfAllSubsets ( arr N ) { // Initialize result let result = 0.0 ; // Find sum of elements let sum = 0 ; for ( let i = 0 ; i < N ; i ++ ) sum += arr [ i ]; // looping once for all subset of same size for ( let n = 1 ; n <= N ; n ++ ) /* each element occurs nCr(N-1 n-1) times while considering subset of size n */ result += ( sum * ( nCr ( N - 1 n - 1 ))) / n ; return result ; } let arr = [ 2 3 5 7 ]; let N = arr . length ; document . write ( resultOfAllSubsets ( arr N )); < /script>Python3// PHP program to get sum // of average of all subsets // Returns value of Binomial // Coefficient C(n k) function nCr ( $n $k ) { $C [ $n + 1 ][ $k + 1 ] = 0 ; $i ; $j ; // Calculate value of Binomial // Coefficient in bottom up manner for ( $i = 0 ; $i <= $n ; $i ++ ) { for ( $j = 0 ; $j <= min ( $i $k ); $j ++ ) { // Base Cases if ( $j == 0 || $j == $i ) $C [ $i ][ $j ] = 1 ; // Calculate value using // previously stored values else $C [ $i ][ $j ] = $C [ $i - 1 ][ $j - 1 ] + $C [ $i - 1 ][ $j ]; } } return $C [ $n ][ $k ]; } // method returns sum of // average of all subsets function resultOfAllSubsets ( $arr $N ) { // Initialize result $result = 0.0 ; // Find sum of elements $sum = 0 ; for ( $i = 0 ; $i < $N ; $i ++ ) $sum += $arr [ $i ]; // looping once for all // subset of same size for ( $n = 1 ; $n <= $N ; $n ++ ) /* each element occurs nCr(N-1 n-1) times while considering subset of size n */ $result += (( $sum * ( nCr ( $N - 1 $n - 1 ))) / $n ); return $result ; } // Driver Code $arr = array ( 2 3 5 7 ); $N = sizeof ( $arr ) / sizeof ( $arr [ 0 ]); echo resultOfAllSubsets ( $arr $N ) ; // This code is contributed by nitin mittal. ?>
Producción63.75Complejidad del tiempo: En 3 )
Espacio Auxiliar: En 2 )Enfoque eficiente: optimización del espacio O(1)
Para optimizar la complejidad espacial del enfoque anterior, podemos utilizar un enfoque más eficiente que evite la necesidad de toda la matriz. DO[][] para almacenar coeficientes binomiales. En su lugar, podemos usar una fórmula combinada para calcular el coeficiente binomial directamente cuando sea necesario.Pasos de implementación:
- Itere sobre los elementos de la matriz y calcule la suma de todos los elementos.
- Itere sobre cada tamaño de subconjunto de 1 a N.
- Dentro del bucle calcula el promedio de la suma de elementos multiplicada por el coeficiente binomial para el tamaño del subconjunto. Sume el promedio calculado al resultado.
- Devuelve el resultado final.
Implementación:
C++ #include using namespace std ; // Method to calculate binomial coefficient C(n k) int binomialCoeff ( int n int k ) { int res = 1 ; // Since C(n k) = C(n n-k) if ( k > n - k ) k = n - k ; // Calculate value of [n * (n-1) * ... * (n-k+1)] / [k * (k-1) * ... * 1] for ( int i = 0 ; i < k ; i ++ ) { res *= ( n - i ); res /= ( i + 1 ); } return res ; } // Method to calculate the sum of the average of all subsets double resultOfAllSubsets ( int arr [] int N ) { double result = 0.0 ; int sum = 0 ; // Calculate the sum of elements for ( int i = 0 ; i < N ; i ++ ) sum += arr [ i ]; // Loop for each subset size for ( int n = 1 ; n <= N ; n ++ ) result += ( double )( sum * binomialCoeff ( N - 1 n - 1 )) / n ; return result ; } // Driver code to test the above methods int main () { int arr [] = { 2 3 5 7 }; int N = sizeof ( arr ) / sizeof ( int ); cout < < resultOfAllSubsets ( arr N ) < < endl ; return 0 ; }
Java import java.util.Arrays ; public class Main { // Method to calculate binomial coefficient C(n k) static int binomialCoeff ( int n int k ) { int res = 1 ; // Since C(n k) = C(n n-k) if ( k > n - k ) k = n - k ; // Calculate value of [n * (n-1) * ... * (n-k+1)] / [k * (k-1) * ... * 1] for ( int i = 0 ; i < k ; i ++ ) { res *= ( n - i ); res /= ( i + 1 ); } return res ; } // Method to calculate the sum of the average of all subsets static double resultOfAllSubsets ( int arr [] int N ) { double result = 0.0 ; int sum = 0 ; // Calculate the sum of elements for ( int i = 0 ; i < N ; i ++ ) sum += arr [ i ] ; // Loop for each subset size for ( int n = 1 ; n <= N ; n ++ ) result += ( double ) ( sum * binomialCoeff ( N - 1 n - 1 )) / n ; return result ; } // Driver code to test the above methods public static void main ( String [] args ) { int arr [] = { 2 3 5 7 }; int N = arr . length ; System . out . println ( resultOfAllSubsets ( arr N )); } }
C# using System ; public class MainClass { // Method to calculate binomial coefficient C(n k) static int BinomialCoeff ( int n int k ) { int res = 1 ; // Since C(n k) = C(n n-k) if ( k > n - k ) k = n - k ; // Calculate value of [n * (n-1) * ... * (n-k+1)] / [k * (k-1) * ... * 1] for ( int i = 0 ; i < k ; i ++ ) { res *= ( n - i ); res /= ( i + 1 ); } return res ; } // Method to calculate the sum of the average of all subsets static double ResultOfAllSubsets ( int [] arr int N ) { double result = 0.0 ; int sumVal = 0 ; // Calculate the sum of elements for ( int i = 0 ; i < N ; i ++ ) sumVal += arr [ i ]; // Loop for each subset size for ( int n = 1 ; n <= N ; n ++ ) result += ( double )( sumVal * BinomialCoeff ( N - 1 n - 1 )) / n ; return result ; } // Driver code to test the above methods public static void Main () { int [] arr = { 2 3 5 7 }; int N = arr . Length ; Console . WriteLine ( ResultOfAllSubsets ( arr N )); } }
JavaScript // Function to calculate binomial coefficient C(n k) function binomialCoeff ( n k ) { let res = 1 ; // Since C(n k) = C(n n-k) if ( k > n - k ) k = n - k ; // Calculate value of [n * (n-1) * ... * (n-k+1)] / [k * (k-1) * ... * 1] for ( let i = 0 ; i < k ; i ++ ) { res *= ( n - i ); res /= ( i + 1 ); } return res ; } // Function to calculate the sum of the average of all subsets function resultOfAllSubsets ( arr ) { let result = 0.0 ; let sum = arr . reduce (( acc val ) => acc + val 0 ); // Loop for each subset size for ( let n = 1 ; n <= arr . length ; n ++ ) { result += ( sum * binomialCoeff ( arr . length - 1 n - 1 )) / n ; } return result ; } const arr = [ 2 3 5 7 ]; console . log ( resultOfAllSubsets ( arr ));
Python3 # Method to calculate binomial coefficient C(n k) def binomialCoeff ( n k ): res = 1 # Since C(n k) = C(n n-k) if k > n - k : k = n - k # Calculate value of [n * (n-1) * ... * (n-k+1)] / [k * (k-1) * ... * 1] for i in range ( k ): res *= ( n - i ) res //= ( i + 1 ) return res # Method to calculate the sum of the average of all subsets def resultOfAllSubsets ( arr N ): result = 0.0 sum_val = 0 # Calculate the sum of elements for i in range ( N ): sum_val += arr [ i ] # Loop for each subset size for n in range ( 1 N + 1 ): result += ( sum_val * binomialCoeff ( N - 1 n - 1 )) / n return result # Driver code to test the above methods arr = [ 2 3 5 7 ] N = len ( arr ) print ( resultOfAllSubsets ( arr N ))
Producción
63.75Complejidad del tiempo: O(n^2)
Espacio Auxiliar: O(1)Crear cuestionario
