Биномиальный коэффициент


Сложный уровень средний
Часто спрашивают в Directi Expedia Хакер Rank Xome
Динамическое программирование LeetCode Экзамен Математики

Постановка задачи

Найдите биномиальный коэффициент для заданного значения n и k.

математика,  биномиальные коэффициенты являются положительными целые которые происходят как коэффициенты в биноминальная теорема, Обычно биномиальный коэффициент индексируется парой целых чисел n ≥ k ≥ 0 и записывается как »- цитата из Wikipedia.

Пример

n = 5, k = 2
10

Пояснение: Используя формулу для расчета биномиального коэффициента, находим 5 C 3 что равно 10.

Что такое биномиальный коэффициент?

Прежде чем узнать, как найти биномиальный коэффициент. Обсудим кратко что такое биномиальный коэффициент? и зачем это вообще нужно?

Потому что биномиальный коэффициент широко используется для решения задач комбинаторики. Допустим, у вас есть разные элементы, и вам нужно выбрать элементы. Итак, если вы хотите решить эту проблему, вы можете легко написать все случаи выбора k элементов из n элементов. Но при увеличении n это очень трудоемкий процесс. Эту проблему легко решить, используя биномиальный коэффициент. Более того, эта проблема выбора k элементов из n различных элементов является одним из способов определения биномиального коэффициента n C k. Биномиальный коэффициент легко вычисляется по приведенной формуле:

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

Наивный подход к нахождению биномиального коэффициента

Этот подход не слишком наивно вообще. Представьте, что вас просят найти количество способов выбрать 3 элемента из 5. Так ты легко сможешь найти п !, к! и (нк)! и поместите значения в данную формулу. Это решение занимает всего Вовремя и O (1) пробел. Но иногда ваши факториальные значения могут переполняться, поэтому нам нужно об этом позаботиться. Этот подход хорош, если мы хотим вычислить единственный биномиальный коэффициент. Но много раз нам нужно вычислить много биномиальных коэффициентов. Так что лучше их предварительно вычислить. Мы узнаем, как эффективно находить биномиальные коэффициенты.

Оптимизированный подход к нахождению биномиального коэффициента

Что ж, наивный подход не был бы наивным, если бы мы хотели найти единственный биномиальный коэффициент. Но когда нам нужно найти много биномиальных коэффициентов. Таким образом, задачу становится трудно решить в срок. Потому что наивный подход все же требует времени. Итак, здесь у нас есть несколько запросов, по которым нас просят вычислить nCk для заданных n и k. Может быть много вопросов. Чтобы решить эту проблему, мы должны быть знакомы с треугольником Паскаля. Потому что это заставит нас очень ясно понять, почему мы собираемся делать то, что собираемся делать.

Биномиальный коэффициент

Любая ячейка в треугольнике Паскаля обозначает биномиальные коэффициенты. Нам нужно знать кое-что о треугольнике Паскаля.

  1. Начинается с строки 0.
  2. Любое число в треугольнике Паскаля обозначает биномиальный коэффициент.
  3. Любой биномиальный коэффициент, который не находится на границах строки, получается путем суммирования элементов, которые находятся чуть выше него в левом и правом направлениях.

{\ binom {n} {k}} = {\ binom {n-1} {k-1}} + {\ binom {n-1} {k}} \ quad {\ text {для всех целых чисел}} n , к: 1 \ leq k \ leq n-1,

Теперь мы знаем, что каждый биномиальный коэффициент зависит от двух биномиальных коэффициентов. Итак, если мы сможем каким-то образом решить их, то мы можем легко взять их сумму, чтобы найти наш требуемый биномиальный коэффициент. Это дает нам интуитивное представление об использовании Динамическое программирование. Здесь также очень легко указать базовые случаи. dp [0] [0] = 1, dp [i] [0] = dp [i] [[i] = 1.

Код:

Код C ++ для поиска биномиального коэффициента

#include<bits/stdc++.h>
using namespace std;

int C[51][51];

// this function just makes our pascal triangle
void precomputeBinomialCoefficients()
{

  for (int i = 0; i <= 50; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      // Base Cases
      if (j == 0 || j == i)
        C[i][j] = 1;
      else
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; // use recursive formula
    }
  }
}

int main()
{
  // precomputationis being done for n = 50, you can change the value of n
  precomputeBinomialCoefficients();
  int noOfQueries;cin>>noOfQueries;
  while(noOfQueries--){
    // here n & k do not satisfy the propertoes of binomial coefficient
    // then we will answer it as 0
    int n,k;cin>>n>>k;
    if(n<=50 && k<=50)
      cout<<C[n][k]<<endl;
    else
      cout<<0<<endl;
  }
}
3
5 3
5 2
6 4
10
10
15

Код Java для поиска биномиального коэффициента

import java.util.*;

class Main{
  static int C[][];

  // this function just makes our pascal triangle
  static void precomputeBinomialCoefficients() 
  {
    for (int i = 0; i <= 50; i++) 
    { 
      for (int j = 0; j <= i; j++) 
      { 
        // Base Cases 
        if (j == 0 || j == i) 
          C[i][j] = 1; 
        else
          C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; // use recursive formula
      } 
    }	
  } 

  public static void main(String[] args)
  {
    C = new int[51][51];
    // precomputationis being done for n = 50, you can change the value of n
    precomputeBinomialCoefficients();
    Scanner sc = new Scanner(System.in);
    int noOfQueries;
    noOfQueries = sc.nextInt();
    while(noOfQueries-- > 0){
      // here n & k do not satisfy the propertoes of binomial coefficient
      // then we will answer it as 0
      int n = sc.nextInt();
      int k = sc.nextInt();
      if(n<=50 && k<=50)
        System.out.println(C[n][k]);		
      else
        System.out.println(0);
    }
  }
}
3
5 2
5 3
6 3
10
10
15

Анализ сложности

Сложность времени 

О (N ^ 2 + Q),  потому что мы предварительно вычисляем биномиальные коэффициенты до nCn. Эта операция занимает время O (N ^ 2), а затем время O (1), чтобы ответить на каждый запрос.

Космическая сложность

О (N ^ 2),  для хранения предварительно вычисленных результатов биномиальных коэффициентов.