ضریب دوجمله ای


سطح دشواری متوسط
اغلب در دیرتی Expedia HackerRank Xome
برنامه نویسی پویا LeetCode ریاضی

بیان مسأله

ضریب Binomial را برای یک مقدار مشخص n و k پیدا کنید.

"در ریاضیاتاز ضرایب دو جمله ای مثبت هستند عدد صحیح که رخ می دهد به عنوان ضرایب در قضیه دوتایی. معمولاً ضریب دوجمله ای توسط یک جفت عدد صحیح نمایه می شود n ≥ k ≥ 0 و به صورت نوشته شده است ”- به نقل از ویکیپدیا کمک کنید.

مثال

n = 5, k = 2
10

توضیح: با استفاده از فرمول محاسبه ضریب دو جمله ای ، می یابیم 5 C 3 که برابر با 10 است.

ضریب دوجمله ای چیست؟

قبل از اینکه بدانید چگونه ضریب دوجمله ای را پیدا کنید. بیایید به طور خلاصه بحث کنیم ضریب دو جمله ای چیست؟ و چرا حتی مورد نیاز است؟

زیرا از ضریب Binomial به شدت برای حل مشکلات ترکیبی استفاده می شود. بگذارید بگوییم شما مقداری دارید عناصر مختلف و شما نیاز به انتخاب کنید عناصر. بنابراین ، اگر می خواهید این مشکل را حل کنید ، می توانید به راحتی همه موارد انتخاب عناصر k را از n عنصر بنویسید. اما وقتی n افزایش می یابد ، این یک فرایند بسیار زمانبر است. با استفاده از ضریب دوجمله ای این مشکل به راحتی قابل حل است. بیشتر از آن ، این مشکل انتخاب عناصر k از n عنصر مختلف یکی از راه های تعیین ضریب دوجمله ای است n C k ضریب دو جمله ای را می توان با استفاده از فرمول داده شده به راحتی محاسبه کرد:

از آنجا که ما در اصول کار مهارت داریم ، باید روشهایی برای محاسبه موثر آن پیدا کنیم.

رویکرد ساده لوحانه برای یافتن ضریب دوجمله ای

این رویکرد اینگونه نیست اصلاً خیلی ساده لوحانه در نظر بگیرید که از شما خواسته شده تعداد روشهای انتخاب 3 عنصر از 5 عنصر را پیدا کنید. بنابراین به راحتی می توانید پیدا کنید n !، k! و (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 برای یافتن ضریب Binomial

#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) ،  برای ذخیره نتایج محاسبه شده ضرایب دوجمله ای.