#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
素朴なアプローチ: 単純な解決策は、考えられるすべてのサブセットを反復処理して、 平均 すべてを取り出してから 1 つずつ追加しますが、これには指数関数的な時間がかかり、より大きな配列では実行できません。
例を取ることでパターンを取得できます
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) になることがわかります。これは、合計に 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)
上記のアプローチの空間の複雑さを最適化するには、行列全体の必要性を回避する、より効率的なアプローチを使用できます。 C[][] 二項係数を保存します。代わりに、必要に応じて組み合わせ式を使用して二項係数を直接計算できます。
実装手順:
- 配列の要素を反復処理し、すべての要素の合計を計算します。
- 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 時間計算量: O(n^2)
補助スペース: ○(1)