N 번째 카탈로니아 숫자

난이도 중급
자주 묻는 질문 아마존
동적 프로그래밍 수학조회수 111

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

N 번째 카탈로니아 수 문제에서 정수 n을 지정했습니다. 처음 n 개의 카탈루냐 숫자를 찾으십시오. 카탈루냐 숫자는 많은 계산 문제에서 볼 수있는 일련의 양의 정수입니다.

계산하는 데 사용됩니다.

  • n 개의 키가있는 BST (이진 검색 트리).
  • 특정 유형의 격자 경로.
  • 순열

그리고 더 많은 그러한 문제. 카탈루냐 숫자의 재귀 공식은 –

C0 = 0 및 Cn + 1 = Σ Ci Cni n> = 0 및 n => i> = 0 인 경우.

카탈로니아 어 숫자 시리즈의 처음 몇 개의 숫자 – 각각 n = 1, 1, 2, 5, 14 …… 인 경우 0, 1, 2, 3, 4 …… 

입력 : n=2

출력 : 1 1

입력 : n=9

출력 : 1 1 2 5 14 42 132 429

N 번째 카탈 론 수에 대한 재귀 방법

암호알고리즘

  1. 초기화 a 변수 n.
  2. 기본 사례 – n이 1보다 작 으면 반환 1.
  3. 재귀 사례 – 1과 n (0 포함) 사이의 모든 i에 대해 모든 cat (i) x cat (ni-0)의 합계를 반환합니다.

시간 복잡성 : O (3n)

공간 복잡성 : O (1)

N 번째 카탈 론 번호 구현

C ++ 프로그램

#include<bits/stdc++.h> 
using namespace std; 
  
long int cat(int n){ 
    // Base case 
    if(n<=1) 
        return 1; 
  
    // cat(n)= sum of cat(i)*cat(n-i-1) 
    long int r = 0; 
    for (int i=0; i<n; i++) 
        r += cat(i)*cat(n-i-1); 
    return r; 
} 
  
int main(){
    int n=3;
    for (int i=0; i<n; i++) 
        cout<<cat(i)<< " "; 
    return 0; 
}
1 1 2

자바 프로그램

class Catalan{ 
    int cat(int n) { 
        int r = 0; 
          
        // Base case 
        if(n<=1) { 
            return 1; 
        } 
        // cat(n)= sum of cat(i)*cat(n-i-1)
        for(int i=0; i<n; i++) { 
            r+=cat(i)*cat(n-i-1); 
        } 
        return r; 
    } 
  
    public static void main(String[] args) { 
        Catalan c = new Catalan(); 
        int n=3;
        for (int i=0; i<n; i++) { 
            System.out.print(c.cat(i) + " "); 
        } 
    } 
}
1 1 2

N 번째 카탈루냐 숫자에 대한 동적 프로그래밍 방법

암호알고리즘

  1. 카탈루냐 숫자를 저장하려면 변수 n과 배열 c를 초기화합니다.
  2. 의 처음 두 요소를 초기화합니다. 정렬 각각 1과 1로.
  3. 2부터 하나씩 n까지 모든 값을 탐색하고 배열 값을 c [j] * c [ij-1]의 합으로 업데이트합니다.
  4. c [n]을 반환합니다.

시간 복잡성 : 의 위에2)

공간 복잡성 : O(n)

N 번째 카탈 론 번호 구현

C ++ 프로그램

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

long int cat(int n){ 
    
    long int c[n+1]; 
  
    // Initialisation of first two values 
    c[0]=1;
    c[1]=1; 
  
    for(int i=2; i<=n; i++){ 
        c[i] = 0; 
        for(int j=0; j<i; j++) 
            c[i] += c[j] * c[i-j-1]; 
    } 
  
    // Return last number in array
    return c[n]; 
} 
  
int main(){ 
    int n=3;
    for(int i=0; i<n; i++) 
        cout << cat(i) << " "; 
    return 0; 
}
1 1 2

자바 프로그램

class Catalan{ 
  
    static int cat(int n){ 
        int c[] = new int[n + 2]; 
  
         // Initialisation of first two values 
        c[0]=1;
        c[1]=1; 
      
        for(int i=2; i<=n; i++){ 
            c[i] = 0; 
            for(int j=0; j<i; j++) 
                c[i] += c[j] * c[i-j-1]; 
        } 
      
        // Return last number in array
        return c[n]; 
    } 
    public static void main(String[] args) { 
        int n=3;
        for(int i=0; i<n; i++){ 
            System.out.print(cat(i) + " "); 
        } 
    } 
}
1 1 2

이항 계수 사용

여기서는 공식을 직접 사용하여 n 번째 카탈로니아 숫자를 찾습니다.

Cn = ( ( 2n! ) / ((n + 1)! n!))

시간 복잡성 : O (N)

공간 복잡성 : O (1)

N 번째 카탈로니아 숫자 구현

C ++ 프로그램

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

long int biCoef(int n, int m){ 
    long int r=1; 
  
    if(m>(n-m)) 
        m=n-m; 

    for (int i=0; i<m; ++i){ 
        r *= (n-i); 
        r /= (i+1); 
    } 
  
    return r; 
} 

long int cat(int n){ 
    // Calculate value of 2nCn 
    long int c = biCoef(2*n, n); 
  
    // return 2nCn/(n+1) 
    return c/(n+1); 
} 
int main(){
    int n=3;
    for (int i=0; i<n; i++) 
        cout << cat(i) << " "; 
    return 0; 
}
1 1 2

자바 프로그램

class Catalan{ 
  
    static long biCoef(int n, int m){ 
        long r=1; 
      
        if(m>(n-m)) 
            m=n-m; 
    
        for (int i=0; i<m; ++i){ 
            r *= (n-i); 
            r /= (i+1); 
        } 
      
        return r; 
    } 
    
    static long cat(int n){ 
        // Calculate value of 2nCn 
        long c = biCoef(2*n, n); 
      
        // return 2nCn/(n+1) 
        return c/(n+1); 
    } 
    public static void main(String[] args) { 
        int n=3;
        for(int i=0; i<n; i++){ 
            System.out.print(cat(i) + " "); 
        } 
    } 
}
1 1 2

참조

균열 시스템 설계 인터뷰
Translate »