NCr% p есептеу


Күрделілік дәрежесі оңай
Жиі кіреді Accenture Cadence Үндістан Komli Media Ola Cabs шаршы
Динамикалық бағдарламалау математика

Проблемалық мәлімдеме

«Compute nCr% p» есептерінде p модулінің биномдық коэффициентін табу қажет екендігі айтылған. Сондықтан сіз биномдық коэффициент туралы алдымен білуіңіз керек. Біз бұны алдыңғы жазбада талқыладық. Сіз мұны тексере аласыз Мұнда.

мысал

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

Түсіндіру

nCr = 5C2 = 10
nCr% p = 10% 6 = 4
Сонымен, биномдық коэффициенттің формуласын пайдаланып 5C2-ді есептедік. Содан кейін модульді мәннен асырып алды.

NCr% p есептеу

жақындау

Биномдық коэффициентті есептеуге қатысты алдыңғы жазбада. Біз не істедік, алдымен nCr шешуге қажетті мәндерді есептедік. Біз қолдандық динамикалық бағдарламалау мәселені шешу үшін, бірақ біз тек nCr мәнін есептеп шығардық. Биномдық коэффициент емес, кейбір p саны. Алдымен биномдық коэффициентті есептеп, содан кейін 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 есептеуге арналған Java коды

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), өйткені біз аралық мәндерді сақтау үшін массив жасадық, осылайша кеңістіктің күрделілігі сызықтық болып табылады.