ද්විමය සංගුණකය


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඩිරෙක්ටි Expedia හැකර් රැන්ක් Xome
ගතික වැඩසටහන්කරණය ලීට්කෝඩ් ගණිතය

ගැටළු ප්රකාශය

ලබා දී ඇති n සහ k අගය සඳහා ද්විමය සංගුණකය සොයා ගන්න.

"තුළ ගණිතය, එම ද්විමාන සංගුණක ධනාත්මක වේ නිඛිල එය සිදු වේ සංගුණක තුළ ද්විමය ප්‍රමේයය. පොදුවේ ගත් කල, ද්විමාන සංගුණකය පූර්ණ සංඛ්‍යා යුගලයක් මඟින් සුචිගත කරනු ලැබේ n ≥ k ≥ 0 ලෙස ලියා ඇත ”- උපුටා දක්වා ඇත විකිපීඩියා

උදාහරණයක්

n = 5, k = 2
10

පැහැදිලි කිරීම: ද්විමය සංගුණකය ගණනය කිරීම සඳහා සූත්‍රය භාවිතා කිරීමෙන් අපට පෙනී යයි 5 සී 3 එය 10 ට සමාන වේ.

ද්විමය සංගුණකය යනු කුමක්ද?

ද්විමය සංගුණකය සොයා ගන්නේ කෙසේදැයි දැන ගැනීමට පෙර. අපි කෙටියෙන් සාකච්ඡා කරමු ද්විමය සංගුණකය යනු කුමක්ද? එය අවශ්‍ය වන්නේ ඇයි?

සංයුක්ත ගැටලු විසඳීම සඳහා ද්විමය සංගුණකය විශාල වශයෙන් භාවිතා කරන බැවිනි. අපි ඔබට කියමු විවිධ අංග සහ ඔබ තෝරා ගත යුතුය මූලද්රව්ය. එබැවින්, ඔබට මෙම ගැටළුව විසඳීමට අවශ්‍ය නම්, මූලද්‍රව්‍ය n වලින් k මූලද්‍රව්‍ය තෝරා ගැනීමේ සියලු අවස්ථා පහසුවෙන් ලිවිය හැකිය. නමුත් n වැඩි වන විට මෙය බොහෝ කාලයක් ගතවන ක්‍රියාවලියකි. ද්විමය සංගුණකය භාවිතයෙන් මෙම ගැටළුව පහසුවෙන් විසඳා ගත හැකිය. ඊටත් වඩා, විවිධ මූලද්‍රව්‍ය n වලින් k මූලද්‍රව්‍ය තෝරා ගැනීමේ මෙම ගැටළුව ද්විමය සංගුණකය අර්ථ දැක්වීමේ එක් ක්‍රමයකි n සී කේ. දී ඇති සූත්‍රය භාවිතයෙන් ද්විමාන සංගුණකය පහසුවෙන් ගණනය කළ හැකිය:

දැන් අපි මූලික කරුණු පිළිබඳව හොඳ මට්ටමක සිටින බැවින් මෙය කාර්යක්ෂමව ගණනය කිරීමට ක්‍රම සොයා ගත යුතුය.

ද්විමය සංගුණකය සොයා ගැනීම සඳහා බොළඳ ප්‍රවේශය

මෙම ප්‍රවේශය එසේ නොවේ කිසිසේත් බොළඳ ය. මූලද්රව්ය 3 න් මූලද්රව්ය 5 ක් තෝරා ගැනීමේ ක්රම සොයා ගැනීමට ඔබෙන් ඉල්ලා ඇති බව සලකන්න. එබැවින් ඔබට පහසුවෙන් සොයාගත හැකිය n!, k! සහ (nk)! දී ඇති සූත්‍රයේ අගයන් දමන්න. මෙම විසඳුම පමණක් අවශ්‍ය වේ වෙලාවට සහ ඕ (1) අවකාශය. නමුත් සමහර විට ඔබේ සාධකීය අගයන් පිරී ඉතිරී යා හැකි බැවින් අපි ඒ ගැන සැලකිලිමත් විය යුතුය. අපට තනි ද්විමය සංගුණකයක් ගණනය කිරීමට අවශ්‍ය නම් මෙම ප්‍රවේශය හොඳයි. නමුත් බොහෝ විට අපට බොහෝ ද්විමය සංගුණක ගණනය කළ යුතුය. එබැවින්, ඒවා පූර්ව ගණනය කිරීම වඩා හොඳය. ද්විමය සංගුණක කාර්යක්ෂමව සොයා ගන්නේ කෙසේදැයි අපි සොයා බලමු.

ද්විමය සංගුණකය සොයා ගැනීම සඳහා ප්‍රශස්ත ප්‍රවේශය

අපට තනි ද්විමය සංගුණකයක් සොයා ගැනීමට අවශ්‍ය නම් බොළඳ ප්‍රවේශය බොළඳ නොවේ. නමුත් අපට බොහෝ ද්විමාන සංගුණක සොයා ගැනීමට අවශ්‍ය වූ විට. එබැවින් ගැටළුව කාල සීමාව තුළ සම්පූර්ණ කිරීම දුෂ්කර වේ. බොළඳ ප්‍රවේශය තවමත් කාලය ගතවන බැවිනි. ඉතින්, මෙහිදී අපට ගණනය කිරීම් කිහිපයක් විමසනු ලැබේ nCk ලබා දී ඇති n සහ k සඳහා. බොහෝ විමසුම් තිබිය හැකිය. මෙය විසඳීම සඳහා අපි පැස්කල්ගේ ත්‍රිකෝණය ගැන දැන සිටිය යුතුය. හේතුව අප කුමක් කිරීමට යන්නේද යන්න අපට පැහැදිලිව අවබෝධ වනු ඇත.

ද්විමය සංගුණකය

පැස්කල් ත්‍රිකෝණයේ ඇති ඕනෑම සෛලයක් ද්විමාන සංගුණක දක්වයි. පැස්කල්ගේ ත්‍රිකෝණය සම්බන්ධයෙන් අප යම් යම් දේ දැන සිටිය යුතුය.

  1. එය 0 පේළියෙන් ආරම්භ වේ.
  2. පැස්කල්ගේ ත්‍රිකෝණයේ ඇති ඕනෑම සංඛ්‍යාවක් ද්විමාන සංගුණකය දක්වයි.
  3. පේළියේ මායිම්වල නොමැති ඕනෑම ද්විමාන සංගුණකය සෑදී ඇත්තේ ඊට ඉහළින් ඇති මූලද්‍රව්‍යවල එකතුව වම් සහ දකුණු දිශාවට ය.

inte \ binom {n} {k}} = {in binom {n-1} {k-1}} + {\ binom {n-1} {k}} ad quad {\ text 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) කාලය ගතවේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (එන් ^ 2),  ද්විමාන සංගුණකවල පූර්ව සම්පාදනය කළ ප්‍රති results ල ගබඩා කිරීම සඳහා.