گنتی nCr٪ p


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایکسینچر کیڈینس انڈیا کوملی میڈیا اولا کیبس چوک
متحرک پروگرامنگ ریاضی

مسئلہ یہ بیان

"کمپیوٹ این سی آر٪ p" مسئلہ یہ بیان کرتا ہے کہ آپ کو بائنومیئل کوفیفی ماڈیولو پی تلاش کرنے کی ضرورت ہے۔ اس ل you آپ کو پہلے باطنی گتانک کے بارے میں معلوم ہونا چاہئے۔ ہم پہلے ہی اس بارے میں پچھلی پوسٹ میں گفتگو کر چکے ہیں۔ آپ اسے چیک کر سکتے ہیں یہاں.

مثال کے طور پر

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

وضاحت

این سی آر = 5 سی 2 = 10
nCr٪ p = 10٪ 6 = 4
لہذا ، ہم نے بائنومیئل قابلیت کے فارمولے کا استعمال کرتے ہوئے 5C2 کا حساب لگایا۔ پھر قیمت پر موڈولو لیا۔

گنتی nCr٪ p

نقطہ نظر

پچھلی پوسٹ میں بائنومیئل قابلیت کے حساب سے متعلق۔ ہم نے سب سے پہلے ان اقدار کی گنتی کی تھی جو NCr کو حل کرنے کے لئے درکار تھے۔ ہم نے استعمال کیا متحرک پروگرامنگ مسئلے کو حل کرنے کے ل but لیکن پھر ہم صرف این سی آر کی قیمت کا حساب لگارہے تھے۔ نہیں بیومینی گتانک موڈیول کچھ نمبر پی۔ بولی کا نقطہ نظر یہ ہوگا کہ پہلے بایومینیئل قابلیت کا حساب لگائیں اور پھر ماڈیولو پی لیں۔ لیکن اس حساب کتاب میں ایک حد ہے۔ آپ بڑی تعداد میں بائنومیئل گتانکوں کا حساب نہیں لگاسکتے ہیں کیونکہ اس کے نتیجے میں زیادہ بہاؤ ہوجائے گا۔ لہذا ہمیں ایک ایسا راستہ تلاش کرنے کی ضرورت ہے جو عددی حد سے زیادہ بہاؤ میں جانے کے بغیر صحیح نتیجہ پیدا کرسکے۔

ایک چیز جو ہم کرسکتے ہیں وہ ہے ماڈیولس لیتے رہنا جبکہ ہمارے بائنومیئل قابلیت کا حساب کتاب۔ تو پچھلی پوسٹ کا واحد حل یہ ہے کہ ہم حساب کے دوران ماڈیولس لیں گے۔ اس طرح ہمارا بار بار چلنے والا فارمولا تھوڑا سا بدلا جائے گا ، لیکن ٹرانزیشن اسی طرح رہتی ہے۔ اور موجودہ دو طرفہ قابلیت اسی حالتوں پر منحصر ہے جیسا کہ پہلے تھا۔

ضابطے

C ++ کوڈ کے حساب کے لئے NCr٪ p

#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

جاوا کوڈ کی گنتی کے لئے nCr٪ p

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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N * R)، جہاں N اور R دیئے گئے آدان ہیں۔ اس کی وجہ یہ ہے کہ جب ہم اپنے بونومیل گتانک کا حساب لگارہے تھے تو ہمارے پاس بیرونی لوپ اور ایک اندرونی لوپ تھا۔

خلائی پیچیدگی

O (R)، چونکہ ہم نے انٹرمیڈیٹ اقدار کو ذخیرہ کرنے کے لئے ایک صف تیار کی ہے ، اور اس طرح خلائی پیچیدگی لکیری ہے۔