حساب ڪريو nCr٪ پي


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Accenture سيڊنس انڊيا ڪولي ميڊيا اولا ڪئابس چورس
متحرڪ پروگرامنگ Math

مسئلي جو بيان

مسئلو “Compute nCr٪ p” ٻڌائي ٿو ته توهان کي بوموميشنل ڪوآرڊينيو ماڊلو پي ڳولڻ جي ضرورت آهي. تنهن ڪري پهريان توهان کي بينوميئل گنجائش جي باري ۾ mustاڻڻ گهرجي. اسان اڳ ۾ ئي بحث ڪيو ته گذريل پوسٽ ۾. توهان اهو چيڪ ڪري سگهو ٿا هتي.

مثال

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

وضاحت

nCr = 5C2 = 10
nCr٪ p = 10٪ 6 = 4
تنهن ڪري ، اسان 5C2 جي حساب سان بائنومل گنجائش جي فارمولا استعمال ڪيو. پوءِ ويل ويل مولو قدر مٿان.

حساب ڪريو nCr٪ پي

چرچو

پوئين پوسٽ ۾ بائنومل ايجاد جي حساب سان. جيڪو اسان ڪيو هو پهرين انهن قدرن جو حساب ڪتاب ڪيو ويو جيڪي اين سي آر کي حل ڪرڻ جي ضرورت هئا. اسان استعمال ڪيو متحرڪ پروگرامنگ مسئلو حل ڪرڻ لاءِ پر اسان nCr جي قيمت کي صرف ڳڻپيندا رهيا سين. بائنوملڪ ڪوئفيول ماڊلڊو نه ڪي نمبر پي. غير معمولي طريقي سان پهرين طور تي بائنوملل ڪيڪسن کي حساب ڪرڻ گهرجي ۽ پوءِ ماڊليو پي کي ڪ takeڻو پوندو. پر هن ڳڻپيوڪر تي هڪ حد آهي. توھان وڏي تعداد ۾ بائنوملل ظاھر جو حساب نٿا لڳائي سگھو ڇاڪاڻ ته ان جي نتيجي ۾ اوور فلو ٿيندو. تنهنڪري اسان کي هڪ رستو ڳولڻ جي ضرورت آهي جيڪا انٽيگرنٽ اوور فلو ۾ وڃي بغير صحيح نتيجو پيدا ڪري سگهي.

هڪ شي جيڪا اسان ڪري سگهون ٿا اهو موڊوليس وٺڻ جاري آهي جڏهن ته اسان جي بائنوملڪ حساب جي حساب سان. تنهنڪري واحد تبديلي واري پوئين پوسٽ جو حل آهي ته اسان حساب جي دوران ماڊلول وٺنداسين. اهڙيءَ طرح اسان جو تربيتي فارمولا ڪجهه تبديل ٿي ويندو ، پر منتقلي ساڳي رهي ٿي. ۽ موجوده بائنومل گنجائش وڌيڪ رياستن تي منحصر آهي جيڪي اڳي هئا.

ڪوڊ

nCr٪ p کي ڳڻپ ڪرڻ لاءِ C ++ ڪوڊ

#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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين * آر)جتي اين ۽ آر داخل ڪيا ويا آهن. اهو ڇو ته جڏهن اسان پنهنجو Binomial Coeffice ڳڻپ ڪري رهيا هئاسين ، اسان وٽ هڪ ٻاهرئين لوپ ۽ هڪ اندروني لوپ هو.

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

اي (ر)جڏهن کان اسان وچولي قدرن کي ذخيرو ڪرڻ لاءِ آرينج ٺاهيو ۽ اهڙي طرح خلائي پيچيدگي لڪير آهي.