Хоёртын коэффициент


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Directi Expedia HackerRank Xome
Динамик програмчлал LeetCode Математик

Асуудлын мэдэгдэл

Өгөгдсөн n ба k утгын Биномын коэффициентийг ол.

"нь математикбиномын коэффициентууд эерэг байна бүхэл тоо гэж тохиолддог коэффициентүүд дахь биномийн теорем. Ихэвчлэн биномын коэффициентийг хос бүхэл тоогоор индексжүүлдэг n ≥ k ≥ 0 гэж бичсэн байна ”- иш татсан Википедиа.

Жишээ нь

n = 5, k = 2
10

Тайлбар: Биномын коэффициентийг тооцоолох томъёог ашиглан бид олж мэдэв 5 C 3 энэ нь 10-тай тэнцүү юм.

Биномын коэффициент гэж юу вэ?

Биномын коэффициентийг хэрхэн олохоо мэдэхээс өмнө. Одоо товчхон ярилцъя Биномын коэффициент гэж юу вэ? яагаад үүнийг шаарддаг вэ?

Биномиал коэффициентийг комбинаторикийн асуудлыг шийдвэрлэхэд маш их ашигладаг тул. Танд зарим нь байна гэж бодъё өөр өөр элементүүд байгаа тул та сонгох хэрэгтэй элементүүд. Тиймээс, хэрэв та энэ асуудлыг шийдэхийг хүсвэл n элементээс k элемент сонгосон бүх тохиолдлыг хялбархан бичиж болно. Гэхдээ n нэмэгдэх үед энэ нь маш их цаг хугацаа шаарддаг процесс юм. Энэ асуудлыг биномын коэффициент ашиглан хялбархан шийдвэрлэх боломжтой. Үүнээс гадна n өөр элементээс k элементийг сонгох энэ асуудал нь биномын коэффициентийг тодорхойлох арга замуудын нэг юм n C k. Биномын коэффициентийг дараахь томъёогоор хялбархан тооцоолж болно.

Нэгэнт бид үндсийг сайн эзэмшсэн тул үүнийг үр дүнтэй тооцоолох арга замыг олох хэрэгтэй.

Биномын коэффициентийг олох гэнэн хандлага

Энэ арга нь тийм биш юм дэндүү гэнэн. 3 элементээс 5 элементийг сонгох хэд хэдэн аргыг олохыг танаас хүсч байгаагаа бодоорой. Тиймээс та амархан олох боломжтой н !, к! ба (nk)! өгөгдсөн томъёонд утгыг оруулна уу. Энэ шийдэл нь зөвхөн шаардагдана Цагтаа болон O (1) зай. Гэхдээ заримдаа таны факториал үнэ цэнэ хэтэрч магадгүй тул бид үүнийг анхаарч үзэх хэрэгтэй. Хэрэв бид нэг биномын коэффициентийг тооцоолохыг хүсч байвал энэ арга нь зүгээр юм. Гэхдээ олон удаа бид олон биномын коэффициентийг тооцоолох хэрэгтэй. Тиймээс, тэдгээрийг урьдчилж тооцоолсон нь дээр. Биномын коэффициентийг хэрхэн үр дүнтэй олохыг бид олж мэдэх болно.

Биномын коэффициентийг олох оновчтой арга

Хэрэв бид ганц биномын коэффициент олохыг хүсч байвал гэнэн хандлага нь гэнэн биш байсан. Гэхдээ бид олон тооны binmoial коэффициентийг олох шаардлагатай үед. Тиймээс асуудлыг цаг хугацааны хувьд дуусгахад хэцүү болж байна. Учир нь гэнэн хандлага нь цаг хугацаа их шаарддаг хэвээр байна. Тиймээс, энд биднээс тооцоолохыг хүссэн зарим асуултууд байна 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),  биномын коэффициентүүдийн тооцоолсон үр дүнг хадгалахад зориулагдсан.