இரும குணகம்  


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது டைரக்டி Expedia ஹேக்கர் தரவரிசை Xome
டைனமிக் புரோகிராமிங் லீட்கோட் கணித

சிக்கல் அறிக்கை  

கொடுக்கப்பட்ட n மற்றும் k இன் மதிப்புக்கு இரும குணகம் கண்டுபிடிக்கவும்.

"ஆம் கணிதம், அந்த இருமுனை குணகம் நேர்மறை முழு என நிகழ்கிறது குணகங்கள் உள்ள இருபக்க தேற்றம். பொதுவாக, ஒரு ஜோடி முழு எண்களால் ஒரு பைனோமியல் குணகம் குறியிடப்படுகிறது n ≥ k ≥ 0 மற்றும் என எழுதப்பட்டுள்ளது ”- மேற்கோள் காட்டப்பட்டுள்ளது விக்கிபீடியா.

உதாரணமாக  

n = 5, k = 2
10

விளக்கம்: இருபக்க குணகத்தைக் கணக்கிடுவதற்கான சூத்திரத்தைப் பயன்படுத்தி, நாம் காண்கிறோம் 5 சி 3 இது 10 க்கு சமம்.

பைனோமியல் குணகம் என்றால் என்ன?  

பைனோமியல் குணகத்தை எவ்வாறு கண்டுபிடிப்பது என்பதை அறிவதற்கு முன். சுருக்கமாக விவாதிப்போம் பைனோமியல் குணகம் என்றால் என்ன? அது ஏன் தேவைப்படுகிறது?

ஏனென்றால் பைனமியல் குணகம் கூட்டு சிக்கல்களை தீர்க்க பெரிதும் பயன்படுத்தப்படுகிறது. உங்களிடம் சில உள்ளன என்று சொல்லலாம் வெவ்வேறு கூறுகள் மற்றும் நீங்கள் எடுக்க வேண்டும் கூறுகள். எனவே, இந்த சிக்கலை நீங்கள் தீர்க்க விரும்பினால், n உறுப்புகளில் இருந்து k கூறுகளைத் தேர்ந்தெடுக்கும் அனைத்து நிகழ்வுகளையும் எளிதாக எழுதலாம். ஆனால் n அதிகரிக்கும் போது இது மிகவும் நேரத்தை எடுத்துக்கொள்ளும் செயல்முறையாகும். இந்த சிக்கலை இருபக்க குணகத்தைப் பயன்படுத்தி எளிதில் தீர்க்க முடியும். அதற்கும் மேலாக, n வெவ்வேறு கூறுகளில் இருந்து k கூறுகளைத் தேர்ந்தெடுப்பதில் இந்த சிக்கல் இருவகை குணகத்தை வரையறுப்பதற்கான ஒரு வழியாகும் n சி கே. கொடுக்கப்பட்ட சூத்திரத்தைப் பயன்படுத்தி இரும குணகம் எளிதில் கணக்கிடப்படலாம்:

இப்போது நாம் அடிப்படைகளில் நல்லவர்கள் என்பதால், இதை திறமையாக கணக்கிடுவதற்கான வழிகளை நாம் கண்டுபிடிக்க வேண்டும்.

மேலும் காண்க
ஒரு முக்கோணத்தில் அதிகபட்ச பாதை தொகை

பைனோமியல் குணகத்தைக் கண்டுபிடிப்பதற்கான அப்பாவி அணுகுமுறை  

இந்த அணுகுமுறை இல்லை மிகவும் அப்பாவியாக. 3 உறுப்புகளில் 5 கூறுகளைத் தேர்ந்தெடுப்பதற்கான வழிகளின் எண்ணிக்கையைக் கண்டறியும்படி கேட்கப்படுவதைக் கவனியுங்கள். எனவே நீங்கள் எளிதாக கண்டுபிடிக்கலாம் n!, க! மற்றும் (nk)! கொடுக்கப்பட்ட சூத்திரத்தில் மதிப்புகளை வைக்கவும். இந்த தீர்வு மட்டுமே எடுக்கும் சரியான நேரத்தில் மற்றும் ஓ (1) இடம். ஆனால் சில நேரங்களில் உங்கள் காரணியாலான மதிப்புகள் நிரம்பி வழிகிறது, எனவே நாங்கள் அதை கவனித்துக் கொள்ள வேண்டும். ஒற்றை இருவகை குணகத்தை நாம் கணக்கிட விரும்பினால் இந்த அணுகுமுறை நன்றாக இருக்கும். ஆனால் பல முறை நாம் பல இரும குணகங்களைக் கணக்கிட வேண்டும். எனவே, அவற்றை முன்கூட்டியே கணக்கிடுவது நல்லது. இருவகைக் குணகங்களை எவ்வாறு திறமையாகக் கண்டுபிடிப்பது என்பதைக் கண்டுபிடிப்போம்.

பைனோமியல் குணகத்தைக் கண்டுபிடிப்பதற்கான உகந்த அணுகுமுறை  

ஒரு இருவகை குணகத்தைக் கண்டுபிடிக்க விரும்பினால், அப்பாவியாக அணுகுமுறை அப்பாவியாக இல்லை. ஆனால் நாம் பல இருமுனை குணகங்களைக் கண்டுபிடிக்க வேண்டியிருக்கும் போது. எனவே சிக்கலை நேர வரம்பில் முடிக்க கடினமாகிறது. அப்பாவியாக அணுகுமுறை இன்னும் நேரம் எடுக்கும் என்பதால். எனவே, இங்கே நாம் கணக்கிட சில கேள்விகள் உள்ளன nCk கொடுக்கப்பட்ட n மற்றும் k க்கு. பல கேள்விகள் இருக்கலாம். இதைத் தீர்க்க நாம் பாஸ்கலின் முக்கோணத்தை நன்கு அறிந்திருக்க வேண்டும். நாம் என்ன செய்யப் போகிறோம் என்பதை ஏன் செய்யப் போகிறோம் என்பது நமக்குத் தெளிவாகத் தெரியும்.

இரும குணகம்முள்

பாஸ்கல் முக்கோணத்தில் உள்ள எந்த கலமும் இருவக குணகங்களைக் குறிக்கிறது. பாஸ்கலின் முக்கோணம் தொடர்பான சில விஷயங்களை நாம் தெரிந்து கொள்ள வேண்டும்.

  1. இது 0 வது வரிசையில் தொடங்குகிறது.
  2. பாஸ்கலின் முக்கோணத்தில் உள்ள எந்த எண்ணும் இருவக குணகத்தைக் குறிக்கிறது.
  3. வரிசையின் எல்லைகளில் இல்லாத எந்த இருவக குணகம் இடது மற்றும் வலது திசையில் அதற்கு மேலே உள்ள தனிமங்களின் தொகுப்பிலிருந்து தயாரிக்கப்படுகிறது.
மேலும் காண்க
நியூமன்-கான்வே வரிசை

inte \ binom {n} {k}} = {in binom {n-1} {k-1}} + {\ binom {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) நேரத்தையும் எடுக்கும்.

மேலும் காண்க
ஓ (தொகை) இடத்தில் கூட்டுத்தொகை சிக்கல்

விண்வெளி சிக்கலானது

ஓ (என் ^ 2),  இருமுனை குணகங்களின் முன் தயாரிக்கப்பட்ட முடிவுகளை சேமிப்பதற்காக.