Каэфіцыент перастаноўкі


Узровень складанасці серада
Часта пытаюцца ў БанкБазар Xome
Дынамічнае праграмаванне Матэматыка Перастаноўка

Пастаноўка праблемы

У гэтай задачы «Каэфіцыент перастаноўкі» нам трэба знайсці яе, калі нам дадуць значэнні n & k.

Прыклад

n = 5, k = 2
20

Тлумачэнне: Гэта значэнне NPR знаходзіць з выкарыстаннем формулы каэфіцыента перастаноўкі. nPr = n! / (nr)!

Падыход да пошуку каэфіцыента перастаноўкі

Каб даведацца пра каэфіцыент перастаноўкі. Мы павінны ведаць пра гэта Перастаноўка, гэта не што іншае, як любая выпадковая паслядоўнасць лікаў ад 1 да n. Такім чынам, цяпер мы ведаем, што такое Перастаноўка. Але што такое каэфіцыент перастаноўкі?

Гэта не што іншае, як некалькі спосабаў замовы r рэчы з розныя рэчы. Такім чынам, спрасціць, што гэта значыць? Гэта азначае, што ў нас іх было розныя элементы, а потым мы выбіраем некаторыя элементы з яго, і цяпер нам трэба знайсці спосабы іх перабудовы. nPr абазначае ўсе спосабы выканання. Напрыклад, 3P2 абазначае спосабы перастаноўкі 2 элементаў, выбраных з набору з 3 розных элементаў.

Каэфіцыент перастаноўкі

Каэфіцыент перастаноўкі таксама можна лёгка зразумець, бо спачатку мы выбіраем r элементаў з n элементаў. Такім чынам, гэта так 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

Код Java для атрымання каэфіцыента перастаноўкі

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 у Аб (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
Код Java для аптымізаванага падыходу
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