#practiceLinkDiv { display: none !important; }Având în vedere un tablou arr[] de N elemente întregi, sarcina este de a găsi suma mediei tuturor submulților din această matrice.
an în trimestre
Exemplu:
Input : arr[] = [2 3 5]Recommended Practice Suma mediei tuturor subgrupurilor Încearcă!
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
Abordare naivă: O soluție naivă este să iterați prin toate subseturile posibile obțineți un medie dintre toate și apoi adăugați-le unul câte unul, dar acest lucru va dura un timp exponențial și va fi imposibil pentru matrice mai mari.
Putem obține un model luând un exemplu
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
Coeficientul cu numărători poate fi explicat după cum urmează să presupunem că iterăm peste submulțimi cu K elemente, atunci numitorul va fi K și numărătorul va fi r*S unde „r” denotă de câte ori va fi adăugat un anumit element de matrice în timp ce iterăm peste subseturi de aceeași dimensiune. Prin inspecție, putem vedea că r va fi nCr(N - 1 n - 1) deoarece după plasarea unui element în însumare trebuie să alegem (n – 1) elemente din (N - 1) elemente, astfel încât fiecare element va avea o frecvență de nCr(N - 1 n - 1) în timp ce luăm în considerare submulțimi de aceeași dimensiune deoarece toate elementele iau parte la însumare, de asemenea, frecvența numărătorului va fi egală cu numărul de timpi S în final.
În codul de mai jos nCr este implementat folosind metoda de programare dinamică puteți citi mai multe despre asta aici
C++// C++ program to get sum of average of all subsets #include
// 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# 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
<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 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 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.
Ieșire
63.75
Complexitatea timpului: Pe3)
Spațiu auxiliar: Pe2)
Abordare eficientă: optimizarea spațiului O(1)
Pentru a optimiza complexitatea spațială a abordării de mai sus putem folosi o abordare mai eficientă care evită necesitatea întregii matrice C[][] pentru a stoca coeficienți binomi. În schimb, putem folosi o formulă de combinație pentru a calcula coeficientul binom direct atunci când este necesar.
Etape de implementare:
- Iterați peste elementele matricei și calculați suma tuturor elementelor.
- Repetați pe fiecare dimensiune a subsetului de la 1 la N.
- În interiorul buclei calculați medie a sumei elementelor înmulțită cu coeficientul binom pentru mărimea submulțimii. Adăugați media calculată la rezultat.
- Întoarceți rezultatul final.
Implementare:
C++#include
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)); } }
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)); } }
// 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));
# 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))
Ieșire
63.75 Complexitatea timpului: O(n^2)
Spațiu auxiliar: O(1)