題意：

給你一個(gè)數(shù)n，表示有n輛火車，編號(hào)從1到n，入站，問(wèn)你有多少種出站的可能。??? (題于文末)

?

知識(shí)點(diǎn)：

??????????????????????????????????????????????????????????????????????????????????????? ps:百度百科的卡特蘭數(shù)講的不錯(cuò)，注意看其參考的博客。

卡特蘭數(shù)(Catalan)：前幾項(xiàng)為 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670…

??? 令h(0)=1,h(1)=1，catalan數(shù)滿足遞推式：

???? h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)

??? 另類遞推式：

???

??? 遞推關(guān)系的解為：

???

??? 遞推關(guān)系的另類解為：

??

?? 對(duì)于在2n位的2進(jìn)制中，有n個(gè)0，其余為1,且1的累計(jì)數(shù)>=0的累計(jì)數(shù)，二進(jìn)制數(shù)有種

?? 對(duì)于在n位的2進(jìn)制中，有m個(gè)0，其余為1的catalan數(shù)為：

??? 理解：catalan數(shù)的理解

??? 應(yīng)用：

??? 1.出棧次序： 一個(gè)棧(無(wú)窮大)的進(jìn)棧序列為1，2，3，…，n，有多少個(gè)不同的出棧序列?????????? h(n)種。

??? 2.給定節(jié)點(diǎn)組成二叉樹(shù)：給定n個(gè)節(jié)點(diǎn)，能構(gòu)成多少種不同的二叉樹(shù)？??? h(n)種。

??? 3.括號(hào)化：矩陣連乘，依據(jù)乘法結(jié)合律，不改變其順序，只用括號(hào)表示成對(duì)的乘積，有幾種括號(hào)化的方案？? h(n-1)種。

??? 4.凸多邊形三角劃分：在一個(gè)凸n邊形中，通過(guò)若干條互不相交的對(duì)角線，有多少種方法把這個(gè)多邊形劃分成若干個(gè)三角形？???????? h(n-2)種。

/**/???

?

題解：

此題為應(yīng)用1，運(yùn)用公式?? ?

catalan數(shù)計(jì)算一般都涉及大數(shù)運(yùn)算，java寫起來(lái)方便。

?

import java.util.Scanner; import java.math.BigInteger; import java.io.*;public class Main{public static void main(String[] args){int n;Scanner sc=new Scanner(System.in);while(sc.hasNext()){n=sc.nextInt();BigInteger ans=BigInteger.valueOf(1);for(int i=1;i<=n;i++){ans=ans.multiply(BigInteger.valueOf(4*i-2));ans=ans.divide(BigInteger.valueOf(i+1));}System.out.println(ans);}} }

?

?

?

?

?

Train Problem II

Time Limit:1000MS???? Memory Limit:32768KB???? 64bit IO Format:%I64d & %I64u

Submit Status

Description

As we all know the Train Problem I, the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order, how many orders that all the trains can get out of the railway.

Input

The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.

Output

For each test case, you should output how many ways that all the trains can get out of the railway.

Sample Input

1 2 3 10

Sample Output

1 2 5 16796

Hint

The result will be very large, so you may not process it by 32-bit integers.

轉(zhuǎn)載于:https://www.cnblogs.com/shentr/p/5349707.html

總結(jié)

以上是生活随笔為你收集整理的hdu1032 Train Problem II (卡特兰数)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。