卡特兰数 |
您所在的位置：网站首页 › 卡特兰数如何理解 › 卡特兰数 |
|
卡特兰数（Catalan numbers）是组合数学中的一种数列，以比利时数学家Eugène Charles Catalan的名字命名。卡特兰数出现在各种计数问题中，通常涉及括号的组合，路径计数，树结构等。 卡特兰数序列的前几项如下： C(0) = 1 C(1) = 1 C(2) = 2 C(3) = 5 C(4) = 14 C(5) = 42 C(6) = 132 C(7) = 429 C(8) = 1430 C(9) = 4862卡特兰数在计数问题中的应用非常广泛，例如： 括号表达式：卡特兰数用于计算合法的括号表达式的数量。例如，n对括号可以组成多少个合法的括号表达式。 二叉树：卡特兰数用于计算不同的二叉搜索树的数量，其中n个不同的节点按特定的顺序插入。 路径计数：在网格上从左上角到右下角的合法路径数量。 凸多边形三角形的数量：卡特兰数用于计算n边凸多边形的不同三角形数量。这些只是卡特兰数应用的一部分。它们在组合数学中扮演着重要的角色，帮助解决各种计数和排列问题。 public class Catalan{ public static void main(String[] args) { System.out.println(catalan(3)); } static int catalan(int n) { int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for (int j = 2; j < n + 1; j++) { for (int i = 0; i < j; i++) { //第j个卡特兰数的拆分 System.out.printf("(%d,%d)\t", i, j - 1 - i); dp[j] += dp[i]*dp[j-1-i]; } // System.out.println(Arrays.toString(dp)); } return dp[n]; } } |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |