ስሌት nCr% p  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ Accenture ካዴንስ ህንድ ኮምሊ ሚዲያ ኦላ ካብስ አራት ማዕዘን
ተለዋዋጭ ፕሮግራም ሒሳብ

የችግሩ መግለጫ  

ችግሩ “Compute nCr% p” የሚለው ቢንዮሚያል Coefficient modulo p ን ማግኘት ይጠበቅብዎታል። ስለዚህ በመጀመሪያ ስለ ‹ቢኖሚያል› መጠን ማወቅ አለብዎት ፡፡ ቀደም ባለው ልጥፍ ላይ ያንን ቀደም ብለን ተወያይተናል ፡፡ ያንን ማረጋገጥ ይችላሉ እዚህ.

ለምሳሌ  

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

ማስረጃ

nCr = 5C2 = 10
nCr% p = 10% 6 = 4
ስለዚህ ፣ የሁለትዮሽ ቅጥር ቀመርን በመጠቀም 5C2 ን እናሰላለን ፡፡ ከዚያ ሞጁሉን ከእሴቱ በላይ ወሰደ።

ስሌት nCr% p

ቀረበ  

የሁለትዮሽ ኪሳራ ስሌት በተመለከተ ባለፈው ልጥፍ ውስጥ። እኛ ያደረግነው መጀመሪያ nCr ን ለመፍታት የሚያስፈልጉትን እሴቶች ተቆጥሯል ፡፡ እኛ እንጠቀም ነበር ተለዋዋጭ ፕሮግራም ችግሩን ለመፍታት ግን ከዚያ የ nCr ዋጋን ብቻ እናሰላ ነበር ፡፡ የሁለትዮሽ ቅንጅት ሞዱሎ አይደለም የተወሰነ ቁጥር p. የዋህነት አካሄድ በመጀመሪያ የሁለተኛ ደረጃን መጠን ማስላት እና ከዚያ ሞዱሎ ፒን መውሰድ ይሆናል ፡፡ ግን በዚህ ስሌት ላይ ውስንነት አለ ፡፡ የተትረፈረፈ ፍሰት ስለሚያስገኝ ለብዙ ቁጥሮች የቢኖሚያል ብዛትዎችን ማስላት አይችሉም። ስለዚህ ወደ ኢንቲጀር ፍሰት ፍሰት ሳይገቡ ትክክለኛውን ውጤት ማምጣት የሚችል መንገድ መፈለግ አለብን ፡፡

እኛ ማድረግ የምንችለው አንድ ነገር ቢኖሚየል ቁጥራችን በሚሰላበት ጊዜ ሞዱል መውሰድን መቀጠል ነው። ስለዚህ የቀድሞው ልጥፍ መፍትሔ ብቸኛው የለውጥ ቅፅ በስሌቶቹ ወቅት ሞጁሉን እንወስዳለን ፡፡ ስለዚህ የእኛ ተደጋጋሚ ቀመር ትንሽ ይቀየራል ፣ ግን ሽግግሮቹ ተመሳሳይ ናቸው። እና አሁን ያለው የሁለትዮሽ ቅንጅት ቀደም ሲል እንደነበረው በተመሳሳይ ግዛቶች ላይ ጥገኛ ነው ፡፡

ተመልከት
ረጅሙ እየጨመረ የመጣ ተከታታይ ውጤት

ኮድ  

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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (N * R)፣ ኤን እና አር የተሰጡት ግብዓቶች የት ናቸው ፡፡ ምክንያቱም የእኛን ቢኖሚያል Coefficient በምንሰላበት ጊዜ የውጭ ዑደት እና አንድ የውስጥ ዑደት ነበረን ፡፡

ተመልከት
ሁለት ዛፎች ተመሳሳይ ከሆኑ ለመለየት ኮድ ይጻፉ

የቦታ ውስብስብነት

ኦ (አር)የመካከለኛ እሴቶችን ለማከማቸት አንድ ድርድር ስላደረግን እና ስለዚህ የቦታ ውስብስብነት መስመራዊ ነው።