Binom əmsalı

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Directi Expedia HackerRank Xome
Dinamik proqramlaşdırma LeetCode RiyaziyyatBaxılıb 35

Problem bəyanat

Verilən n və k dəyəri üçün Binomial əmsalı tapın.

"In riyaziyyatKi, binomial əmsallar müsbətdir tamsayılar kimi meydana gəlir əmsallar ci binom teoremi. Ümumiyyətlə, bir binomial əmsal bir cüt tam ədəd ilə indekslənir n ≥ k ≥ 0 kimi yazılır ”- sitat gətirildi Vikipediya.

misal

n = 5, k = 2
10

İzahat: Binomial əmsalı hesablamaq üçün düsturdan istifadə edərək tapırıq 5 C 3 bu 10-a bərabərdir.

Binom katsayısı nədir?

Binom katsayısını necə tapacağınızı bilmədən əvvəl. Qısaca müzakirə edək Binom katsayısı nədir? və niyə belə tələb olunur?

Binomial əmsalı kombinatorika problemlərini həll etmək üçün çox istifadə olunduğundan. Deyək ki, bir neçəsi var fərqli elementlər və seçmək lazımdır elementlər. Beləliklə, bu problemi həll etmək istəyirsinizsə, n element arasından k element seçməyin bütün hallarını asanlıqla yaza bilərsiniz. Ancaq n artdıqda bu çox vaxt aparan bir prosesdir. Bu problem binom katsayısı istifadə edilərək asanlıqla həll edilə bilər. Bundan əlavə, n fərqli element arasından k elementinin seçilməsi problemi binomial əmsalı təyin etməyin yollarından biridir n C k. Binomial əmsalı aşağıdakı düsturdan istifadə edərək asanlıqla hesablamaq olar:

İndi əsasları yaxşı bildiyimiz üçün bunu səmərəli hesablamağın yollarını tapmalıyıq.

Binom katsayısını tapmaq üçün sadəlövh yanaşma

Bu yanaşma deyil ümumiyyətlə çox sadəlövhdür. 3 element arasından 5 element seçmə yollarının sayını tapmağınızı xahiş etdiyinizi düşünün. Beləliklə asanlıqla tapa bilərsiniz n! k! və (nk)! və verilənləri düstura qoyun. Bu həll yalnız tələb edir VaxtındaO (1) boşluq. Ancaq bəzən faktorial dəyərləriniz aşıb-çıxa bilər, buna görə buna diqqət yetirməliyik. Tək bir binom katsayısını hesablamaq istəyiriksə, bu yanaşma yaxşıdır. Ancaq dəfələrlə bir çox binomial əmsalı hesablamalıyıq. Beləliklə, onları əvvəlcədən hesablamaq daha yaxşıdır. Binom katsayılarını necə səmərəli şəkildə tapacağımızı öyrənəcəyik.

Binomial əmsalı tapmaq üçün optimal yanaşma

Tək bir binomiya əmsalı tapmaq istəsək, sadəlövh yanaşma sadəlövhlük deyildi. Ancaq bir çox binmoial əmsal tapmaq lazım olduğunda. Beləliklə problemi vaxtında başa çatdırmaq çətinləşir. Çünki sadəlövh yanaşma hələ çox vaxt aparır. Beləliklə, burada hesablamaq istəndiyimiz bəzi sorğular var nCk verilən n və k üçün. Çox sual ola bilər. Bunu həll etmək üçün Paskalın Üçbucağı ilə tanış olmalıyıq. Nə edəcəyimizi niyə edəcəyimizi bizə çox aydın başa salacağımız səbəb.

Binom əmsalıPin

Paskal üçbucağındakı hər hansı bir hüceyrə binomial əmsalları bildirir. Paskalın üçbucağı ilə bağlı bəzi şeyləri bilməliyik.

  1. Sıra 0 ilə başlayır.
  2. Paskalın üçbucağındakı istənilən rəqəm binomial əmsalı bildirir.
  3. Sətrin hüdudlarında olmayan hər hansı bir binomiya əmsalı soldan və sağdan yuxarıda yerləşən elementlərin cəmindən alınır.

{\ binom {n} {k}} = {\ binom {n-1} {k-1}} + {\ binom {n-1} {k}} \ quad {\ text {bütün tam ədədlər üçün}} n , k: 1 \ leq k \ leq n-1,Pin

İndi bilirik ki, hər binomiya əmsalı iki binomial əmsala bağlıdır. Beləliklə, onları bir şəkildə həll edə bilsək, tələb olunan binom katsayısını tapmaq üçün cəmini asanlıqla götürə bilərik. Beləliklə, bu bizə istifadə etmək üçün bir intuisiya verir Dinamik proqramlaşdırma. Burada əsas məqamlar da çox asanlıqla göstərilmişdir dp [0] [0] = 1, dp [i] [0] = dp [i] [[i] = 1.

Kodu

Binom katsayısını tapmaq üçün C ++ kodu

#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

Binom Katsayısını tapmaq üçün Java Kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi 

O (N ^ 2 + Q),  çünki binomial əmsalları nCn-ə qədər hesablayırıq. Bu əməliyyat hər bir sorğuya cavab vermək üçün O (N ^ 2) vaxt və sonra O (1) vaxt tələb edir.

Kosmik Mürəkkəblik

O (N ^ 2),  binomial əmsalların əvvəlcədən hesablanmış nəticələrini saxlamaq üçün.

Translate »