Рубрики

Биномиальный коэффициент | ДП-9

Ниже приводятся общие определения биномиальных коэффициентов .

  1. Биномиальный коэффициент C (n, k) можно определить как коэффициент X ^ k в разложении (1 + X) ^ n.
  2. Биномиальный коэффициент C (n, k) также дает число способов, независимо от порядка, в которых k объектов может быть выбран из n объектов; более формально, количество k-элементных подмножеств (или k-комбинаций) n-элементного набора.

Проблема
Напишите функцию, которая принимает два параметра n и k и возвращает значение биномиального коэффициента C (n, k). Например, ваша функция должна возвращать 6 для n = 4 и k = 2, и она должна возвращать 10 для n = 5 и k = 2.

1) Оптимальная субструктура
Значение C (n, k) может быть рекурсивно вычислено с использованием следующей стандартной формулы для биномиальных коэффициентов.

   C(n, k) = C(n-1, k-1) + C(n-1, k)
   C(n, 0) = C(n, n) = 1

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

C ++

// Наивная рекурсивная реализация C ++
#include <bits/stdc++.h>

using namespace std; 

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

int binomialCoeff(int n, int k) 

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

    if (k == 0 || k == n) 

        return 1; 

  

    // Recur

    return binomialCoeff(n - 1, k - 1) + 

                binomialCoeff(n - 1, k); 

  
/ * Код водителя * /

int main() 

    int n = 5, k = 2; 

    cout << "Value of C("<<n<<", "<<k<<") is " << binomialCoeff(n, k); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// Наивная рекурсивная реализация
#include<stdio.h>

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

int binomialCoeff(int n, int k)

{

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

  if (k==0 || k==n)

    return 1;

  

  // Recur

  return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int n = 5, k = 2;

    printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k));

    return 0;

}

Джава

// JAVA-код для динамического программирования |
// Установите 9 (биномиальный коэффициент)

import java.util.*;

  

class GFG {

      

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

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

    static int binomialCoeff(int n, int k) 

    {

      

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

        if (k == 0 || k == n)

            return 1;

          

        // Recur

        return binomialCoeff(n - 1, k - 1) + 

                    binomialCoeff(n - 1, k);

    }

      

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String[] args) 

   {

        int n = 5, k = 2;

        System.out.printf("Value of C(%d, %d) is %d ",

                        n, k, binomialCoeff(n, k));

    }

}

  
// Этот код предоставлен Арнавом Кр. Мандал.

питон

# Наивная рекурсивная реализация Python

  

def binomialCoeff(n , k):

  

    if k==0 or k ==n :

        return 1

  

    # Рекурсивный вызов

    return binomialCoeff(n-1 , k-1) + binomialCoeff(n-1 , k)

  
# Программа-драйвер для проверки вышеупомянутой функции

n = 5

k = 2

print "Value of C(%d,%d) is (%d)" %(n , k , binomialCoeff(n , k))

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # код для динамического программирования |
// Установите 9 (биномиальный коэффициент)

using System;

  

class GFG {

      

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

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

    static int binomialCoeff(int n, int k) 

    {

          

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

        if (k == 0 || k == n)

            return 1;

          

        // Recur

        return binomialCoeff(n - 1, k - 1) + 

                    binomialCoeff(n - 1, k);

    }

      

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void Main() 

    {

        int n = 5, k = 2;

        Console.Write("Value of C(" + n + "," 

                            + k + ") is " +

                        binomialCoeff(n, k));

    }

}

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

PHP

<?php
// PHP-код для динамического программирования |
// Установите 9 (биномиальный коэффициент)

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

function binomialCoeff($n, $k)

{

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

    if ($k==0 || $k==$n)

        return 1;

      

    // Recur

    return binomialCoeff($n - 1, $k - 1) + 

               binomialCoeff($n - 1, $k);

}

  

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

    $n = 5; 

    $k = 2;

    echo "Value of C","(",$n ,$k,") is "

               , binomialCoeff($n, $k);

  
// Этот код предоставлен aj_36
?>


Выход:

Value of C(52) is 10

2) Перекрывающиеся подзадачи
Следует отметить, что вышеуказанная функция снова и снова вычисляет одни и те же подзадачи. См. Следующее дерево рекурсии для n = 5 и k = 2. Функция C (3, 1) вызывается два раза. Для больших значений n будет много общих подзадач.

                             C(5, 2)
                    /                      \
           C(4, 1)                           C(4, 2)
            /   \                          /           \
       C(3, 0)   C(3, 1)             C(3, 1)               C(3, 2)
                /    \               /     \               /     \
         C(2, 0)    C(2, 1)      C(2, 0) C(2, 1)          C(2, 1)  C(2, 2)
                   /        \              /   \            /    \
               C(1, 0)  C(1, 1)      C(1, 0)  C(1, 1)   C(1, 0)  C(1, 1)

Поскольку те же самые подзадачи вызываются снова, эта проблема имеет свойство Перекрывающиеся подзадачи. Таким образом, проблема биномиального коэффициента имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и другие типичные проблемы динамического программирования (DP) , повторных вычислений с такими же подзадачами можно избежать, создавая временный массив C [] [] в порядке снизу вверх. Ниже приводится реализация на основе динамического программирования.

C ++

// Решение на основе динамического программирования, использующее
// таблица C [] [] для вычисления биномиального коэффициента
#include<bits/stdc++.h>

using namespace std;

  
// Прототип служебной функции, которая
// возвращает минимум двух целых

int min(int a, int b);

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

int binomialCoeff(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];

}

  
// Полезная функция для возврата
// минимум двух целых

int min(int a, int b)

{

    return (a < b) ? a : b;

}

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

int main()

{

    int n = 5, k = 2;

    cout << "Value of C[" << n << "][" 

         << k << "] is " << binomialCoeff(n, k);

}

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

С

// Решение на основе динамического программирования, использующее таблицу C [] [] для
// вычисляем биномиальный коэффициент
#include<stdio.h>

  
// Прототип служебной функции, которая возвращает минимум двух целых

int min(int a, int b);

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

int binomialCoeff(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];

}

  
// Вспомогательная функция, возвращающая минимум двух целых

int min(int a, int b)

{

    return (a<b)? a: b;

}

  
/ * Сушилка для проверки вышеуказанной функции * /

int main()

{

    int n = 5, k = 2;

    printf ("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k) );

    return 0;

}

Джава

// Решение на основе динамического программирования, использующее таблицу C [] [] для
// вычисляем биномиальный коэффициент

  

class BinomialCoefficient

{

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

    static int binomialCoeff(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 <= 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 int min(int a, int b)

    {

    return (a<b)? a: b; 

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String args[])

    {

    int n = 5, k = 2;

    System.out.println("Value of C("+n+","+k+") is "+binomialCoeff(n, k));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Программа Python на основе динамического программирования, использующая таблицу C [] []
# для расчета биномиального коэффициента

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

def binomialCoef(n, k):

    C = [[0 for x in range(k+1)] for x 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]

  
# Программа драйвера для проверки вышеуказанной функции

n = 5

k = 2

print("Value of C[" + str(n) + "][" + str(k) + "] is "

      + str(binomialCoef(n,k)))

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

C #

// Решение на основе динамического программирования, которое
// использует таблицу C [] [] для вычисления бинома
// Коэффициент

using System;

  

class GFG {

      

    // Возвращает значение биномиального коэффициента

    // C (n, k)

    static int binomialCoeff(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 int min(int a, int b)

    {

        return (a < b) ? a : b; 

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void Main()

    {

        int n = 5, k = 2;

        Console.WriteLine("Value of C(" + n

                        + "," + k + ") is "

                    + binomialCoeff(n, k));

    }

}

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

PHP

<?php
// Динамическое программирование на основе
// решение, использующее таблицу C [] [] для
// вычисляем биномиальный коэффициент

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

function binomialCoeff( $n, $k)

{

    $C = array(array());

    $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];

}

  

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

    $n = 5; 

    $k = 2;

    echo "Value of C(" ,$n," ",$k, ") is"," "

                 , binomialCoeff($n, $k) ;

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


Выход:

Value of C[5][2] is 10

Сложность времени: O (n * k)
Вспомогательное пространство: O (n * k)

Ниже приведена оптимизированная для космоса версия приведенного выше кода. В следующем коде используется только O (k). Спасибо АК за предложение этого метода.

C / C ++

// C ++ программа для динамического программирования с оптимизированным пространством
// Решение биномиального коэффициента
#include<bits/stdc++.h>

using namespace std;

  

int binomialCoeff(int n, int k)

{

    int C[k+1];

    memset(C, 0, sizeof(C));

  

    C[0] = 1;  // nC0 равно 1

  

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

    {

        // Вычисляем следующий ряд паскальского треугольника, используя

        // предыдущая строка

        for (int j = min(i, k); j > 0; j--)

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

    }

    return C[k];

}

  
/ * Сушилка для проверки вышеуказанной функции * /

int main()

{

    int n = 5, k = 2;

    printf ("Value of C(%d, %d) is %d ",

            n, k, binomialCoeff(n, k) );

    return 0;

}

Джава

// JAVA-код для динамического программирования |
// Установите 9 (биномиальный коэффициент)

import java.util.*;

  

class GFG {

      

    static int binomialCoeff(int n, int k)

    {

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

         

        // nC0 равно 1

        C[0] = 1;  

       

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

        {

            // Вычисляем следующий ряд паскаля

            // треугольник с использованием предыдущей строки

            for (int j = Math.min(i, k); j > 0; j--)

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

        }

        return C[k];

    }

      

    / * Драйвер программы * /

    public static void main(String[] args) 

    {

         int n = 5, k = 2;

            System.out.printf("Value of C(%d, %d) is %d "

                                , n, k, binomialCoeff(n, k));

    }

}

питон

# Программа Python для решения для Оптимизированного Динамического Программирования
Коэффициент Binomail. Этот использует концепцию паскаль
# Треугольник и меньше памяти

  

def binomialCoeff(n , k):

  

    # Объявление пустого массива

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

    C[0] = 1 # с nC0 равен 1

  

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

  

        # Вычислить следующий ряд паскаль треугольника, используя

        # предыдущая строка

        j = min(i ,k)

        while (j>0):

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

            j -= 1

  

    return C[k]

  
Программа # Driver для проверки вышеуказанной функции

n = 5

k = 2

print "Value of C(%d,%d) is %d" %(n,k,binomialCoeff(n,k))

  
# Этот код предоставлен Нихилом Кумаром Сингхом (nickzuck_007)

C #

// C # код для динамического программирования |
// Установите 9 (биномиальный коэффициент)

using System;

  

class GFG {

      

    static int binomialCoeff(int n, int k)

    {

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

          

        // nC0 равно 1

        C[0] = 1; 

      

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

        {

            // Вычисляем следующий ряд паскаля

            // треугольник используя предыдущий

            // строка

            for (int j = Math.Min(i, k);

                              j > 0; j--)

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

        }

        return C[k];

    }

      

    / * Драйвер программы * /

    public static void Main() 

    {

        int n = 5, k = 2;

        Console.WriteLine("Value of C(" 

                + n + " " + k + ") is " 

                + binomialCoeff(n, k));

    }

}

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

PHP

<?php
// PHP-программа для оптимизации пространства
// Динамическое программирование решения
// Биномиальный коэффициент

function binomialCoeff($n, $k)

{

    $C = array_fill(0, $k + 1, 0);

  

    $C[0] = 1; // nC0 равно 1

  

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

    {

        // Вычисляем следующий ряд паскаля

        // треугольник с использованием предыдущей строки

        for ($j = min($i, $k); $j > 0; $j--)

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

    }

    return $C[$k];

}

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

$n = 5; $k = 2;

echo "Value of C[$n, $k] is "

        binomialCoeff($n, $k);

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


Выход:

Value of C[5][2] is 10

Сложность времени: O (n * k)
Вспомогательное пространство: O (k)

Объяснение:
1 ========== >> n = 0, C (0,0) = 1
1–1 ======== >> n = 1, C (1,0) = 1, C (1,1) = 1
1–2–1 ====== >> n = 2, C (2,0) = 1, C (2,1) = 2, C (2,2) = 1
1–3–3–1 ==== >> n = 3, C (3,0) = 1, C (3,1) = 3, C (3,2) = 3, C (3,3) = 1
1–4–6–4–1 == >> n = 4, C (4,0) = 1, C (4,1) = 4, C (4,2) = 6, C (4,3) = 4, С (4,4) = 1
Итак, здесь каждый цикл на i строит i-й ряд паскальского треугольника, используя (i-1) -й ряд

В любой момент каждый элемент массива C будет иметь некоторое значение (НОЛЬ или более), и на следующей итерации значение для этих элементов будет получено из предыдущей итерации.
В заявлении
C [j] = C [j] + C [j-1]
Правая часть представляет значение, полученное в предыдущей итерации (строка треугольника Паскаля зависит от предыдущей строки). Левая часть представляет значение текущей итерации, которая будет получена этим оператором.

Let's say we want to calculate C(4, 3), 
i.e. n=4, k=3:

All elements of array C of size 4 (k+1) are
initialized to ZERO.

i.e. C[0] = C[1] = C[2] = C[3] = C[4] = 0;
Then C[0] is set to 1

For i = 1:
C[1] = C[1] + C[0] = 0 + 1 = 1 ==>> C(1,1) = 1

For i = 2:
C[2] = C[2] + C[1] = 0 + 1 = 1 ==>> C(2,2) = 1
C[1] = C[1] + C[0] = 1 + 1 = 2 ==>> C(2,2) = 2

For i=3:
C[3] = C[3] + C[2] = 0 + 1 = 1 ==>> C(3,3) = 1
C[2] = C[2] + C[1] = 1 + 2 = 3 ==>> C(3,2) = 3
C[1] = C[1] + C[0] = 2 + 1 = 3 ==>> C(3,1) = 3

For i=4:
C[4] = C[4] + C[3] = 0 + 1 = 1 ==>> C(4,4) = 1
C[3] = C[3] + C[2] = 1 + 3 = 4 ==>> C(4,3) = 4
C[2] = C[2] + C[1] = 3 + 3 = 6 ==>> C(4,2) = 6
C[1] = C[1] + C[0] = 3 + 1 = 4 ==>> C(4,1) = 4

C(4,3) = 4 is would be the answer in our example.

Смотрите это для Пространственно-временного биномиального коэффициента

Ссылки:
http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2015%20-%20Dynamic%20Programming%20Binomial%20Coefficients.htm

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

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

Биномиальный коэффициент | ДП-9

0.00 (0%) 0 votes