Биномни коефицијент


Ниво тешкоће Средњи
Често питани у Дирецти Екпедиа ХацкерРанк Ксоме
Динамичко програмирање ЛеетЦоде Математика

Изјава о проблему

Наћи биномни коефицијент за дату вредност н и к.

математикабиномни коефицијенти су позитивне интегерс који се јављају као коефицијенти у биномна теорема. Обично се биномни коефицијент индексира паром целих бројева n ≥ k ≥ КСНУМКС а записано је као ”- цитирано од Википедиа.

Пример

n = 5, k = 2
10

Објашњење: Користимо формулу за израчунавање биномног коефицијента 5 Ц 3 што је једнако 10.

Шта је биномни коефицијент?

Пре него што смо знали како пронаћи биномни коефицијент. Хајде да разговарамо укратко шта је биномни коефицијент? и зашто је то уопште потребно?

Будући да се биномни коефицијент у великој мери користи за решавање проблема комбинаторике. Рецимо да их имате различите елементе и треба да одаберете елементи. Дакле, ако желите да решите овај проблем, лако можете да напишете све случајеве избора к елемената од н елемената. Али ово је дуготрајан процес када се н повећава. Овај проблем се лако може решити помоћу биномног коефицијента. Штавише, овај проблем избора к елемената из н различитих елемената један је од начина за дефинисање биномног коефицијента н Ц к. Биномни коефицијент може се лако израчунати помоћу дате формуле:

Пошто смо сада добро у основама, требали бисмо пронаћи начине да то ефикасно израчунамо.

Наивни приступ за проналажење биномног коефицијента

Овај приступ није уопште превише наиван. Узмите у обзир да се од вас тражи да пронађете број начина избора 3 елемента од 5 елемената. Тако да можете лако пронаћи н !, к! и (нк)! и вредности ставите у дату формулу. Ово решење траје само На време О (1) простор. Али понекад ваше факторске вредности могу да преплаве па морамо да се побринемо за то. Овај приступ је у реду ако желимо израчунати један биномни коефицијент. Али много пута морамо израчунати много биномних коефицијената. Дакле, боље је да се они прерачунају. Сазнаћемо како ефикасно пронаћи биномне коефицијенте.

Оптимизирани приступ за проналажење биномног коефицијента

Па, наивни приступ није био наиван ако смо желели да пронађемо један биномни коефицијент. Али када треба да пронађемо много бинмоијалних коефицијената. Дакле, проблем постаје тешко завршити у року. Јер је наиван приступ и даље дуготрајан. Дакле, овде имамо неколико упита у којима се од нас тражи да израчунамо нЦк за дате н и к. Упита може бити много. Да бисмо то решили, требали бисмо бити упознати са Пасцаловим троуглом. Узрок због којег ћемо много јасније схватити зашто ћемо радити оно што ћемо.

Биномни коефицијент

Било која ћелија у паскалном троуглу означава биномне коефицијенте. Морамо знати неке ствари у вези са Паскаловим троуглом.

  1. Почиње са редом 0.
  2. Било који број у Пасцаловом троуглу означава биномни коефицијент.
  3. Било који биномни коефицијент који није на границама реда прави се из збира елемената који се налазе непосредно изнад њега у левом и десном смеру.

{\ бином {н} {к}} = {\ бином {н-1} {к-1}} + {\ бином {н-1} {к}} \ куад {\ тект {за све целобројне}} н , к: 1 \ лек к \ лек н-1,

Сада знамо да је сваки биномни коефицијент зависан од два биномна коефицијента. Дакле, ако их некако можемо решити, онда можемо лако узети њихов збир да бисмо пронашли тражени биномни коефицијент. Дакле, ово нам даје интуицију коришћења Динамичко програмирање. Овде су и основни случајеви врло лако прецизирани дп [0] [0] = 1, дп [и] [0] = дп [и] [[и] = 1.

код

Ц ++ код за проналажење биномног коефицијента

#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

Јава код за проналажење биномног коефицијента

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

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

Сложеност времена 

О (Н ^ 2 + К),  јер прерачунавамо биномне коефицијенте до нЦн. Овој операцији треба О (Н ^ 2) време, а затим О (1) време да одговори на сваки упит.

Сложеност простора

О (Н ^ 2),  за чување унапред израчунатих резултата биномних коефицијената.