Рубрики

Сумма среднего всех подмножеств

Учитывая массив массива из 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

Наивное решение состоит в том, чтобы перебрать все возможные подмножества, получить среднее значение для всех из них, а затем добавить их один за другим, но это займет экспоненциальное время и будет невозможно для больших массивов.

Мы можем получить образец, взяв пример,

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 ++ программа для получения суммы средних по всем подмножествам
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает значение биномиального коэффициента C (n, k)

int nCr(int n, int k)

{

    int C[n + 1][k + 1];

    int i, j;

  

    // Рассчитать значение биномиального коэффициента снизу

    // вверх

    for (i = 0; i <= n; i++) {

        for (j = 0; j <= min(i, k); j++) {

            // Базовые случаи

            if (j == 0 || j == i)

                C[i][j] = 1;

  

            // Рассчитать значение, используя ранее сохраненные

            // ценности

            else

                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];

        }

    }

    return C[n][k];

}

  
// метод возвращает сумму среднего из всех подмножеств

double resultOfAllSubsets(int arr[], int N)

{

    double result = 0.0; // Инициализировать результат

  

    // Находим сумму элементов

    int sum = 0;

    for (int i = 0; i < N; i++)

        sum += arr[i];

  

    // цикл один раз для всех подмножеств одного размера

    for (int n = 1; n <= N; n++)

  

        / * каждый элемент встречается nCr (N-1, n-1) раз, в то время как

           учитывая подмножество размера n * /

        result += (double)(sum * (nCr(N - 1, n - 1))) / n;

  

    return result;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    int arr[] = { 2, 3, 5, 7 };

    int N = sizeof(arr) / sizeof(int);

    cout << resultOfAllSubsets(arr, N) << endl;

    return 0;

}

Джава

// Java-программа для получения суммы
// среднее из всех подмножеств

import java.io.*;

  

class GFG {

  

    // Возвращает значение бинома

    // Коэффициент C (n, k)

    static int nCr(int n, int k)

    {

        int C[][] = new int[n + 1][k + 1];

        int i, j;

  

        // Рассчитать значение биномиального

        // Коэффициент снизу вверх

        for (i = 0; i <= n; i++) {

            for (j = 0; j <= Math.min(i, k); j++) {

                // Базовые случаи

                if (j == 0 || j == i)

                    C[i][j] = 1;

  

                // Рассчитать значение, используя

                // ранее сохраненные значения

                else

                    C[i][j] = C[i - 1][j - 1] + C[i - 1][j];

            }

        }

        return C[n][k];

    }

  

    // метод возвращает сумму среднего из всех подмножеств

    static double resultOfAllSubsets(int arr[], int N)

    {

        // Инициализировать результат

        double result = 0.0;

  

        // Находим сумму элементов

        int sum = 0;

        for (int i = 0; i < N; i++)

            sum += arr[i];

  

        // цикл один раз для всех подмножеств одного размера

        for (int n = 1; n <= N; n++)

  

            / * каждый элемент встречается nCr (N-1, n-1) раз, в то время как

            учитывая подмножество размера n * /

            result += (double)(sum * (nCr(N - 1, n - 1))) / n;

  

        return result;

    }

  

    // Код драйвера для тестирования вышеуказанных методов

    public static void main(String[] args)

    {

        int arr[] = { 2, 3, 5, 7 };

        int N = arr.length;

        System.out.println(resultOfAllSubsets(arr, N));

    }

}

  
// Этот код предоставлен vt_m

python3

# Python3 программа для получения суммы
# среднее значение всех подмножеств

  
# Возвращает значение биномиального
Коэффициент C (n, k)

def nCr(n, k):

  

    C = [[0 for i in range(k + 1)]

            for j in range(n + 1)]

  

    # Рассчитать значение биномиального

    # Коэффициент снизу вверх

    for i in range(n + 1):

      

        for j in range(min(i, k) + 1):

          

            # Базовые случаи

            if (j == 0 or j == i):

                C[i][j] = 1

  

            # Рассчитать стоимость, используя

            # ранее сохраненные значения

            else:

                C[i][j] = C[i-1][j-1] + C[i-1][j]

      

    return C[n][k]

  
# Метод возвращает сумму
# среднее из всех подмножеств

def resultOfAllSubsets(arr, N):

  

    result = 0.0 # Инициализировать результат

  

    # Найти сумму элементов

    sum = 0

    for i in range(N):

        sum += arr[i]

  

    # цикл один раз для всех подмножеств одного размера

    for n in range(1, N + 1):

  

        # каждый элемент встречается nCr (N-1, n-1) раз, пока

        # учитывая подмножество размера n * /

        result += (sum * (nCr(N - 1, n - 1))) / n

  

    return result

  
# Код драйвера

arr = [2, 3, 5, 7]

N = len(arr)

print(resultOfAllSubsets(arr, N))

  

  
# Этот код предоставлен Anant Agarwal.

C #

// C # программа для получения суммы
// среднее из всех подмножеств

using System;

  

class GFG {

      

    // Возвращает значение бинома

    // Коэффициент C (n, k)

    static int nCr(int n, int k)

    {

        int[, ] C = new int[n + 1, k + 1];

        int i, j;

  

        // Рассчитать значение биномиального

        // Коэффициент снизу вверх

        for (i = 0; i <= n; i++) {

            for (j = 0; j <= Math.Min(i, k); j++) 

            {

                // Базовые случаи

                if (j == 0 || j == i)

                    C[i, j] = 1;

  

                // Рассчитать значение, используя

                // ранее сохраненные значения

                else

                    C[i, j] = C[i - 1, j - 1] + C[i - 1, j];

            }

        }

        return C[n, k];

    }

  

    // метод возвращает сумму среднего

    // всех подмножеств

    static double resultOfAllSubsets(int[] arr, int N)

    {

        // Инициализировать результат

        double result = 0.0;

  

        // Находим сумму элементов

        int sum = 0;

        for (int i = 0; i < N; i++)

            sum += arr[i];

  

        // цикл один раз для всего подмножества

        // одного размера

        for (int n = 1; n <= N; n++)

  

            / * каждый элемент встречается nCr (N-1, n-1) раз, в то время как

               учитывая подмножество размера n * /

            result += (double)(sum * (nCr(N - 1, n - 1))) / n;

  

        return result;

    }

  

    // Код драйвера для тестирования вышеуказанных методов

    public static void Main()

    {

        int[] arr = { 2, 3, 5, 7 };

        int N = arr.Length;

        Console.WriteLine(resultOfAllSubsets(arr, N));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для получения суммы
// среднего значения всех подмножеств

  
// Возвращает значение бинома
// Коэффициент C (n, k)

function nCr($n, $k)

{

    $C[$n + 1][$k + 1] = 0;

    $i; $j;

  

    // Рассчитать значение биномиального

    // Коэффициент снизу вверх

    for ($i = 0; $i <= $n; $i++) 

    {

        for ($j = 0; $j <= min($i, $k); $j++)

        {

            // Базовые случаи

            if ($j == 0 || $j == $i)

                $C[$i][$j] = 1;

  

            // Рассчитать значение, используя

            // ранее сохраненные значения

            else

                $C[$i][$j] = $C[$i - 1][$j - 1] + 

                             $C[$i - 1][$j];

        }

    }

    return $C[$n][$k];

}

  
// метод возвращает сумму
// среднее из всех подмножеств

function resultOfAllSubsets($arr, $N)

{

    // Инициализировать результат

    $result = 0.0; 

  

    // Находим сумму элементов

    $sum = 0;

    for ($i = 0; $i < $N; $i++)

        $sum += $arr[$i];

  

    // цикл один раз для всех

    // подмножество одинакового размера

    for ($n = 1; $n <= $N; $n++)

  

        / * каждый элемент встречается nCr (N-1,

        п-1) раз при рассмотрении

        подмножество размера n * /

        $result += (($sum * (nCr($N - 1, 

                                 $n - 1))) / $n);

  

    return $result;

}

  
// Код драйвера

$arr = array( 2, 3, 5, 7 );

$N = sizeof($arr) / sizeof($arr[0]);

echo resultOfAllSubsets($arr, $N) ;

  
// Этот код предоставлен нитин митталь.
?>


Выход :

63.75

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Сумма среднего всех подмножеств

0.00 (0%) 0 votes