দ্বিপদী সহগ  


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় ডাইরেক্টি এক্সপিডিয়া HackerRank জুম
ডায়নামিক প্রোগ্রামিং লেটকোড ম্যাথ

সমস্যা বিবৃতি  

এন এবং কে এর প্রদত্ত মানের জন্য দ্বিপদী সহগ আবিষ্কার করুন।

"ইন অংক, দ্য দ্বিপদী সহগ ইতিবাচক হয় পূর্ণসংখ্যার যে হিসাবে ঘটে সহগ মধ্যে দ্বিপদী উপপাদ্য। সাধারণত, দ্বিপদী সহগ একটি সংখ্যার পূর্ণসংখ্যার দ্বারা সূচক হয় n ≥ k ≥ 0 এবং হিসাবে লেখা হয় ”- থেকে উদ্ধৃত উইকিপিডিয়া।

উদাহরণ  

n = 5, k = 2
10

ব্যাখ্যা: দ্বিপদী সহগের গণনার জন্য সূত্রটি ব্যবহার করে আমরা সন্ধান করি 5 সি 3 যা 10 এর সমান।

দ্বিপদী সহগ কী?  

দ্বিপদী সহগ কীভাবে সন্ধান করবেন তা জানার আগে সংক্ষেপে আলোচনা করা যাক দ্বিপদী সহগ কী? এবং কেন এটি এমনকি প্রয়োজন?

কারণ বিনোমিয়াল গুণাগুণ সংমিশ্রণ সংক্রান্ত সমস্যাগুলি সমাধান করতে খুব বেশি ব্যবহৃত হয়। বলি আপনার কিছু আছে বিভিন্ন উপাদান এবং আপনি বাছাই করা প্রয়োজন উপাদান। সুতরাং, আপনি যদি এই সমস্যার সমাধান করতে চান তবে সহজেই এন উপাদানগুলির বাইরে কে উপাদানগুলি বেছে নেওয়ার সমস্ত ক্ষেত্রে লিখতে পারেন। N বৃদ্ধি পেলে এটি একটি খুব সময়সাপেক্ষ প্রক্রিয়া। দ্বিপদী সহগ ব্যবহার করে এই সমস্যাটি সহজেই সমাধান করা যায়। এর চেয়েও বেশি, n উপাদানগুলির বাইরে কে উপাদান নির্বাচন করার এই সমস্যাটি দ্বিপদী সহগকে সংজ্ঞায়িত করার অন্যতম উপায় n সি কে। দ্বিপদী সহগকে প্রদত্ত সূত্রটি ব্যবহার করে সহজেই গণনা করা যায়:

যেহেতু এখন আমরা বেসিকগুলিতে ভাল, আমাদের এটি দক্ষতার সাথে গণনা করার উপায়গুলি খুঁজে পাওয়া উচিত।

আরো দেখুন
ত্রিভুজটিতে সর্বাধিক পথের যোগফল

দ্বিপদী সহগ খুঁজে পাওয়ার জন্য নিষ্পাপ দৃষ্টিভঙ্গি  

এই পদ্ধতির না মোটেও নিষ্পাপ। বিবেচনা করুন আপনাকে 3 টি উপাদানের মধ্যে 5 টি উপাদান বেছে নেওয়ার উপায়গুলি খুঁজতে বলা হবে। সুতরাং আপনি সহজেই খুঁজে পেতে পারেন এন !, কে! এবং (এন কে)! এবং প্রদত্ত সূত্রে মানগুলি রাখুন। এই সমাধানটি কেবল নেয় ও (এন) সময় এবং ও (1) স্থান। তবে কখনও কখনও আপনার বর্ণনামূলক মানগুলি উপচে পড়তে পারে তাই আমাদের এটির যত্ন নেওয়া দরকার। যদি আমরা একটি একক দ্বিপদী সহগকে গণনা করতে চাই তবে এই পদ্ধতিরটি ঠিক। তবে অনেক সময় আমাদের অনেক দ্বিপদী সহগগুলি গণনা করতে হবে। সুতরাং, এগুলি পূর্ববর্তী করা ভাল better আমরা দ্বিপদী সহগগুলি কীভাবে দক্ষতার সাথে আবিষ্কার করব তা আবিষ্কার করব।

দ্বিপদী সহগ খুঁজে পাওয়ার জন্য অনুকূল দৃষ্টিভঙ্গি  

হ্যাঁ, আমরা যদি একটি একক দ্বিপদী সহগ খুঁজে পেতে চাইতাম নিখরচায় দৃষ্টিভঙ্গি নিষ্পাপ ছিল না। কিন্তু যখন আমাদের অনেক দ্বিপদী সহগ খুঁজে পাওয়া দরকার। সুতরাং সমস্যাটি সময়সীমাতে সম্পন্ন করা কঠিন হয়ে পড়ে। কারণ নিষ্পাপ দৃষ্টিভঙ্গি এখনও সময়সাপেক্ষ। সুতরাং, এখানে আমাদের কয়েকটি প্রশ্ন রয়েছে যেখানে আমাদের গণনা করতে বলা হয় nCk প্রদত্ত এন এবং কে জন্য অনেক প্রশ্ন থাকতে পারে। এটি সমাধান করার জন্য আমাদের পাসকালের ত্রিভুজটির সাথে পরিচিত হওয়া উচিত। এর কারণ আমাদের আরও পরিষ্কারভাবে বুঝতে সক্ষম করবে যে আমরা কী করতে যাচ্ছি।

দ্বিপদী সহগপিন

পাস্কাল ত্রিভুজের যে কোনও ঘর দ্বিপদী সহগগুলি বোঝায়। পাস্কালের ত্রিভুজ সম্পর্কিত কিছু জিনিস আমাদের জানা দরকার।

  1. এটি 0 সারি দিয়ে শুরু হয়।
  2. পাস্কালের ত্রিভুজের যে কোনও সংখ্যা দ্বিপদী সহগকে বোঝায়।
  3. যে কোনও দ্বিপদী সহগ যা সারির সীমানায় নেই, এমন উপাদানগুলির সংমিশ্রণ থেকে তৈরি করা হয় যা এর উপরে বাম এবং ডানদিকে থাকে।
আরো দেখুন
নিউম্যান-কনওয়ে সিকোয়েন্স

inte om বিনম {n} {কে}} = {\ বিনোম {n-1} {কে-1}} + {\ বিনোম {এন-1} {কে}} \ কোয়াড {\ পাঠ্য {সমস্ত পূর্ণসংখ্যার জন্য}} n , কে: 1 \ লেক কে \ লেক এন -1,

এখন আমরা জানি যে প্রতিটি দ্বিপদী সহগ দুটি দ্বিপদী সহগের উপর নির্ভরশীল। সুতরাং যদি আমরা কোনওভাবে সেগুলি সমাধান করতে পারি তবে আমরা আমাদের প্রয়োজনীয় দ্বিপদী গুণাগুণটি সহজেই তাদের যোগফলটি নিতে পারি। সুতরাং এটি আমাদের ব্যবহারের একটি অন্তর্দৃষ্টি দেয় ডায়নামিক প্রোগ্রামিং। এখানে বেসকেসগুলি খুব সহজেই নির্দিষ্ট করা হয় ডিপি [0] [0] = 1, ডিপি [আমি] [0] = ডিপি [আই] [[আমি] = 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 ^ 2) সময় এবং তারপরে ও (1) সময় নেয়।

আরো দেখুন
ও (যোগফল) স্পেসে সাবসেট সমষ্টি সমস্যা

স্পেস জটিলতা ity

ও (এন ^ 2),  দ্বিপদী সহগের প্রাকম্পৃক্ত ফলাফলগুলি সংরক্ষণ করার জন্য।