h(n)=c(2n-2,n-1)/n 是什么意思哈 C代表什么呀  回復  更多評論
  

順便說一下啊

你的瀏覽計數器太大了 影響頁面訪問和美觀 呵呵呵 隨便提個建議  回復  更多評論
  

@江水獸
c代表組合數,即2n-2個體種選取n-1個的種類  回復  更多評論
  

@江水獸
謝謝啊
不過字體設置到最小后,還是這么大,let it be  回復  更多評論
  

不過好像有些問題還不是那么好處理呵

例如“有2n個人排成一行進入劇場。入場費5元。其中只有n個人有一張5元鈔票，另外n人只有10元鈔票，劇院無其它鈔票，問有多少中方法使得只要有10元的人買票，售票處就有5元的鈔票找零？(將持5元者到達視作將5元入棧，持10元者到達視作使棧中某5元出棧)”這個問題；

到底該如何利用類推法呢？

假如用f(x)來表示x個人時的情況，
那么一個人時f(1)=1;
兩個人時f(2)=2f(1)+1;
三個人時f(3)=3f(1)+f(2)f(1)+f(1)f(2);
四個人時f(4)=4f(1)+2f(3)f(1)+f(2)f(2)+f(1)f(2)f(1);
……
這樣貌似還是有點不好處理呀……  回復  更多評論
  

@江水獸
你是說這么遞歸解這一堆遞歸式吧.
大可不必,
我們只需要發現一個問題滿足catalan數列的遞歸式,然后直接就可以得到解
f(n)=h(n)=c(2n-2,n-1)/n
有時候還要看具體問題,可能最終的解是h(n+1)或h(n-1)或h(2n)等等  回復  更多評論
  

@pengkuny
好像有道理喲 我再看看！  回復  更多評論
  

應該是C(n)種吧
C(n)=(2n)!/[n!*(n+1)!]  回復  更多評論
  

應該是C(n)種吧
C(n)=(2n)!/[n!*(n+1)!]  回復  更多評論
  

我想知道catalan數是怎樣推導出來的呀
怎樣用于算法的分析呀  回復  更多評論
  

ding~~
好文啊,這幾個都很典型!  回復  更多評論
  

對于每一個數來說，必須進棧一次、出棧一次。我們把進棧設為狀態‘1’，出棧設為狀態‘0’。n個數的所有狀態對應n個1和n個0組成的2n位二進制數。由于等待入棧的操作數按照1‥n的順序排列、入棧的操作數b大于等于出棧的操作數a(a≤b)，因此輸出序列的總數目=由左而右掃描由n個1和n個0組成的2n位二進制數，1的累計數不小于0的累計數的方案種數。
在2n位二進制數中填入n個1的方案數為c(2n,n),不填1的其余n位自動填0。從中減去不符合要求（由左而右掃描，0的累計數大于1的累計數）的方案數即為所求。

不符合要求的數的特征是由左而右掃描時，必然在某一奇數位2m+1位上首先出現m+1個0的累計數和m個1的累計數，此后的2（n-m）-1位上有n-m個1和n-m-1個0。如若把后面這2（n-m）-1位上的0和1互換，使之成為n-m個0和n-m-1個1，結果得1個由n+1個0和n-1個1組成的2n位數，即一個不合要求的數對應于一個由n+1個0和n-1個1組成的排列。
反過來，任何一個由n+1個0和n-1個1組成的2n位二進制數，由于0的個數多2個，2n為偶數，故必在某一個奇數位上出現0的累計數超過1的累計數。同樣在后面部分0和1互換，使之成為由n個0和n個1組成的2n位數，即n+1個0和n-1個1組成的2n位數必對應一個不符合要求的數。顯然，不符合要求的方案數為c(2n,n+1)。由此得出
輸出序列的總數目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)。


(form 日照NOIP夏令營,by 王建德老師)  回復  更多評論
  

問題條件MS都不太清楚，可不可以說明白一點？

比如
3.將多邊行劃分為三角形問題。
將一個凸多邊形區域分成三角形區域的方法數?

劃分線是否可以相交？如果不可以相交那結果應該是catalan數，如果可以相交那就得另當別論了。

再問一句，為什么c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)？  回復  更多評論
  

輸出前n個catalan數：
program jk;
const maxn=1000;
type arraytype=array[0..maxn] of longint;
var i,j,n:longint;

procedure mul(var h:arraytype;k:longint);
var i:longint;
begin
for i:=0 to maxn do h[i]:=h[i]*k;
for i:=0 to maxn-1 do
begin
h[i+1]:=h[i+1]+h[i] div 10;
h[i]:=h[i] mod 10
end
end;

procedure devide(var h:arraytype;k:longint);
var d,i,r:longint;
begin
r:=0;
for i:=maxn downto 0 do
begin
d:=10*r+h[i];
h[i]:=d div k;
r:=d mod k
end
end;
procedure cat(n:integer);
var i,j:integer;
h:arraytype;
begin
for i:=1 to maxn do h[i]:=0;
h[0]:=1;
for i:=3 to n-1 do
begin
mul(h,4*i-6);
devide(h,i)
end;
i:=maxn;
while (i>0) and (h[i]=0) do i:=i-1;
for j:=i downto 0 do write(h[j]);
writeln;
end;

begin
assign(input,'input.dat');reset(input);
assign(output,'output.dat');rewrite(output);
readln(n);
n:=n+2;
for i:=1 to n do cat(i);
close(input);close(output);
end.
  回復  更多評論
  

對于有n個節點可構成幾棵不同形態的二叉樹,可以這么考慮:
因為只有一個根節點,而且二叉樹只有左孩子或右孩子,所以可知:
當左孩子有0個節點時,右孩子有n-1個節點,可構成的不同形態二叉樹的數目為:
h(0)*h(n-1)
當左孩子有1個節點時,右孩子有n-2個節點,可構成的不同形態二叉樹的數目為:
h(1)*h(n-2)
當左孩子有2個節點時,右孩子有n-3個節點,可構成的不同形態二叉樹的數目為:
h(2)*h(n-3)
依次類推:
可知共有不同形態二叉樹的數目為:
h(0)*h(n-1)+h(1)*h(n-2)+h(2)*h(n-3)...+h(n-1)*h(0)
注:h(0)=1,h(1)=1,h(2)=2 h(3)=5  回復  更多評論
  

內容有錯誤，別人又來復制，導致錯誤的事情擴大，可悲。。。  回復  更多評論