Suma de la mitjana de tots els subconjunts
Prova-ho a GfG Practice 
#practiceLinkDiv { mostrar: cap !important; }
#practiceLinkDiv { mostrar: cap !important; } Donada una matriu arr[] de N elements enters, la tasca és trobar la suma de la mitjana de tots els subconjunts d'aquesta matriu.
Exemple:
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 de la mitjana de tots els subconjunts Prova-ho!Enfocament ingenu: Una solució ingènua és iterar a través de tots els subconjunts possibles obtenir un mitjana de tots i després afegir-los un per un, però això trigarà un temps exponencial i serà inviable per a matrius més grans.
Podem obtenir un patró prenent un exemplearr = [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 coeficient amb numeradors es pot explicar de la següent manera, suposem que estem iterant sobre subconjunts amb K elements, llavors el denominador serà K i el numerador serà r * S on "r" denota el nombre de vegades que s'afegirà un element de matriu en particular mentre iterarem sobre subconjunts de la mateixa mida. Per inspecció podem veure que r serà nCr(N - 1 n - 1) perquè després de col·locar un element en la suma hem de triar (n – 1) elements entre (N - 1) elements de manera que cada element tindrà una freqüència de nCr(N - 1 n - 1) mentre es consideren subconjunts de la mateixa mida que tots els elements participen en la suma i la freqüència final serà igual a la freqüència del numerador en la suma.
En el codi següent nCr s'implementa mitjançant el mètode de programació dinàmica podeu llegir més sobre això 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. ?>
Sortida63.75Complexitat temporal: O (n 3 )
Espai auxiliar: O (n 2 )Enfocament eficient: optimització de l'espai O(1)
Per optimitzar la complexitat espacial de l'enfocament anterior, podem utilitzar un enfocament més eficient que evita la necessitat de tota la matriu C[][] per emmagatzemar coeficients binomials. En canvi, podem utilitzar una fórmula de combinació per calcular el coeficient binomi directament quan sigui necessari.Passos d'implementació:
- Itera sobre els elements de la matriu i calcula la suma de tots els elements.
- Itera sobre cada mida de subconjunt d'1 a N.
- Dins del bucle calculeu el mitjana de la suma d'elements multiplicada pel coeficient binomial de la mida del subconjunt. Afegiu la mitjana calculada al resultat.
- Torna el resultat final.
Implementació:
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 ))
Sortida
63.75Complexitat temporal: O(n^2)
Espai auxiliar: O(1)Crea un qüestionari
