순열 계수-TutorialCup

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

Twitter Facebook 링크드인 버퍼 레딧 텀블러

차례

문제 정책

이 문제 "순열 계수"에서 우리는 n & k 값이 주어 졌을 때 그것을 찾아야합니다.

예

n = 5, k = 2

설명 :이 값은 n P r 순열 계수의 공식을 사용하여 구합니다. nPr = n! / (nr)!

순열 계수를 찾는 방법

순열 계수에 대해 알아보기. 우리는 알고 있어야합니다 순열, 그것은 1에서 n까지의 임의의 숫자 시퀀스에 불과합니다. 이제 우리는 순열이 무엇인지 압니다. 그러나 순열 계수는 무엇입니까?

주문하는 방법은 다양합니다. r 밖으로 물건 n 다른 것들. 이것이 의미하는 바를 단순화하기 위해? 이것은 우리가 n 다른 요소를 선택한 다음 r 요소를 재배치하는 방법을 찾아야합니다. nPr은 모든 작업 방식을 나타냅니다. 예를 들어, 3P2는 2 개의 다른 요소 집합에서 선택한 3 개의 요소를 재배 열하는 방법을 나타냅니다.

$순열 계수$

순열 계수는 먼저 n 개 요소 중 r 개 요소를 선택하므로 쉽게 이해할 수 있습니다. 그래서 nCr 그런 다음 r 요소를 재정렬합니다. 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

순열 계수를 얻기위한 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

복잡성 분석

시간 복잡성

O (N ^ 2 + Q), 순열 계수를 찾으려면 먼저 필요한 답을 계산하는 데 필요한 모든 순열 계수를 미리 계산해야합니다. 따라서 시간 복잡도는 다항식입니다. 여기에서 모든 쿼리는 O (1)에서 답할 수 있습니다.

공간 복잡성

O (N ^ 2), 미리 계산 된 결과를 저장하기 위해 2D 배열을 사용했기 때문입니다.

순열 계수를위한 최적화 된 접근 방식

순열 계수는 n에서 n-k + 1까지 숫자의 곱에 불과하기 때문입니다. 우리는 간단히 nPk를 계산할 수 있습니다. O (1) 공간 및 O (N) 시간.

암호

최적화 된 접근 방식을위한 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

최적화 된 접근 방식을위한 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

Twitter Facebook 링크드인 버퍼 레딧 텀블러