ຕົວຄູນ Binomial


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Directi Expedia ແຮກເກີຣ Xome
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ LeetCode ຄະນິດສາດ

ຖະແຫຼງການບັນຫາ

ຊອກຫາຕົວຄູນ Binomial ສຳ ລັບຄ່າຂອງ n ແລະ k.

"ໃນ ຄະນິດສາດ, ການ ຕົວຄູນ binomial ແມ່ນໃນທາງບວກ integers ທີ່ເກີດຂຶ້ນເປັນ ຕົວຄູນ ໃນ ທິດສະດີບົດມ. ໂດຍທົ່ວໄປ, ຕົວຄູນ binomial ແມ່ນຖືກດັດສະນີໂດຍຄູ່ຄູ່ n ≥ k ≥ 0 ແລະຖືກຂຽນເປັນ ” - ອ້າງອີງຈາກ Wikipedia

ຍົກຕົວຢ່າງ

n = 5, k = 2
10

ຄຳ ອະທິບາຍ: ການ ນຳ ໃຊ້ສູດ ສຳ ລັບການຄິດໄລ່ຕົວຄູນ binomial, ພວກເຮົາພົບ 5 C 3 ເຊິ່ງເທົ່າກັບ 10.

ຕົວຄູນ Binomial ແມ່ນຫຍັງ?

ກ່ອນທີ່ຈະຮູ້ວິທີການຊອກຫາຕົວຄູນ binomial. ຂໍໃຫ້ພິຈາລະນາສັ້ນໆ ຕົວຄູນ Binomial ແມ່ນຫຍັງ? ແລະເປັນຫຍັງມັນຈິ່ງ ຈຳ ເປັນ?

ເນື່ອງຈາກວ່າຕົວຄູນ Binomial ຖືກໃຊ້ຢ່າງ ໜັກ ເພື່ອແກ້ໄຂບັນຫາການປະສົມປະສານ. ໃຫ້ເວົ້າວ່າທ່ານມີບາງຢ່າງ ອົງປະກອບທີ່ແຕກຕ່າງກັນແລະທ່ານຕ້ອງການເລືອກເອົາ ອົງປະກອບ. ສະນັ້ນ, ຖ້າທ່ານຕ້ອງການແກ້ໄຂບັນຫານີ້ທ່ານສາມາດຂຽນທຸກກໍລະນີຂອງການເລືອກ k ອົງປະກອບອອກຈາກ n element. ແຕ່ນີ້ແມ່ນຂະບວນການທີ່ໃຊ້ເວລາຫຼາຍເມື່ອ n ເພີ່ມຂື້ນ. ບັນຫານີ້ສາມາດແກ້ໄຂໄດ້ງ່າຍໂດຍ ນຳ ໃຊ້ຕົວຄູນ binomial. ຍິ່ງໄປກວ່ານັ້ນ, ບັນຫານີ້ໃນການເລືອກເອົາອົງປະກອບ k ອອກຈາກ n ອົງປະກອບທີ່ແຕກຕ່າງກັນແມ່ນ ໜຶ່ງ ໃນວິທີການທີ່ຈະ ກຳ ນົດຕົວຄູນ binomial n C k. ຕົວຄູນ Binomial ສາມາດຄິດໄລ່ໄດ້ງ່າຍໂດຍໃຊ້ສູດທີ່ໃຫ້ໄວ້:

ຍ້ອນວ່າດຽວນີ້ພວກເຮົາເກັ່ງພື້ນຖານ, ພວກເຮົາຄວນຊອກຫາວິທີຕ່າງໆໃນການຄິດໄລ່ສິ່ງນີ້ຢ່າງມີປະສິດຕິຜົນ.

ວິທີການ Naive ສໍາລັບການຊອກຫາຕົວຄູນ Binomial

ວິທີການນີ້ບໍ່ແມ່ນ naive ເກີນໄປຢູ່ໃນທຸກ. ພິຈາລະນາທ່ານຖືກຂໍໃຫ້ຊອກຫາ ຈຳ ນວນວິທີການໃນການເລືອກ 3 ອົງປະກອບຈາກ 5 ອົງປະກອບ. ດັ່ງນັ້ນທ່ານສາມາດຫາໄດ້ງ່າຍ ນ!, ກ! ແລະ (nk)! ແລະເອົາຄ່າເຂົ້າໃນສູດທີ່ໃຫ້ໄວ້. ວິທີແກ້ໄຂນີ້ໃຊ້ເວລາເທົ່ານັ້ນ ຕົງ​ເວ​ລາ ແລະ O (1) ພື້ນທີ່. ແຕ່ບາງຄັ້ງຄຸນຄ່າຂອງຂໍ້ເທັດຈິງຂອງທ່ານອາດຈະລົ້ນເກີນໄປສະນັ້ນພວກເຮົາຕ້ອງໄດ້ເບິ່ງແຍງສິ່ງນັ້ນ. ວິທີການນີ້ແມ່ນດີຖ້າພວກເຮົາຕ້ອງການຄິດໄລ່ຕົວຄູນ binomial ດຽວ. ແຕ່ຫຼາຍຄັ້ງພວກເຮົາຕ້ອງຄິດໄລ່ຕົວຄູນ binomial ຫຼາຍ. ສະນັ້ນ, ມັນດີກວ່າທີ່ຈະໃຫ້ພວກເຂົາມີ ຄຳ ເຫັນກ່ອນ. ພວກເຮົາຈະຊອກຫາວິທີການຊອກຫາຕົວຄູນ binomial ຢ່າງມີປະສິດຕິຜົນ.

ວິທີການທີ່ດີທີ່ສຸດສໍາລັບການຊອກຫາຕົວຄູນ Binomial

ດີ, ວິທີການທີ່ໂງ່ຈ້າບໍ່ແມ່ນຄວາມໂງ່ຖ້າພວກເຮົາຕ້ອງການຊອກຫາຕົວຄູນ binomial ດຽວ. ແຕ່ເມື່ອພວກເຮົາຕ້ອງການຊອກຫາຕົວຄູນ binmoial ຫຼາຍ. ສະນັ້ນບັນຫາຈະກາຍເປັນເລື່ອງຍາກທີ່ຈະເຮັດໃຫ້ ສຳ ເລັດຕາມ ກຳ ນົດເວລາ. ເນື່ອງຈາກວ່າວິທີການທີ່ໂງ່ຈ້າຍັງໃຊ້ເວລາຫຼາຍ. ດັ່ງນັ້ນ, ນີ້ພວກເຮົາມີ ຄຳ ຖາມບາງບ່ອນທີ່ພວກເຮົາຖືກຂໍໃຫ້ຄິດໄລ່ nCk ສຳ ລັບ n ແລະ k. ອາດຈະມີການສອບຖາມຫຼາຍຢ່າງ. ເພື່ອແກ້ໄຂບັນຫານີ້ພວກເຮົາຄວນຄຸ້ນເຄີຍກັບສາມຫຼ່ຽມ Pascal. ສາເຫດທີ່ຈະເຮັດໃຫ້ພວກເຮົາເຂົ້າໃຈຫຼາຍຢ່າງຊັດເຈນວ່າເປັນຫຍັງພວກເຮົາຈະເຮັດໃນສິ່ງທີ່ພວກເຮົາຈະເຮັດ.

ຕົວຄູນ Binomial

ຈຸລັງໃດໃນສາມຫຼ່ຽມ pascal ໝາຍ ເຖິງຕົວຄູນ binomial. ພວກເຮົາຕ້ອງຮູ້ບາງສິ່ງທີ່ກ່ຽວຂ້ອງກັບສາມຫຼ່ຽມຂອງ Pascal.

  1. ມັນເລີ່ມຕົ້ນດ້ວຍແຖວ 0.
  2. ຕົວເລກໃດໆໃນສາມຫຼ່ຽມຂອງ Pascal ໝາຍ ເຖິງຕົວຄູນ binomial.
  3. ຕົວຄູນ binomial ໃດທີ່ບໍ່ຢູ່ໃນຂອບເຂດຂອງແຖວແມ່ນເຮັດຈາກການສະຫຼຸບຂອງອົງປະກອບທີ່ຢູ່ ເໜືອ ມັນໃນທິດທາງຊ້າຍແລະຂວາ.

{\ binom {n} {k}} = {\ binom {n-1} {k-1}} + {\ binom {n-1} {k}} \ quad {\ ຂໍ້ຄວາມ {ສຳ ລັບເລກລວມທັງ ໝົດ}} n , k: 1 \ leq k \ leq n-1,

ດຽວນີ້ພວກເຮົາຮູ້ແລ້ວວ່າຕົວຄູນ binomial ແຕ່ລະຕົວຂື້ນຢູ່ກັບສອງຕົວຄູນ binomial. ດັ່ງນັ້ນຖ້າພວກເຮົາສາມາດແກ້ໄຂບັນຫາເຫລົ່ານັ້ນໄດ້ຢ່າງງ່າຍດາຍພວກເຮົາສາມາດເອົາຍອດລວມຂອງພວກເຂົາໄປຫາຕົວຄູນ binomial ທີ່ພວກເຮົາຕ້ອງການ. ດັ່ງນັ້ນສິ່ງນີ້ຈຶ່ງເຮັດໃຫ້ພວກເຮົາມີຄວາມຕັ້ງໃຈໃນການ ນຳ ໃຊ້ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ. ໃນທີ່ນີ້ຖານຂໍ້ມູນກໍ່ຖືກລະບຸຢ່າງງ່າຍດາຍ dp [0] [0] = 1, dp [i] [0] = dp [i] [[i] = 1.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບຊອກຫາ Binomial Coefficient

#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 ເພື່ອຊອກຫາຕົວຄູນ Binomial

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),  ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງ ນຳ ໃຊ້ຕົວຄູນ binomial ຈົນເຖິງ nCn. ການປະຕິບັດງານນີ້ໃຊ້ເວລາ O (N ^ 2) ແລະຫຼັງຈາກນັ້ນ O (1) ໃຊ້ເວລາເພື່ອຕອບ ຄຳ ຖາມແຕ່ລະຄັ້ງ.

ຄວາມສັບສົນໃນອະວະກາດ

O (N ^ 2),  ສຳ ລັບການເກັບຮັກສາຜົນໄດ້ຮັບທີ່ໄດ້ກ່າວມາກ່ອນຂອງຕົວຄູນ binomial.