#practiceLinkDiv { display: none !important; }Atsižvelgiant į N sveikųjų skaičių elementų masyvo arr[], užduotis yra rasti visų šio masyvo poaibiulių vidurkio sumą.
kas yra $home linux
Pavyzdys:
Input : arr[] = [2 3 5]Recommended Practice Visų pogrupių vidurkio suma Išbandykite!
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
Naivus požiūris: Naivus sprendimas yra kartoti visus galimus poaibius ir gauti an vidutinis visų ir pridėkite juos po vieną, tačiau tai užtruks eksponentiškai ir bus neįmanoma didesniems masyvams.
Mes galime gauti modelį imdami pavyzdį
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
Koeficientas su skaitikliais gali būti paaiškintas taip, tarkime, kad kartojame poaibius su K elementų, tada vardiklis bus K, o skaitiklis bus r*S, kur „r“ reiškia, kiek kartų konkretus masyvo elementas bus pridėtas, kai kartojama per tokio paties dydžio poaibius. Patikrinus matome, kad r bus nCr(N - 1 n - 1), nes sudėjus vieną elementą reikia pasirinkti (n - 1) elementus iš (N - 1) elementų, kad kiekvieno elemento dažnis būtų nCr(N - 1 n - 1), o atsižvelgiant į tokio pat dydžio poaibius, nes visi elementai dalyvauja, o sumuojant bus lygus kartų skaičius, o galutinis dažnis S bus lygus. išraiška.
Žemiau esančiame kode nCr realizuojamas naudojant dinaminio programavimo metodą daugiau apie tai galite paskaityti čia
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.
Išvestis
63.75
Laiko sudėtingumas: O (n3)
Pagalbinė erdvė: O (n2)
Efektyvus požiūris: erdvės optimizavimas O(1)
Norėdami optimizuoti pirmiau pateikto metodo erdvės sudėtingumą, galime naudoti efektyvesnį metodą, kuris nereikalauja visos matricos C[][] binominiams koeficientams saugoti. Vietoj to galime naudoti kombinuotą formulę, kad prireikus tiesiogiai apskaičiuotų binominį koeficientą.
Diegimo žingsniai:
- Pakartokite masyvo elementus ir apskaičiuokite visų elementų sumą.
- Pakartokite kiekvieną pogrupio dydį nuo 1 iki N.
- Apskaičiuokite kilpos viduje vidutinis elementų sumos, padaugintos iš poaibio dydžio dvinario koeficiento. Prie rezultato pridėkite apskaičiuotą vidurkį.
- Grąžinkite galutinį rezultatą.
Įgyvendinimas:
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))
Išvestis
63.75 Laiko sudėtingumas: O(n^2)
Pagalbinė erdvė: O(1)