Рубрики

Вероятность такова, что два подмножества содержат одинаковое количество элементов

Дан набор, содержащий N элементов. Если выбрано два подмножества X и Y, найдите вероятность того, что оба они содержат одинаковое количество элементов.

Примеры:

Input: 4
Output: 35/128
Input: 2
Output: 3/8

Подходить:
Давайте выберем подмножество X с r количеством элементов, тогда Y должно содержать r количество элементов. Подмножество может иметь минимум 0 элементов и максимум N элементов.

Общее количество подмножеств набора содержит N элементов. Всего возможный способ выбрать X и Y одновременно будет знак равно знак равно ,

Пусть, P = Общий возможный способ выбрать X и Y так , чтобы оба имели одинаковое количество элементов.

Тогда P = знак равно знак равно

Таким образом, требуемая вероятность будет ,

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация
// вышеуказанный подход
#include <bits/stdc++.h>

using namespace std;

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

int binomialCoeff(int n, int k)

{

    int res = 1;

  

    // Поскольку C (n, k) = C (n, nk)

    if (k > n - k)

        k = n - k;

  

    // Рассчитать значение

    for (int i = 0; i < k; ++i) {

        res *= (n - i);

        res /= (i + 1);

    }

  

    return res;

}

  
// Итеративная функция для
// вычислить (x ^ y) в O (log y)

int power(int x, unsigned int y)

{

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

    int res = 1;

  

    while (y > 0) {

  

        // Если у нечетное, умножаем

        // х с результатом

        if (y & 1)

            res = res * x;

  

        // у должен быть даже сейчас

        // y = y / 2

        y = y >> 1;

  

        // Меняем x на x ^ 2

        x = x * x;

    }

    return res;

}

  
// Функция поиска вероятности

void FindProbability(int n)

{

  

    // Подсчитать общее возможное

    // способы и выгодные пути.

    int up = binomialCoeff(2 * n, n);

    int down = power(2, 2 * n);

  

    // Делим на gcd так, чтобы

    // они становятся относительно простыми

    int g = __gcd(up, down);

  

    up /= g, down /= g;

  

    cout << up << "/" << down << endl;

}

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

int main()

{

  

    int N = 8;

  

    FindProbability(N);

  

    return 0;

}

Джава

// Java реализация
// вышеуказанный подход

class GFG

{

      

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

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

    static int binomialCoeff(int n, int k) 

    

        int res = 1

      

        // Поскольку C (n, k) = C (n, nk)

        if (k > n - k) 

            k = n - k; 

      

        // Рассчитать значение

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

        

            res *= (n - i); 

            res /= (i + 1); 

        

      

        return res; 

    

      

    // Итеративная функция для

    // вычислить (x ^ y) в O (log y)

    static int power(int x, int y) 

    

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

        int res = 1

      

        while (y > 0

        

      

            // Если у нечетное, умножаем

            // х с результатом

            if ((y & 1) == 1

                res = res * x; 

      

            // у должен быть даже сейчас

            // y = y / 2

            y = y >> 1

      

            // Меняем x на x ^ 2

            x = x * x; 

        

        return res; 

    

      

    // Рекурсивная функция для возврата gcd из a и b

    static int gcd(int a, int b) 

    

        if (b == 0

            return a; 

        return gcd(b, a % b); 

          

    

      

    // Функция поиска вероятности

    static void FindProbability(int n) 

    

      

        // Подсчитать общее возможное

        // способы и выгодные пути.

        int up = binomialCoeff(2 * n, n); 

        int down = power(2, 2 * n); 

      

        // Делим на gcd так, чтобы

        // они становятся относительно простыми

        int g = gcd(up, down); 

      

        up /= g;

        down /= g; 

      

        System.out.println(up + "/" + down); 

    

      

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

    public static void main (String[] args)

    

        int N = 8

      

        FindProbability(N); 

    

}

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

python3

# Python3 реализация
# вышеуказанный подход

import math

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

def binomialCoeff(n, k):

  

    res = 1

  

    # Так как C (n, k) = C (n, nk)

    if (k > n - k): 

        k = n -

  

    # Рассчитать стоимость

    for i in range(0, k): 

        res = res * (n - i) 

        res = res // (i + 1)

  

    return res

  
# Итеративная функция для
# вычислить (x ^ y) в O (log y)

def power(x, y):

      

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

    res = 1

  

    while (y > 0):

  

        # Если у нечетно, умножить

        # х с результатом

        if (y & 1):

            res = res * x

  

        # у должно быть даже сейчас

        # y = y / 2

        y = y // 2

  

        # Измените x на x ^ 2

        x = x * x

      

    return res 

  
# Функция поиска вероятности

def FindProbability(n):

  

    # Подсчитать общее возможное

    # способы и выгодные способы.

    up = binomialCoeff(2 * n, n)

    down = power(2, 2 * n)

  

    # Разделите на gcd так, чтобы

    # они становятся относительно простыми

    g = math.gcd(up,down)

  

    up = up // g

    down = down // g

  

    print(up, "/", down)

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

N = 8

FindProbability(N)

  
# Этот код предоставлен Sanjit_Prasad

C #

// C # реализация
// вышеуказанный подход

using System;

using System.Collections.Generic;

      

class GFG

{

      

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

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

    static int binomialCoeff(int n, int k) 

    

        int res = 1; 

      

        // Поскольку C (n, k) = C (n, nk)

        if (k > n - k) 

            k = n - k; 

      

        // Рассчитать значение

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

        

            res *= (n - i); 

            res /= (i + 1); 

        

      

        return res; 

    

      

    // Итеративная функция для

    // вычислить (x ^ y) в O (log y)

    static int power(int x, int y) 

    

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

        int res = 1; 

      

        while (y > 0) 

        

      

            // Если у нечетное, умножаем

            // х с результатом

            if ((y & 1) == 1) 

                res = res * x; 

      

            // у должен быть даже сейчас

            // y = y / 2

            y = y >> 1; 

      

            // Меняем x на x ^ 2

            x = x * x; 

        

        return res; 

    

      

    // Рекурсивная функция для

    // вернуть gcd из a и b

    static int gcd(int a, int b) 

    

        if (b == 0) 

            return a; 

        return gcd(b, a % b); 

    

      

    // Функция поиска вероятности

    static void FindProbability(int n) 

    

      

        // Подсчитать общее возможное

        // способы и выгодные пути.

        int up = binomialCoeff(2 * n, n); 

        int down = power(2, 2 * n); 

      

        // Делим на gcd так, чтобы

        // они становятся относительно простыми

        int g = gcd(up, down); 

      

        up /= g;

        down /= g; 

      

        Console.WriteLine(up + "/" + down); 

    

      

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

    public static void Main (String[] args)

    

        int N = 8; 

      

        FindProbability(N); 

    

}

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

Выход:

6435/32768

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

Вероятность такова, что два подмножества содержат одинаковое количество элементов

0.00 (0%) 0 votes