Биномдық коэффициент


Күрделілік дәрежесі орта
Жиі кіреді Directi Expedia HackerRank Xome
Динамикалық бағдарламалау LeetCode математика

Проблемалық мәлімдеме

N және k берілген мәні үшін Биномдық коэффициентті табыңыз.

«In математикабиномдық коэффициенттер оң болып табылады бүтін сандар ретінде пайда болады коэффициенттер ішінде биномдық теорема. Әдетте, биномдық коэффициент жұп бүтін сандармен индекстеледі n ≥ k ≥ 0 ретінде жазылады »- деп келтірілген Уикипедия.

мысал

n = 5, k = 2
10

Түсініктеме: биномдық коэффициентті есептеу формуласын пайдаланып, табамыз 5 С 3 бұл 10-ға тең.

Биномдық коэффициент дегеніміз не?

Биномдық коэффициентті қалай табуға болатынын білмес бұрын. Қысқаша талқылайық Биномдық коэффициент дегеніміз не? және неге бұл тіпті қажет?

Биномдық коэффициент комбинаторика мәселелерін шешу үшін көп қолданылатындықтан. Сізде біраз бар делік әр түрлі элементтерді таңдау керек элементтер. Егер сіз бұл мәселені шешкіңіз келсе, онда n элементтің ішінен k элементтерін таңдаудың барлық жағдайларын оңай жаза аласыз. N өскенде бұл өте көп уақытты алатын процесс. Бұл мәселені биномдық коэффициенттің көмегімен оңай шешуге болады. Бұдан басқа, n әр түрлі элементтердің ішінен k элементтерін таңдау мәселесі биномдық коэффициентті анықтау тәсілдерінің бірі болып табылады n C k. Биномдық коэффициентті мына формула арқылы оңай есептеуге болады:

Қазір біз негіздерді жақсы білетін болғандықтан, оны тиімді есептеудің жолдарын табуымыз керек.

Биномдық коэффициентті іздеудің қарапайым әдісі

Бұл тәсіл емес мүлдем аңғалдық. Сізден 3 элементтің ішінен 5 элементті таңдау тәсілін табуды сұраймыз. Сондықтан сіз оңай таба аласыз н! к! және (nk)! және берілген формулаға мәндерді қойыңыз. Бұл шешім тек қабылдайды Уақытында және O (1) кеңістігі. Бірақ кейде сіздің факторлық құндылықтарыңыз асып кетуі мүмкін, сондықтан біз бұл туралы ойлануымыз керек. Егер біз бір биномдық коэффициентті есептегіміз келсе, бұл тәсіл жақсы. Бірақ көптеген биномдық коэффициенттерді есептеу керек. Сондықтан оларды алдын-ала есептеген дұрыс. Биномдық коэффициенттерді қалай тиімді табуға болатынын білеміз.

Биномдық коэффициентті табудың оңтайландырылған тәсілі

Жалғыз биномдық коэффициент тапқымыз келсе, аңғалдық аңғалдық емес еді. Бірақ біз көптеген бинмиялық коэффициенттерді табуымыз керек болғанда. Мәселен, мәселені мерзімінде аяқтау қиын болады. Өйткені аңғалдық тәсіл әлі көп уақытты алады. Сонымен, міне, бізде сұралатын бірнеше сұрақ бар, оларды есептеу керек nCk берілген n және k үшін. Сұрақтар көп болуы мүмкін. Мұны шешу үшін біз Паскаль үшбұрышымен таныс болуымыз керек. Неліктен біз не істейтінімізді нақты түсінуге мүмкіндік беретін себеп.

Биномдық коэффициент

Паскаль үшбұрышындағы кез-келген ұяшық биномдық коэффициенттерді білдіреді. Біз Паскаль үшбұрышына қатысты кейбір нәрселерді білуіміз керек.

  1. Ол 0 қатарынан басталады.
  2. Паскаль үшбұрышындағы кез келген сан биномдық коэффициентті білдіреді.
  3. Жол шекарасында жоқ кез-келген биномдық коэффициент сол жақта және оң жақта оның дәл үстінде тұрған элементтердің қосындысынан алынады.

{\ binom {n} {k}} = {\ binom {n-1} {k-1}} + {\ binom {n-1} {k}} \ quad {\ text {барлық бүтін сандар үшін}} n , k: 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

Күрделілікті талдау

Уақыттың күрделілігі 

O (N ^ 2 + Q),  өйткені біз биномдық коэффициенттерді nCn дейін есептейміз. Бұл операция әр сұрауға жауап беру үшін O (N ^ 2) уақытты, содан кейін O (1) уақытты алады.

Ғарыштың күрделілігі

O (N ^ 2),  биномдық коэффициенттердің алдын ала есептелген нәтижелерін сақтауға арналған.