ദ്വിമാന ഗുണകം  


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ഡയറക്റ്റി ബൈ ഹാക്കർ റാങ്ക് സോം
ഡൈനാമിക് പ്രോഗ്രാമിംഗ് ലീട്ട് കോഡ് മഠം

പ്രശ്നം പ്രസ്താവന  

N, k എന്നിവയുടെ ഒരു നിശ്ചിത മൂല്യത്തിനായി ദ്വിമാന ഗുണകം കണ്ടെത്തുക.

"ൽ ഗണിതംദ്വിമാന ഗുണകങ്ങൾ പോസിറ്റീവ് ആണ് പൂർണ്ണസംഖ്യകൾ അത് സംഭവിക്കുന്നു ഗുണകങ്ങൾ ലെ ദ്വിമാന സിദ്ധാന്തം. സാധാരണയായി, ഒരു ജോഡി പൂർണ്ണസംഖ്യകളാൽ ഒരു ദ്വിമാന ഗുണകം സൂചികയിലാക്കുന്നു n ≥ k ≥ 0 എന്ന് എഴുതിയിരിക്കുന്നു ”- ഉദ്ധരിച്ചത് വിക്കിപീഡിയ

ഉദാഹരണം  

n = 5, k = 2
10

വിശദീകരണം: ദ്വിമാന ഗുണകം കണക്കാക്കുന്നതിനുള്ള സമവാക്യം ഉപയോഗിച്ച്, ഞങ്ങൾ കണ്ടെത്തി 5 സി 3 ഇത് 10 ന് തുല്യമാണ്.

എന്താണ് ബൈനോമിയൽ കോഫിഫിഷ്യന്റ്?  

ദ്വിമാന ഗുണകം എങ്ങനെ കണ്ടെത്താമെന്ന് അറിയുന്നതിന് മുമ്പ്. നമുക്ക് സംക്ഷിപ്തമായി ചർച്ച ചെയ്യാം എന്താണ് ദ്വിമാന ഗുണകം? എന്തുകൊണ്ടാണ് ഇത് ആവശ്യമായി വരുന്നത്?

കോമ്പിനേറ്ററിക്സ് പ്രശ്നങ്ങൾ പരിഹരിക്കുന്നതിന് ബൈനോമിയൽ കോഫിഫിഷ്യന്റ് വളരെയധികം ഉപയോഗിക്കുന്നു. നിങ്ങൾക്ക് കുറച്ച് ഉണ്ടെന്ന് പറയാം വ്യത്യസ്ത ഘടകങ്ങൾ കൂടാതെ നിങ്ങൾ തിരഞ്ഞെടുക്കേണ്ടതുണ്ട് ഘടകങ്ങൾ. അതിനാൽ, നിങ്ങൾക്ക് ഈ പ്രശ്നം പരിഹരിക്കണമെങ്കിൽ n ഘടകങ്ങളിൽ നിന്ന് k ഘടകങ്ങൾ തിരഞ്ഞെടുക്കുന്നതിനുള്ള എല്ലാ കേസുകളും എളുപ്പത്തിൽ എഴുതാം. N വർദ്ധിക്കുമ്പോൾ ഇത് വളരെ സമയമെടുക്കുന്ന പ്രക്രിയയാണ്. ദ്വിമാന ഗുണകം ഉപയോഗിച്ച് ഈ പ്രശ്നം എളുപ്പത്തിൽ പരിഹരിക്കാൻ കഴിയും. അതിലുപരിയായി, n വ്യത്യസ്ത ഘടകങ്ങളിൽ നിന്ന് k ഘടകങ്ങൾ തിരഞ്ഞെടുക്കുന്നതിനുള്ള ഈ പ്രശ്നം ദ്വിമാന ഗുണകം നിർവചിക്കാനുള്ള ഒരു മാർഗമാണ് n സി കെ. തന്നിരിക്കുന്ന സൂത്രവാക്യം ഉപയോഗിച്ച് ദ്വിമാന ഗുണകം എളുപ്പത്തിൽ കണക്കാക്കാം:

ഇപ്പോൾ ഞങ്ങൾ അടിസ്ഥാനകാര്യങ്ങളിൽ നല്ലവരായതിനാൽ, ഇത് കാര്യക്ഷമമായി കണക്കാക്കാനുള്ള വഴികൾ കണ്ടെത്തണം.

ദ്വിമാന ഗുണകം കണ്ടെത്തുന്നതിനുള്ള നിഷ്കളങ്കമായ സമീപനം  

ഈ സമീപനം അല്ല വളരെ നിഷ്കളങ്കമാണ്. 3 ഘടകങ്ങളിൽ 5 ഘടകങ്ങൾ തിരഞ്ഞെടുക്കുന്നതിനുള്ള മാർഗങ്ങൾ കണ്ടെത്താൻ നിങ്ങളോട് ആവശ്യപ്പെടുന്നത് പരിഗണിക്കുക. അതിനാൽ നിങ്ങൾക്ക് എളുപ്പത്തിൽ കണ്ടെത്താനാകും n!, കെ! (nk)! തന്നിരിക്കുന്ന സമവാക്യത്തിൽ മൂല്യങ്ങൾ ഇടുക. ഈ പരിഹാരം മാത്രമേ എടുക്കൂ സമയത്ത് ഒപ്പം O (1) ഇടം. എന്നാൽ ചിലപ്പോൾ നിങ്ങളുടെ ഫാക്റ്റോറിയൽ മൂല്യങ്ങൾ കവിഞ്ഞേക്കാം, അതിനാൽ ഞങ്ങൾ അത് ശ്രദ്ധിക്കേണ്ടതുണ്ട്. ഒരൊറ്റ ദ്വിമാന ഗുണകം കണക്കാക്കണമെങ്കിൽ ഈ സമീപനം മികച്ചതാണ്. എന്നാൽ പലതവണ നമ്മൾ പല ദ്വിമാന ഗുണകങ്ങളും കണക്കാക്കേണ്ടതുണ്ട്. അതിനാൽ, അവ മുൻ‌കൂട്ടി തയ്യാറാക്കിയതാണ് നല്ലത്. ദ്വിപദീയ ഗുണകങ്ങളെ എങ്ങനെ കാര്യക്ഷമമായി കണ്ടെത്താമെന്ന് ഞങ്ങൾ കണ്ടെത്തും.

ഇതും കാണുക
ഒരു ത്രികോണത്തിലെ പരമാവധി പാത്ത് തുക

ദ്വിമാന ഗുണകം കണ്ടെത്തുന്നതിനുള്ള ഒപ്റ്റിമൈസ് ചെയ്ത സമീപനം  

ഒരൊറ്റ ദ്വിമാന ഗുണകം കണ്ടെത്തണമെങ്കിൽ നിഷ്കളങ്കമായ സമീപനം നിഷ്കളങ്കമായിരുന്നില്ല. എന്നാൽ നമുക്ക് ധാരാളം ബിൻ‌മോയൽ ഗുണകങ്ങൾ കണ്ടെത്തേണ്ടി വരുമ്പോൾ. അതിനാൽ സമയപരിധി പൂർത്തിയാക്കാൻ പ്രശ്നം ബുദ്ധിമുട്ടാണ്. നിഷ്കളങ്കമായ സമീപനം ഇപ്പോഴും സമയമെടുക്കുന്നു. അതിനാൽ, കണക്കാക്കാൻ ആവശ്യപ്പെടുന്ന ചില ചോദ്യങ്ങൾ ഇവിടെയുണ്ട് nCk നൽകിയ n, k എന്നിവയ്‌ക്ക്. നിരവധി ചോദ്യങ്ങൾ ഉണ്ടാകാം. ഇത് പരിഹരിക്കാൻ പാസ്കലിന്റെ ത്രികോണം നമുക്ക് പരിചിതമായിരിക്കണം. കാരണം ഞങ്ങൾ എന്താണ് ചെയ്യാൻ പോകുന്നത് എന്ന് വ്യക്തമായി മനസിലാക്കാൻ ഇത് കാരണമാകും.

ദ്വിമാന ഗുണകം

പാസ്കൽ ത്രികോണത്തിലെ ഏത് സെല്ലും ദ്വിമാന ഗുണകങ്ങളെ സൂചിപ്പിക്കുന്നു. പാസ്കലിന്റെ ത്രികോണത്തെക്കുറിച്ച് ചില കാര്യങ്ങൾ അറിയേണ്ടതുണ്ട്.

  1. ഇത് 0 വരിയിൽ ആരംഭിക്കുന്നു.
  2. പാസ്കലിന്റെ ത്രികോണത്തിലെ ഏത് സംഖ്യയും ദ്വിമാന ഗുണകത്തെ സൂചിപ്പിക്കുന്നു.
  3. വരിയുടെ അതിരുകളില്ലാത്ത ഏതൊരു ദ്വിപദ കോഫിഫിഷ്യന്റും അതിനു മുകളിലുള്ള ഇടത്, വലത് ദിശയിലുള്ള മൂലകങ്ങളുടെ സംഗ്രഹത്തിൽ നിന്നാണ് നിർമ്മിച്ചിരിക്കുന്നത്.

inte \ ബിനോം {n} {k}} = {in ബിനോം {n-1} {k-1}} + {\ ബിനോം {n-1} {k}} ad ക്വാഡ് {\ വാചകം all എല്ലാ സംഖ്യകൾക്കും}} n , k: 1 \ leq k \ leq n-1,

ഓരോ ദ്വിമാന ഗുണകവും രണ്ട് ദ്വിമാന ഗുണകങ്ങളെ ആശ്രയിച്ചിരിക്കുന്നുവെന്ന് ഇപ്പോൾ നമുക്കറിയാം. അതിനാൽ നമുക്ക് അവ എങ്ങനെയെങ്കിലും പരിഹരിക്കാൻ കഴിയുമെങ്കിൽ, നമുക്ക് ആവശ്യമായ ബൈനോമിയൽ കോഫിഫിഷ്യന്റ് കണ്ടെത്താൻ അവയുടെ തുക എളുപ്പത്തിൽ എടുക്കാം. അതിനാൽ ഇത് ഉപയോഗത്തിനുള്ള ഒരു അവബോധം നൽകുന്നു ഡൈനാമിക് പ്രോഗ്രാമിംഗ്. ഇവിടെ ബേസ്‌കേസുകളും വളരെ എളുപ്പത്തിൽ വ്യക്തമാക്കുന്നു dp [0] [0] = 1, dp [i] [0] = dp [i] [[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

സങ്കീർണ്ണത വിശകലനം  

സമയ സങ്കീർണ്ണത 

O (N ^ 2 + Q),  കാരണം ഞങ്ങൾ nCn വരെ ദ്വിപദ ഗുണകങ്ങളെ മുൻ‌കൂട്ടി കംപ്യൂട്ട് ചെയ്യുന്നു. ഈ പ്രവർത്തനത്തിന് ഓരോ ചോദ്യത്തിനും ഉത്തരം നൽകാൻ O (N ^ 2) സമയവും O (1) സമയവും എടുക്കും.

ഇതും കാണുക
ന്യൂമാൻ-കോൺവേ സീക്വൻസ്

ബഹിരാകാശ സങ്കീർണ്ണത

O (N ^ 2),  ദ്വിപദ കോഫിഷ്യന്റുകളുടെ മുൻ‌കൂട്ടി തയ്യാറാക്കിയ ഫലങ്ങൾ സംഭരിക്കുന്നതിന്.