اجازت نامو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ بينڪ بازار Xome
متحرڪ پروگرامنگ Math اجازت نامو

مسئلي جو بيان

انهي مسئلي ۾ ”اجازت نامو ڪوآرينيشن“ ، اسان کي اهو ڳولڻ جي ضرورت آهي جڏهن اسان کي ن ۽ ڪ جي قيمت ڏني ويندي آهي.

مثال

n = 5, k = 2
20

وضاحت: انهي جو قدر اين پي آر تعيناتي گنجائش جي فارمولا استعمال ڪندي مليو آهي. nPr = n! / (اين آر)!

اجازت نامو وڌائڻ وارو طريقو ڳولڻ

Permutation Coefficient بابت اڻ حاصل ڪرڻ لاءِ. اسان کي خبردار رھڻ گھرجي اجازت نامو، اهو ڪجهه نه آهي پر 1 کان نا تائين انگن جي بي ترتيب ترتيب. تنهن ڪري ، هاڻي اسان knowاڻون ٿا Permutation ڇا آهي. پر اجازت نامو ڇا آهي؟

اهو ڪجهه نه آهي پر حڪم ڪرڻ جا ڪيترائي طريقا r مان شيون مختلف شيون. تنهن ڪري ، انهي کي آسان بڻائڻ لاءِ ڇا مطلب آهي؟ انهي جو مطلب آهي ته اسان وٽ ڪجهه هئا مختلف عنصر ۽ پوءِ اسان ڪجهه چونڊيندا آهيون عناصر ان کان ۽ ھاڻي اسان کي انھن کي ترتيب ڏيڻ جا طريقا ڳولڻ جي ضرورت آھي. nPr ڪم ڪرڻ جي سڀني طريقن کي رد ڪري ٿي. مثال طور ، 3P2 2 مختلف عنصرن جي سيٽ مان چونڊيل 3 عنصرن کي ٻيهر ترتيب ڏيڻ جي طريقن کي ظاهر ڪري ٿو.

اجازت نامو

اجازت واري گنجائش پڻ آساني سان سمجهي سگھجي ٿي جئين پهرين اسان آر عنصرن مان نڪتا آهيون. تنهنڪري اهو آهي اين سي آر پوءِ اسان آر عنصرن کي ترتيب ڏينداسين nPr = nCr * ر! .

تعميري فارمولا Permutation Coefficient جي نسل لاءِ

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

اسان استعمال ڪندي گهربل جواب ڳولي سگھون ٿا متحرڪ پروگرامنگ recursive فارمولا لاءِ ته ان کي موثر طريقي سان شمار ڪرڻ.

ڪوڊ

سي ++ ڪوڊ permutation cofficient حاصل ڪرڻ لاءِ

#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

جاوا ڪوڊ Permutation Coefficient حاصل ڪرڻ لاءِ

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

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

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

اي (اين ^ 2 + ق) ، ڇاڪاڻ ته اسان جي اجازتن جي گنجائش ڳولهڻ لاءِ سڀ کان پهرين ضرورتن جو حساب لڳائڻ جي ضرورت آهي جيڪي گهربل جواب جي حساب سان لازمي آهن. ان ڪري وقت جي پيچيدگي پولينومل آهي. هتي سڀ سوالن جو جواب او (1) ۾ ڏئي سگهجي ٿو.

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

اي (اين ^ 2) ، ڇاڪاڻ ته اسان انهي نتيجي واري نتيجن کي اسٽور ڪرڻ لاءِ 2D صف استعمال ڪئي آهي.

اجازت نامي جي اصلاح لاءِ اصلاح جي جستجو

جيئن ته اجازت ڏيڻ واري گنجائش ڪجهه ناهي سواءِ نمبرن کان n-k + 1 جي انگ. اسان صرف اين پي ڪي جو حساب لڳائي سگهون ٿا اي (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