SUMMAN AV MEDELVÄRDET AV ALLA DELMÄNGDER

Prova det på GfG Practice
#practiceLinkDiv { display: ingen !viktigt; }
Givet en array arr[] av N heltalselement är uppgiften att hitta summan av medelvärdet av alla delmängder av denna array.
Exempel:
 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  Summan av medelvärdet av alla delmängder    Prova!       Naivt tillvägagångssätt:    En naiv lösning är att iterera igenom alla möjliga delmängder få en    genomsnitt    av dem alla och lägg sedan till dem en efter en men detta kommer att ta exponentiell tid och kommer att vara omöjligt för större arrayer.    
 Vi kan få ett mönster genom att ta ett exempel    
   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)/4   Koefficienten med täljare kan förklaras på följande sätt, anta att vi itererar över delmängder med K element, då kommer nämnaren att vara K och täljaren kommer att vara r*S där 'r' anger antalet gånger ett visst arrayelement kommer att läggas till medan det itererar över delmängder av samma storlek. Genom inspektion kan vi se att r kommer att vara nCr(N - 1 n - 1) eftersom vi efter att ha placerat ett element i summeringen måste välja (n – 1) element från (N - 1) element så att varje element kommer att ha en frekvens av nCr(N - 1 n - 1) samtidigt som delmängder av samma storlek tar del av dessa element och frekvensen är lika med summan av dessa element. kommer att vara täljaren i det slutliga uttrycket.   
   I koden nedan    nCr implementeras med en dynamisk programmeringsmetod    du kan läsa mer om det här   
 C++      // C++ program to get sum of average of all subsets   #include          using     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  ;   }   
  Java      // 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_m   
  C#      // 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 Sam007   
  JavaScript       <  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>   
  PHP         // 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.    ?>   
  Python3      # Python3 program to get sum   # of average of all subsets   # Returns value of Binomial   # Coefficient C(n k)   def   nCr  (  n     k  ):   C   =   [[  0   for   i   in   range  (  k   +   1  )]   for   j   in   range  (  n   +   1  )]   # Calculate value of Binomial    # Coefficient in bottom up manner   for   i   in   range  (  n   +   1  ):   for   j   in   range  (  min  (  i     k  )   +   1  ):   # Base Cases   if   (  j   ==   0   or   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   def   resultOfAllSubsets  (  arr     N  ):   result   =   0.0   # Initialize result   # Find sum of elements   sum   =   0   for   i   in   range  (  N  ):   sum   +=   arr  [  i  ]   # looping once for all subset of same size   for   n   in   range  (  1     N   +   1  ):   # 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   =   [  2     3     5     7  ]   N   =   len  (  arr  )   print  (  resultOfAllSubsets  (  arr     N  ))   # This code is contributed by Anant Agarwal.   
    
  Produktion   63.75 
     Tidskomplexitet:    På  ³ )   
    Hjälputrymme:    På  ² )  
      Effektivt tillvägagångssätt: rymdoptimering O(1)     
 För att optimera rymdkomplexiteten för ovanstående tillvägagångssätt kan vi använda ett mer effektivt tillvägagångssätt som undviker behovet av hela matrisen     C[][]    att lagra binomialkoefficienter. Istället kan vi använda en kombinationsformel för att beräkna binomialkoefficienten direkt när det behövs.  
      Implementeringssteg:    
    Iterera över elementen i arrayen och beräkna summan av alla element.  
  Iterera över varje delmängdsstorlek från 1 till N.  
  Inuti slingan beräkna    genomsnitt    av summan av element multiplicerat med binomialkoefficienten för delmängdsstorleken. Lägg till det beräknade genomsnittet till resultatet.  
  Returnera det slutliga resultatet.  
 
     Genomförande:    
 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  ))   
     
    Produktion    
   63.75      Tidskomplexitet:    O(n^2)   
    Hjälputrymme:    O(1)  
       
  
    
         Skapa frågesport