د پام کولو کوفی


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي د بانک بازار Xome
متحرک برنامې ریاضی پرمټ ورکول

ستونزه بیان

پدې ستونزه کې د "پرمټیوشن کوفيفیت" کې ، موږ اړتیا لرو چې دا ومومو کله چې موږ ته د N & K ارزښت راکړل شو.

بېلګه

n = 5, k = 2
20

توضیحي: د دې ارزښت ن P ر د اجازه لیک ضرب الاضله په کارولو سره موندل شوی. nPr = n! / (NR)!

د پرمټیوشن کوفيف موندلو لپاره تګلاره

د پرمټیوشن کوفيف په اړه پوهیدلو لپاره. موږ باید خبرتیا ولرو پرمټ ورکول، دا د 1 څخه تر n پورې د هرې بې ترتیب ترتیب څخه پرته بل څه ندي. نو ، اوس موږ پوهیږو چې پرمټشن څه شی دی. مګر د جواز ضرب الاجل څه شی دی؟

دا د ترتیب کولو ډیری لارو پرته بل څه ندي r شیان بهر مختلف شیان. نو ، ساده کولو لپاره دا څه معنی لري؟ دا پدې مانا ده چې موږ یو څه درلودل مختلف عنصرونه او بیا موږ یو څه غوره کوو د دې څخه عناصر او اوس موږ اړتیا لرو د دوی د تنظیم کولو لارې ومومئ. nPr د کولو ټولې لارې په ګوته کوي. د مثال په توګه ، 3P2 د 2 بیلابیلو عناصرو له سیټ څخه غوره شوي 3 عناصرو د تنظیم لپاره لارې توضیح کوي.

د پام کولو کوفی

د پرمټیوشن کوفیف هم په اسانۍ سره پیژندل کیدی شي لکه څنګه چې موږ لومړی د n عناصرو څخه r عناصر غوره کوو. نو داسې ده nCr بیا موږ د آر عناصر تنظیم کوو ، نو nPr = nCr * r! .

د پرمټیوشن کوفیف نسل تولید لپاره تکراري فورمول

P(n, k) = P(n-1, k) + k*P(n-1, k-1)

موږ په کارولو سره اړین ځواب موندلی شو متحرک برنامې د تکراري فارمول لپاره چې دا په موثره توګه محاسبه کړئ.

کوډ

د پرمټیوشن کوفيف ترلاسه کولو لپاره C ++ کوډ

#include<bits/stdc++.h>
using namespace std;

int P[51][51];

//precomputePermutationCoefficient
void precomputePermutationCoefficients()
{

  for (int i = 0; i <= 50; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      // Base Cases
      if (j == 0)
        P[i][j] = 1;
      else
        P[i][j] = P[i - 1][j] + j * P[i - 1][j - 1]; // use recursive formula
    }
  }
}

int main()
{
  // precomputations being done for n = 50, you can change the value of n
  precomputePermutationCoefficients();
  int noOfQueries;cin>>noOfQueries;
  while(noOfQueries--){
    // here n & k do not satisfy the properties of permutation coefficient
    // then we will answer it as 0
    int n,k;cin>>n>>k;
    if(n<=50 && k<=50)
      cout<<P[n][k]<<endl;
    else
      cout<<0<<endl;
  }
}
1
5 2
20

د جایزی کوډ د پرمټیوشن کوفیف ترلاسه کولو لپاره

import java.util.*;

class Main{
  static int P[][];

  // precompute permutation coefficient
  static void precomputePermutationCoefficients() 
  {

    for (int i = 0; i <= 50; i++) 
    { 
      for (int j = 0; j <= i; j++) 
      { 
        // Base Cases 
        if (j == 0) 
          P[i][j] = 1; 
        else
          P[i][j] = P[i - 1][j] + j * P[i - 1][j - 1]; // use recursive formula
      } 
    }	
  } 

  public static void main(String[] args)
  {
    P = new int[51][51];
    // precomputations being done for n = 50, you can change the value of n
    precomputePermutationCoefficients();
    Scanner sc = new Scanner(System.in);
    int noOfQueries;
    noOfQueries = sc.nextInt();
    while(noOfQueries-- > 0){
      // here n & k do not satisfy the properties of permutation coefficient
      // then we will answer it as 0
      int n = sc.nextInt();
      int k = sc.nextInt();
      if(n<=50 && k<=50)
        System.out.println(P[n][k]);		
      else
        System.out.println(0);
    }
  }
}
1
5 2
20

د پیچلتیا تحلیل

د وخت پیچلتیا

O (N ^ 2 + Q) ، ځکه چې زموږ د لیږدوالی کیفیت موندلو لپاره لومړی موږ اړتیا لرو ټول د رخصتیو کوفیفینټونه تحلیل کړو کوم چې د مطلوب ځواب محاسبې لپاره اړین دي. په دې توګه د وخت پیچلتیا ډیری ده. دلته ټولې پوښتنې په O (1) کې ځواب کیدی شي.

د ځای پیچلتیا

O (N ^ 2) ، ځکه چې موږ د احتمالي پایلې ذخیره کولو لپاره د 2D سرې کارولې.

د مطلق تکفیریت لپاره مطلوب کړنلاره

له هغه وخته چې د تقلید کوونکی کافی له N څخه n-k + 1 ته د شمیر ضرب الاجل پرته بل څه ندی. موږ کولی شو په ساده ډول په NPk کې محاسبه کړو O (1) ځای او پر وخت.

کوډ

د مطلوب لید لپاره C ++ کوډ
#include<bits/stdc++.h>
using namespace std;

int main(){
  int n,k;cin>>n>>k;
  int P = 1;
  for(int i=n;i>=(n-k+1);i--)
    P*=i;
  cout<<P<<endl;
}
5 2
20
د مطلوب لید لپاره جاوا کوډ
import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int P = 1;
    for(int i=n;i>=(n-k+1);i--)
      P*=i;
    System.out.println(P);
  }
}
5 2
20