Коэффитсиенти биномӣ


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Directi Expedia HackerRank Xome
Барномарезии динамикӣ LeetCode Матем

Изҳороти мушкилот

Барои арзиши додаи n ва k коэффисиенти биномиро ёбед.

«Дар риёзиёт, ки коэффитсиентҳои биномалӣ мусбат мебошанд ҳаждаҳҳо ки рух медиҳанд коэффитсиентҳо дар теоремаи биномӣ. Одатан, коэффисиенти биномиро бо як ҷуфти бутун индекс мекунанд n ≥ k ≥ 0 ва ҳамчун навишта шудааст ”- иқтибос аз Википедия

мисол

n = 5, k = 2
10

Шарҳ: Бо истифода аз формулаи ҳисобкунии коэффисиенти биномиалӣ, мо пайдо мекунем 5 C 3 ки ба 10 баробар аст.

Коэффисиенти Биномӣ чист?

Пеш аз донистани чӣ гуна пайдо кардани коэффисиенти биномалӣ Биёед мухтасар муҳокима кунем Коэффисиенти Биномӣ чист? ва чаро ин ҳатто талаб карда мешавад?

Азбаски коэффисиенти Биномиалӣ барои ҳалли масъалаҳои комбинатория сахт истифода мешавад. Биёед бигӯем, ки шумо каме доред унсурҳои гуногун ва ба шумо лозим аст, ки чидани унсурҳо. Пас, агар шумо хоҳед, ки ин масъаларо ҳал кунед, шумо метавонед ҳамаи ҳолатҳои интихоби n элементро аз n унсур ба осонӣ нависед. Аммо ин раванди хеле зиёдро талаб мекунад, вақте ки n зиёд мешавад. Ин масъаларо бо истифода аз коэффисиенти биномӣ ба осонӣ ҳал кардан мумкин аст. Зиёда аз он, ин масъалаи интихоби элементҳои k аз n унсури гуногун яке аз роҳҳои муайян кардани коэффисиенти биномӣ мебошад 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),  барои нигоҳ доштани натиҷаҳои пешакии коэффисиентҳои биномиалӣ