દ્વિપદી ગુણાંક


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે ડાયરેક્ટિ એક્સપેડિયા હેકરરંક Xome
ડાયનેમિક પ્રોગ્રામિંગ લેટકોડ મઠ

સમસ્યા નિવેદન

આપેલ મૂલ્ય એન અને કે માટે દ્વિપદી ગુણાંક શોધો.

"માં ગણિતદ્વિપક્ષીય ગુણાંક સકારાત્મક છે પૂર્ણાંક કે તરીકે થાય છે ગુણાંક માં દ્વિપદીય પ્રમેય. સામાન્ય રીતે, દ્વિપક્ષીય ગુણાંક પૂર્ણાંકોની જોડી દ્વારા અનુક્રમિત થાય છે n ≥ k ≥ 0 અને તરીકે લખાયેલ છે ”- માંથી નોંધાયેલા વિકિપીડિયા

ઉદાહરણ

n = 5, k = 2
10

સમજૂતી: દ્વિપક્ષીય ગુણાંકની ગણતરી માટેના સૂત્રનો ઉપયોગ કરીને, આપણે શોધી કા .ીએ છીએ 5 સી 3 જે 10 ની બરાબર છે.

દ્વિપદી ગુણાંક શું છે?

દ્વિપક્ષીય ગુણાંક કેવી રીતે શોધવું તે જાણતા પહેલા. ચાલો ટૂંકમાં ચર્ચા કરીએ દ્વિપદી ગુણાંક શું છે? અને તે શા માટે જરૂરી છે?

કારણ કે કમ્બીનેટરિક્સની સમસ્યાઓ હલ કરવા માટે દ્વિપદી ગુણાંકનો ભારે ઉપયોગ થાય છે. ચાલો કહીએ કે તમારી પાસે કંઈક છે વિવિધ તત્વો અને તમારે પસંદ કરવાની જરૂર છે તત્વો. તેથી, જો તમે આ સમસ્યાને હલ કરવા માંગતા હો, તો તમે n તત્વોમાંથી k તત્વો પસંદ કરવાના બધા કિસ્સા સરળતાથી લખી શકો છો. જ્યારે n વધતી જાય છે ત્યારે આ ખૂબ સમય માંગી લેતી પ્રક્રિયા છે. દ્વિપક્ષી ગુણાંકનો ઉપયોગ કરીને આ સમસ્યા સરળતાથી ઉકેલી શકાય છે. આના કરતાં, n વિવિધ તત્વોમાંથી K તત્વો પસંદ કરવાની આ સમસ્યા, દ્વિપક્ષી ગુણાંકને વ્યાખ્યાયિત કરવાની એક રીત છે એન સી કે. આપેલ સૂત્રનો ઉપયોગ કરીને દ્વિપદી ગુણાંકની ગણતરી સરળતાથી કરી શકાય છે:

હવે આપણે મૂળભૂત બાબતોમાં સારા છીએ, તેથી આપણે તેની અસરકારક રીતે ગણતરી કરવાની રીતો શોધી કા .વી જોઈએ.

દ્વિપક્ષીય ગુણાંક શોધવા માટે નિષ્કપળ અભિગમ

આ અભિગમ નથી બધા નિષ્કપટ ધ્યાનમાં લો કે તમને 3 તત્વોમાંથી 5 તત્વો પસંદ કરવાની રીતોની સંખ્યા શોધવા માટે કહેવામાં આવે છે. તેથી તમે સરળતાથી શોધી શકો છો એન !, કે! અને (એનકે)! અને આપેલ સૂત્રમાં કિંમતો મૂકો. આ સોલ્યુશન માત્ર લે છે સમયસર અને ઓ (1) જગ્યા. પરંતુ કેટલીકવાર તમારા કારણિક મૂલ્યો ઓવરફ્લો થઈ શકે છે તેથી આપણે તેની કાળજી લેવાની જરૂર છે. જો આપણે એક દ્વિપક્ષીય ગુણાંકની ગણતરી કરવી હોય તો આ અભિગમ બરાબર છે. પરંતુ ઘણી વાર આપણે ઘણા દ્વિપક્ષી સહગુણાંકોની ગણતરી કરવાની જરૂર છે. તેથી, તેમને પૂર્વનિર્ધારિત કરવું વધુ સારું છે. અમે દ્વિપક્ષી સહગુણાંકોને અસરકારક રીતે કેવી રીતે શોધવી તે શોધીશું.

દ્વિપક્ષીય ગુણાંક શોધવા માટે Approપ્ટિમાઇઝ અભિગમ

જો આપણે એક દ્વિપક્ષીય ગુણાંક શોધવા માંગતા હો, તો નિષ્કપટ અભિગમ નિષ્કપટ ન હતો. પરંતુ જ્યારે આપણે ઘણા દ્વિપક્ષીય ગુણાંક શોધવાની જરૂર હોય છે. તેથી સમસ્યા સમય મર્યાદામાં પૂર્ણ કરવી મુશ્કેલ બની જાય છે. કારણ કે નિષ્કપટ અભિગમ હજી સમય માંગે છે. તેથી, અહીં આપણી પાસે કેટલીક ક્વેરીઝ છે જ્યાં આપણને ગણતરી કરવા માટે કહેવામાં આવે છે એનસીકે આપેલ એન અને કે માટે ઘણી પ્રશ્નો હોઈ શકે છે. આને હલ કરવા માટે આપણે પાસ્કલના ત્રિકોણથી પરિચિત હોવા જોઈએ. તેનું કારણ આપણને ખૂબ સ્પષ્ટપણે સમજાય છે કે આપણે જે કરવાનું છે તે કરીશું.

દ્વિપદી ગુણાંક

પાસ્કલ ત્રિકોણનો કોઈપણ કોષ દ્વિપક્ષી સહગુણાંકો સૂચવે છે. આપણે પાસ્કલના ત્રિકોણને લગતી કેટલીક બાબતો જાણવાની જરૂર છે.

  1. તે પંક્તિ 0 થી શરૂ થાય છે.
  2. પાસ્કલના ત્રિકોણમાંની કોઈપણ સંખ્યા દ્વિપક્ષી ગુણાંક સૂચવે છે.
  3. કોઈપણ દ્વિપક્ષીય ગુણાંક જે પંક્તિની સીમાઓ પર નથી તે તત્વોના સારાંશથી બનાવવામાં આવે છે જે તેની ઉપરથી ડાબી અને જમણી દિશામાં હોય છે.

inte om બિનોમ {n} {કે}} = {\ બિનોમ {n-1 {{કે -1}} + {\ બિનોમ {n-1} {કે}} \ ક્વોડ {\ ટેક્સ્ટ all બધા પૂર્ણાંકો માટે}} n , કે: 1 \ લીક કે q લિક એન -1,

હવે આપણે જાણીએ છીએ કે દરેક દ્વિપદી ગુણાંક બે દ્વિપદીય ગુણાંક પર આધારિત છે. તેથી જો આપણે કોઈક રીતે તેનો હલ કરી શકીએ તો આપણે સરળતાથી જરૂરી રકમ દ્વિપક્ષી ગુણાંક શોધવા માટે લઈ શકીએ છીએ. તો આ આપણને ઉપયોગ કરવાની અંતર્જ્ .ાન આપે છે ડાયનેમિક પ્રોગ્રામિંગ. અહીં બેઝકેસો પણ ખૂબ જ સરળતાથી સ્પષ્ટ થયેલ છે ડીપી [0] [0] = 1, ડીપી [હું] [0] = ડીપી [i] [[હું] = 1.

કોડ

દ્વિપક્ષીય ગુણાંક શોધવા માટે સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા 

ઓ (એન ^ 2 + ક્યૂ),  કારણ કે આપણે એન.સી.એન. સુધીના દ્વિપક્ષીય ગુણાંકોને પૂર્ણાહુતિ કરીએ છીએ. આ ક્રિયા દરેક ક્વેરીનો જવાબ આપવા માટે ઓ (N O 2) સમય લે છે અને પછી ઓ (1) સમય લે છે.

અવકાશ જટિલતા

ઓ (એન ^ 2),  દ્વિપક્ષી સહગુણાંકોના પૂર્વાનુમાનિત પરિણામો સંગ્રહિત કરવા માટે.