Summen av gjennomsnittet av alle delmengder
Prøv det på GfG Practice 
#practiceLinkDiv { display: ingen !viktig; }
#practiceLinkDiv { display: ingen !viktig; } Gitt en matrise arr[] av N heltallselementer er oppgaven å finne summen av gjennomsnittet av alle delmengder av denne matrisen.
Eksempel:
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 Summen av gjennomsnittet av alle delmengder Prøv det!Naiv tilnærming: En naiv løsning er å iterere gjennom alle mulige delmengder få en gjennomsnittlig av dem alle og legg dem til én etter én, men dette vil ta eksponentiell tid og vil være umulig for større matriser.
Vi kan få et mønster ved å ta et eksempelarr = [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)/4Koeffisienten med tellere kan forklares som følger anta at vi itererer over delmengder med K elementer, så vil nevneren være K og telleren vil være r*S hvor 'r' angir antall ganger et bestemt matriseelement vil bli lagt til mens det itereres over delsett av samme størrelse. Ved inspeksjon kan vi se at r vil være nCr(N - 1 n - 1) fordi etter å ha plassert ett element i summering, må vi velge (n – 1) elementer fra (N - 1) elementer slik at hvert element vil ha en frekvens på nCr(N - 1 n - 1) mens vi vurderer delmengder av samme størrelse som alle ganger frekvensen vil også være lik antall ganger summeringen. vil være telleren i det endelige uttrykket.
I koden nedenfor nCr er implementert ved hjelp av dynamisk programmeringsmetode du kan lese mer om det her
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. ?>
Produksjon63.75Tidskompleksitet: På 3 )
Hjelpeplass: På 2 )Effektiv tilnærming: plassoptimalisering O(1)
For å optimere plasskompleksiteten til tilnærmingen ovenfor kan vi bruke en mer effektiv tilnærming som unngår behovet for hele matrisen C[][] å lagre binomiale koeffisienter. I stedet kan vi bruke en kombinasjonsformel for å beregne binomialkoeffisienten direkte ved behov.Implementeringstrinn:
- Iterer over elementene i matrisen og beregn summen av alle elementene.
- Iterer over hver delsettstørrelse fra 1 til N.
- Inne i løkken beregner gjennomsnittlig av summen av elementer multiplisert med den binomiale koeffisienten for delmengdestørrelsen. Legg til det beregnede gjennomsnittet til resultatet.
- Returner det endelige resultatet.
Implementering:
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 ))
Produksjon
63.75Tidskompleksitet: O(n^2)
Hjelpeplass: O(1)Lag quiz
