ბინომის კოეფიციენტი


Რთული ტური საშუალო
ხშირად ეკითხებიან დირექტი Expedia HackerRank Xome
დინამიური პროგრამირება LeetCode მათემატიკის

პრობლემის განცხადება

იპოვნეთ binomial კოეფიციენტი n და k მოცემული მნიშვნელობისთვის.

"In მათემატიკისსაქართველოს ბინომური კოეფიციენტები პოზიტიურია რიცხვები რომ მოხდეს როგორც კოეფიციენტები იმ ბინომური თეორემა. ჩვეულებრივ, ბინომის კოეფიციენტი ინდექსირებულია წყვილი მთელი რიცხვით n ≥ k ≥ 0 და იწერება როგორც ”- ციტირებულია აქედან ვიკიპედია

მაგალითი

n = 5, k = 2
10

განმარტება: ბინომის კოეფიციენტის გაანგარიშების ფორმულის გამოყენებით ვხვდებით 5 გ 3 რაც უდრის 10-ს.

რა არის ბინომის კოეფიციენტი?

სანამ იცოდე როგორ იპოვნო ბინომიალური კოეფიციენტი. მოკლედ განვიხილოთ რა არის ბინომის კოეფიციენტი? და რატომ არის ეს საჭირო?

იმის გამო, რომ ბინომიალური კოეფიციენტი გამოიყენება კომბინატორიკის პრობლემების გადასაჭრელად. ვთქვათ, თქვენ გაქვთ რამდენიმე სხვადასხვა ელემენტები და თქვენ უნდა აირჩიოთ ელემენტები. თუ ამ პრობლემის მოგვარება გსურთ, მარტივად შეგიძლიათ დაწეროთ k ელემენტების n ელემენტიდან არჩევის ყველა შემთხვევა. მაგრამ ეს ძალიან შრომატევადი პროცესია, როდესაც n იზრდება. ამ პრობლემის მოგვარება მარტივია ბინომური კოეფიციენტის გამოყენებით. უფრო მეტიც, n სხვადასხვა ელემენტიდან k ელემენტების არჩევის ეს პრობლემა არის ბიომიალური კოეფიციენტის განსაზღვრის ერთ-ერთი გზა n C k Binomial კოეფიციენტი ადვილად გამოითვლება მოცემული ფორმულის გამოყენებით:

რადგან ახლა ჩვენ კარგად ვფლობთ საფუძვლებს, უნდა ვიპოვოთ ამის ეფექტურად გამოთვლის გზები.

გულუბრყვილო მიდგომა ბინომური კოეფიციენტის პოვნისთვის

ეს მიდგომა არ არის ზედმეტად გულუბრყვილო. გაითვალისწინეთ, რომ მოგეთხოვებათ იპოვოთ 3 ელემენტიდან 5 ელემენტის არჩევის გზების რაოდენობა. ასე რომ თქვენ მარტივად იპოვით ნ !, კ! და (ნკ)! და მოცემულ ფორმულაში ჩასვით მნიშვნელობები. ამ გამოსავალს მხოლოდ სჭირდება Დროზე და 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.

კოდი

Binomial კოეფიციენტის მოსაძებნად 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

ჯავა კოდი ბინომის კოეფიციენტის მოსაძებნად

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),  ბინომური კოეფიციენტების წინასწარ გათვლილი შედეგების შესანახად.