第N加泰羅尼亞語編號


難度級別
經常問 亞馬遜
動態編程 數學

在第N個加泰羅尼亞數字問題中,我們給出了整數n。 查找前n個加泰羅尼亞語數字。 加泰羅尼亞語數字是一系列正整數,在許多計數問題中都可以看到。

它們用來計數–

  • 具有n鍵的BST(二進制搜索樹)。
  • 某些類型的晶格路徑。
  • 排列

還有更多這樣的問題。 加泰羅尼亞語數字的遞歸公式為–

C0 = 0和Cn + 1 = Σ Ci C對於n> = 0和n => i> = 0。

加泰羅尼亞語數字系列的前幾個數字-分別為n = 1、1、2、5、14……的0、1、2、3、4……。 

輸入: n=2

輸出: 1 1th Street, Suite XNUMX

輸入: n=9

輸出: 1 1 2 5 14 42 132 429 1430

第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

Java程序

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

Java程序

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

Java程序

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

參考