nCr٪ p را محاسبه کنید  


سطح دشواری ساده
اغلب در Accenture کادنس هند رسانه کوملی کابین های اولا مربع
برنامه نویسی پویا ریاضی

بیان مسأله  

مسئله "محاسبه nCr٪ p" بیان می کند که شما باید ضریب دوجمله ای p p را پیدا کنید. بنابراین ابتدا باید در مورد ضریب دوجمله ای بدانید. ما قبلاً در پست قبلی بحث کردیم. می توانید آن را بررسی کنید اینجا کلیک نمایید.

مثال  

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

توضیح

nCr = 5C2 = 10
nCr٪ p = 10٪ 6 = 4
بنابراین ، ما 5C2 را با استفاده از فرمول ضریب دوجمله ای محاسبه کردیم. سپس مدول را روی مقدار قرار داد.

nCr٪ p را محاسبه کنید

روش  

در پست قبلی در مورد محاسبه ضریب دوجمله ای. کاری که ما انجام دادیم ابتدا محاسبه مقادیری بود که برای حل nCr مورد نیاز بود. ما با استفاده از برنامه نویسی پویا برای حل این مسئله اما ما فقط در حال محاسبه مقدار nCr بودیم. نه ضریب دوجمله ای مدول بعضی از عدد p. رویکرد ساده لوحانه این است که ابتدا ضریب دو جمله ای را محاسبه کرده و سپس مدول p را در نظر بگیرید. اما این محاسبه محدودیتی دارد. شما نمی توانید ضرایب Binomial را برای تعداد زیاد محاسبه کنید زیرا این امر منجر به سرریز شدن می شود. بنابراین ما باید راهی پیدا کنیم که بتواند بدون وارد شدن به سرریز عدد صحیح ، نتیجه صحیحی ایجاد کند.

یک چیز که می توانیم انجام دهیم این است که مدول را در هنگام محاسبه ضریب دوجمله ای خود ادامه دهیم. بنابراین تنها تغییری که در راه حل پست قبلی وجود دارد این است که ما در هنگام محاسبات مدول خواهیم گرفت. بنابراین فرمول بازگشتی ما کمی تغییر می کند ، اما تغییرات ثابت باقی می مانند. و ضریب دوجمله ای فعلی به همان حالت های قبلی وابسته است.

همچنین مشاهده کنید
طولانی ترین عواقب متوالی

رمز  

کد ++ 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 ورودی های داده شده هستند. این بدان دلیل است که وقتی ما در حال محاسبه ضریب Binomial خود بودیم ، یک حلقه بیرونی و یک حلقه داخلی داشتیم.

همچنین مشاهده کنید
برای تعیین یکسان بودن دو درخت کد را بنویسید

پیچیدگی فضا

یا)، از آنجا که ما یک آرایه برای ذخیره مقادیر میانی ایجاد کردیم ، بنابراین پیچیدگی فضا خطی است.