#practiceLinkDiv { 표시: 없음 !중요; }N개의 정수 요소로 구성된 배열 arr[]이 주어지면 이 배열의 모든 하위 집합의 평균 합계를 구하는 작업이 수행됩니다.
자바 입력 문자열
예:
Input : arr[] = [2 3 5]Recommended Practice 모든 하위 집합의 평균 합계 시도해 보세요!
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
순진한 접근 방식: 순진한 해결책은 가능한 모든 하위 집합을 반복하여 평균 그것들을 모두 추가한 다음 하나씩 추가하지만 이는 기하급수적인 시간이 걸리고 더 큰 배열에서는 실행 불가능합니다.
예를 들어 패턴을 얻을 수 있습니다
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++// 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.
산출
63.75
시간 복잡도: 에3)
보조 공간: 에2)
효율적인 접근 방식 : 공간 최적화 O(1)
위 접근 방식의 공간 복잡성을 최적화하기 위해 전체 행렬이 필요하지 않은 보다 효율적인 접근 방식을 사용할 수 있습니다. 기음[][] 이항 계수를 저장합니다. 대신 필요할 때 조합 공식을 사용하여 이항 계수를 직접 계산할 수 있습니다.
구현 단계:
- 배열의 요소를 반복하고 모든 요소의 합계를 계산합니다.
- 각 하위 집합 크기를 1에서 N까지 반복합니다.
- 루프 내부에서 다음을 계산합니다. 평균 부분 집합 크기에 대한 이항 계수를 곱한 요소의 합입니다. 계산된 평균을 결과에 추가합니다.
- 최종 결과를 반환합니다.
구현:
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))
산출
63.75 시간 복잡도: 오(n^2)
보조 공간: 오(1)