द्विपद गुणांक


कठिनाई स्तर मध्यम
में अक्सर पूछा डायरेक्टी Expedia HackerRank ज़ोम
गतिशील प्रोग्रामिंग लेटकोड मठ

समस्या का विवरण

N और k के दिए गए मान के लिए द्विपद गुणांक ज्ञात कीजिए।

"में गणितद्विपद गुणांक सकारात्मक हैं पूर्णांकों जैसा कि होता है गुणांक में द्विपद प्रमेय। आमतौर पर, एक द्विपद गुणांक पूर्णांक की एक जोड़ी द्वारा अनुक्रमित होता है n ≥ k ≥ 0 और के रूप में लिखा है ”- से उद्धृत विकिपीडिया.

उदाहरण

n = 5, k = 2
10

स्पष्टीकरण: द्विपद गुणांक की गणना के लिए सूत्र का उपयोग करना, हम पाते हैं 5 C 3 जो 10 के बराबर है।

द्विपद गुणांक क्या है?

यह जानने से पहले कि द्विपद गुणांक कैसे पाया जाए। आइए संक्षेप में चर्चा करें द्विपद गुणांक क्या है? और इसकी आवश्यकता क्यों है?

क्योंकि कॉम्बिनेटरिक्स समस्याओं को हल करने के लिए द्विपदीय गुणांक का अत्यधिक उपयोग किया जाता है। मान लीजिए कि आपके पास कुछ है विभिन्न तत्वों और आप लेने की जरूरत है तत्व। इसलिए, यदि आप इस समस्या को हल करना चाहते हैं, तो आप आसानी से n तत्वों में से k तत्वों को चुनने के सभी मामलों को लिख सकते हैं। लेकिन n बढ़ने पर यह बहुत समय लेने वाली प्रक्रिया है। द्विपद गुणांक का उपयोग करके इस समस्या को आसानी से हल किया जा सकता है। इससे अधिक, अलग-अलग तत्वों में से k तत्वों को चुनने की यह समस्या द्विपद गुणांक को परिभाषित करने के तरीकों में से एक है एन सी के। द्विपद गुणांक को आसानी से दिए गए सूत्र का उपयोग करके गणना की जा सकती है:

चूंकि अब हम मूल बातें अच्छे हैं, हमें इसे कुशलता से गणना करने के तरीके खोजने चाहिए।

द्विपद गुणांक खोजने के लिए Naive दृष्टिकोण

यह दृष्टिकोण नहीं है बहुत भोला। विचार करें कि आपको 3 तत्वों में से 5 तत्वों को चुनने के तरीकों की संख्या ज्ञात करने के लिए कहा जाता है। तो आप आसानी से पा सकते हैं n !, के! और (nk)! और दिए गए सूत्र में मान डालें। यह समाधान केवल लेता है समय पर और O (1) स्थान। लेकिन कभी-कभी आपके तथ्यात्मक मूल्य भी बह सकते हैं, इसलिए हमें इसका ध्यान रखना चाहिए। यह दृष्टिकोण ठीक है अगर हम एक एकल द्विपद गुणांक की गणना करना चाहते हैं। लेकिन कई बार हमें कई द्विपद गुणांक की गणना करने की आवश्यकता होती है। इसलिए, बेहतर है कि उन्हें प्री-कॉम्पट्यूट किया जाए। हम यह पता लगाएंगे कि कैसे द्विपद गुणांक को कुशलता से पाया जाए।

द्विपद गुणांक खोजने के लिए अनुकूलित दृष्टिकोण

ठीक है, अगर हम एक भी द्विपद गुणांक प्राप्त करना चाहते हैं तो भोली दृष्टिकोण भोला नहीं था। लेकिन जब हमें कई द्विपद गुणांक खोजने की आवश्यकता होती है। तो समय सीमा में समस्या को पूरा करना मुश्किल हो जाता है। क्योंकि भोली दृष्टिकोण अभी भी समय लेने वाला है। इसलिए, यहां हमारे पास कुछ प्रश्न हैं, जहां हमें गणना करने के लिए कहा जाता है एनसीके दिए गए n और k के लिए। कई प्रश्न हो सकते हैं। इसे हल करने के लिए हमें पास्कल के त्रिभुज से परिचित होना चाहिए। कारण जो हमें बहुत स्पष्ट रूप से समझाएंगे कि हम जो करने जा रहे हैं वह हम क्यों कर रहे हैं।

द्विपद गुणांक

पास्कल त्रिकोण में कोई भी सेल द्विपद गुणांक को दर्शाता है। हमें पास्कल के त्रिकोण के बारे में कुछ बातें जानने की जरूरत है।

  1. इसकी शुरुआत पंक्ति 0 से होती है।
  2. पास्कल के त्रिकोण में कोई भी संख्या द्विपद गुणांक को दर्शाता है।
  3. कोई भी द्विपद गुणांक जो पंक्ति की सीमाओं पर नहीं है, उन तत्वों के योग से बना है जो इसके बाईं और दाईं दिशा में ऊपर हैं।

{# बिनोम {n} {k}} = {\ binom {n-1} {k-1}} + {\ binom {n-1} {k}} \ quad {\ text {सभी पूर्णांकों के लिए}} n , k: 1 \ leq k \ leq n-1,

अब हम जानते हैं कि प्रत्येक द्विपद गुणांक दो द्विपद गुणांक पर निर्भर है। इसलिए यदि हम किसी तरह उन्हें हल कर सकते हैं तो हम अपने आवश्यक द्विपद गुणांक को खोजने के लिए आसानी से उनकी राशि ले सकते हैं। तो यह हमें उपयोग करने का एक अंतर्ज्ञान देता है गतिशील प्रोग्रामिंग। यहां बेसकेश भी बहुत आसानी से निर्दिष्ट हैं dp [0] [०] = १, dp [i] [०] = dp [i] [[i] = १।

कोड

द्विपद गुणांक खोजने के लिए 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 तक precomputing कर रहे हैं। यह ऑपरेशन प्रत्येक क्वेरी का उत्तर देने के लिए O (N ^ 2) समय और उसके बाद O (1) समय लेता है।

अंतरिक्ष जटिलता

ओ (एन ^ 2),  द्विपद गुणांक के पूर्ववर्ती परिणामों को संग्रहीत करने के लिए।