資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究Golang 中的第 N 個卡特蘭數
卡特蘭數是表示 n 個值所有可能的二叉查詢樹 (BST) 個數的自然數序列。因此，卡特蘭數是一種有 n+1 片樹葉的完全二叉樹。
卡特蘭數的一些應用包括計算巢狀括號對、有效山脈範圍等。
對於 n = 5，C = (C(0) * C(4)) + (C(1) * C(3)) + (C(2) * C(2)) + (C(3) * C(1)) + (C(4)* C(0))
因此，我們可以看到卡特蘭數呈遞迴關係形式，即對於第 n 項，卡特蘭數 Cn 為，
卡特蘭 (i) * 卡特蘭 (n-i-1) 的總和
其中 i 的範圍為 0 到 (n -1)。
例如，列印 N = 5 的卡特蘭數，
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ........
上述序列中的第 5 項為 14，因此我們將第 5 個卡特蘭數的輸出列印為“14”。
卡特蘭數的實施
下面給出的程式碼是第 n 個卡特蘭數的實施 −
示例
package main
import "fmt"
func main() {
var n =5
fmt.Scanf("%d", &n)
Catalan := make([]int, n + 1)
Catalan[0] = 1
Catalan[1] = 1
for i := 2; i <= n; i++ {
for j := 0; j < i; j++ {
Catalan[i] += (Catalan[j] * Catalan[i - j - 1])
}
}
fmt.Printf("The Catalan Number (Cn) is: %d", Catalan[n - 1])
}輸出
執行上述程式碼將生成 n = 5 的卡特蘭數，
14
更新於：2021 年 2 月 5 日
瀏覽量 179
廣告