مجموع المتوسط لجميع المجموعات الفرعية
جربه على ممارسة GfG 
#practiceLinkDiv { العرض: لا شيء! مهم؛ }
#practiceLinkDiv { العرض: لا شيء! مهم؛ } بالنظر إلى مصفوفة arr[] من N عدد صحيح من العناصر، تكون المهمة هي العثور على مجموع متوسط جميع المجموعات الفرعية من هذه المصفوفة.
مثال:
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 مجموع المتوسط لجميع المجموعات الفرعية جربه!النهج الساذج: الحل الساذج هو التكرار من خلال جميع المجموعات الفرعية الممكنة للحصول على متوسط جميعها ثم قم بإضافتها واحدًا تلو الآخر ولكن هذا سيستغرق وقتًا هائلاً ولن يكون ممكنًا بالنسبة للمصفوفات الأكبر حجمًا.
يمكننا الحصول على نمط من خلال أخذ مثال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يمكن تفسير المعامل مع البسط على النحو التالي لنفترض أننا نكرر على مجموعات فرعية مع عناصر K، ثم سيكون المقام K وسيكون البسط r*S حيث يشير 'r' إلى عدد المرات التي سيتم فيها إضافة عنصر صفيف معين أثناء التكرار على مجموعات فرعية من نفس الحجم. من خلال الفحص يمكننا أن نرى أن r ستكون nCr(N - 1 n - 1) لأنه بعد وضع عنصر واحد في الجمع نحتاج إلى اختيار عناصر (n - 1) من عناصر (N - 1) بحيث يكون لكل عنصر تردد nCr(N - 1 n - 1) مع الأخذ في الاعتبار المجموعات الفرعية من نفس الحجم حيث أن جميع العناصر تشارك في الجمع بعدد متساو من المرات وهذا سيكون تكرار S أيضًا وسيكون البسط في التعبير النهائي.
في الكود أدناه يتم تنفيذ nCr باستخدام طريقة البرمجة الديناميكية يمكنك قراءة المزيد عن ذلك هنا
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. ?>
الإخراج63.75تعقيد الوقت: على 3 )
المساحة المساعدة: على 2 )النهج الفعال: تحسين المساحة O(1)
لتحسين التعقيد المكاني للنهج المذكور أعلاه، يمكننا استخدام نهج أكثر كفاءة يتجنب الحاجة إلى المصفوفة بأكملها ج[][] لتخزين المعاملات ذات الحدين. بدلًا من ذلك، يمكننا استخدام صيغة مركبة لحساب معامل ذات الحدين مباشرة عند الحاجة.خطوات التنفيذ:
- قم بالتكرار على عناصر المصفوفة وحساب مجموع كل العناصر.
- كرر على كل حجم مجموعة فرعية من 1 إلى 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 ))
الإخراج
63.75تعقيد الوقت: يا (ن ^ 2)
المساحة المساعدة: يا(1)إنشاء اختبار
