गणना एनसीआर% पी


अडचण पातळी सोपे
वारंवार विचारले ऐक्सचर कॅडन्स इंडिया कोमली मीडिया ओला कॅब स्क्वेअर
डायनॅमिक प्रोग्रामिंग गणित

समस्या विधान

“कंप्यूट एनसीआर% पी” ही समस्या सांगते की आपल्याला द्विपदी गुणांक मॉड्यूलो पी शोधणे आवश्यक आहे. तर आपल्याला प्रथम द्विपक्षीय गुणांबद्दल माहित असणे आवश्यक आहे. आम्ही आधीच्या पोस्टमध्ये याबद्दल चर्चा केली आहे. आपण ते तपासू शकता येथे.

उदाहरण

n = 5, r = 2, p = 6
4

स्पष्टीकरण

एनसीआर = 5 सी 2 = 10
एनसीआर% पी = 10% 6 = 4
तर, आम्ही द्विपक्षीय गुणकाचे सूत्र वापरून 5 सी 2 मोजले. नंतर मूल्येनुसार मॉड्यूलो घेतला.

गणना एनसीआर% पी

दृष्टीकोन

मागील पोस्टमध्ये द्विपदी गुणकाच्या गणनाबद्दल. आम्ही प्रथम एनसीआर सोडविण्यासाठी आवश्यक असलेल्या मूल्यांची गणना केली. आम्ही वापरले डायनॅमिक प्रोग्रामिंग समस्येचे निराकरण करण्यासाठी परंतु आम्ही फक्त एनसीआरच्या मूल्याची गणना करत होतो. द्विपक्षीय गुणांक मोड्यूलो नाही काही संख्या पी. भोळे दृष्टिकोन म्हणजे प्रथम द्विपदी गुणांक मोजणे आणि नंतर मॉड्युलो पी. परंतु या गणनेवर एक मर्यादा आहे. आपण मोठ्या संख्येने द्विपदीय गुणांकांची गणना करू शकत नाही कारण त्याचा परिणाम ओव्हरफ्लो होईल. म्हणून आम्हाला एखादा मार्ग शोधणे आवश्यक आहे जे पूर्णांक ओव्हरफ्लोमध्ये न जाता योग्य परिणाम देईल.

आपण करू शकणारी एक गोष्ट म्हणजे आपल्या द्विपदी गुणाकारांची गणना करताना मॉड्यूलस घेणे चालू ठेवणे. मागील पोस्टचा सोल्यूशन एकमेव बदल म्हणजे आपण गणना दरम्यान मॉड्यूलस घेऊ. अशाप्रकारे आमचे रिकर्सीव्ह फॉर्म्युला थोडा बदलेल, परंतु संक्रमणे तीच राहिली. आणि सध्याचा द्विपक्षीय गुणांक पूर्वीच्या राज्याप्रमाणेच त्याच राज्यांवर अवलंबून आहे.

कोड

एन + सीआर% पी मोजण्यासाठी सी ++ कोड

#include<bits/stdc++.h>
using namespace std;
// this function just makes our pascal triangle
int computeBinomialCoefficientsModuloP(int n, int r, int p)
{
  int C[r+1];
    C[0] = 1;
    for (int i = 0; i <= n; i++)
    {
        // since the recursive formula is dependent on current and previous binomial coefficient on i
        // if we had run a forward loop our algorithm would have not given us a correct result
        for (int j = min(i, r); j >0 ; j--)
        {
            C[j] = (C[j - 1] + C[j])%p; // use recursive formula
        }
    }
    return C[r];
}

int main()
{
    int n,k,p;cin>>n>>k>>p;
    // here n & k do not satisfy the properties of binomial coefficient
    // then we will answer it as 0
    int val = computeBinomialCoefficientsModuloP(n, k, p);
    if(val != 0)
      cout<<val<<endl;
    else
      cout<<0<<endl;
}
5 2 4
2

एनसीआर% पी मोजण्यासाठी जावा कोड

import java.util.*;
class Main{
  // this function just makes our pascal triangle
  static int computeBinomialCoefficientsModuloP(int n, int r, int p) 
  {
  	int C[] = new int[r+1];
  	C[0] = 1;
    for (int i = 0; i <= n; i++) 
    { 
      // since the recursive formula is dependent on current and previous binomial coefficient on i
      // if we had run a forward loop our algorithm would have not given us a correct result 
      for (int j = Math.min(i, r); j >0 ; j--) 
      {
          C[j] = (C[j - 1] + C[j])%p; // use recursive formula
      }
    } 
    return C[r]; 
  }
  
  public static void main(String[] args)
  {
      Scanner sc = new Scanner(System.in);
      // 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();
      int p = sc.nextInt();
      int val = computeBinomialCoefficientsModuloP(n, k, p);
      if(val != 0)
        System.out.println(val);    
      else
        System.out.println(0);
   }
}
5 2 4
2

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन * आर), जेथे एन आणि आर दिलेली माहिती आहेत. कारण जेव्हा आम्ही आमच्या द्विपदीय गुणांकांची गणना करीत होतो तेव्हा आमच्याकडे बाह्य पळवाट आणि एक आंतरिक पळवाट होती.

स्पेस कॉम्प्लेक्सिटी

किंवा), आम्ही दरम्यानचे मूल्ये संचयित करण्यासाठी अ‍ॅरे बनविल्यामुळे आणि अशा प्रकारे स्पेसची गुंतागुंत रेषात्मक आहे.