深入理解卡特蘭數(shù)及其應(yīng)用

遞推關(guān)系:
它也滿(mǎn)足
這提供了一個(gè)更快速的方法來(lái)計(jì)算卡塔蘭數(shù)。
卡特蘭數(shù)的應(yīng)用n個(gè)元素順序入棧,出棧順序有多少種?此問(wèn)題是一個(gè)卡特蘭數(shù)問(wèn)題,證明過(guò)程如下:
令1表示進(jìn)棧,0表示出棧,則可轉(zhuǎn)化為求一個(gè)2n位、含n個(gè)1、n個(gè)0的二進(jìn)制數(shù),滿(mǎn)足從左往右掃描到任意一位時(shí),經(jīng)過(guò)的0數(shù)不多于1數(shù)。顯然含n個(gè)1、n個(gè)0的2n位二進(jìn)制數(shù)共有個(gè),下面考慮不滿(mǎn)足要求的數(shù)目。
考慮一個(gè)含n個(gè)1、n個(gè)0的2n位二進(jìn)制數(shù),掃描到第2m+1位上時(shí)有m+1個(gè)0和m個(gè)1(容易證明一定存在這樣的情況),則后面的0-1排列中必有n-m個(gè)1和n-m-1個(gè)0。將2m+2及其以后的部分0變成1、1變成0,則對(duì)應(yīng)一個(gè)n+1個(gè)0和n-1個(gè)1的二進(jìn)制數(shù)。
反過(guò)來(lái),任何一個(gè)由n+1個(gè)0和n-1個(gè)1組成的2n位二進(jìn)制數(shù),由于0的個(gè)數(shù)多2個(gè),2n為偶數(shù),故必在某一個(gè)奇數(shù)位上出現(xiàn)0的累計(jì)數(shù)超過(guò)1的累計(jì)數(shù)。同樣在后面部分0和1互換,使之成為由n個(gè)0和n個(gè)1組成的2n位數(shù),即n+1個(gè)0和n-1個(gè)1組成的2n位數(shù)必對(duì)應(yīng)一個(gè)不符合要求的數(shù)。
因而不合要求的2n位數(shù)與n+1個(gè)0,n-1個(gè)1組成的排列一一對(duì)應(yīng)。 顯然,不符合要求的方案數(shù)為c(2n,n+1)。
從而。證畢。
1、一個(gè)棧(無(wú)窮大)的進(jìn)棧序列為1,2,3,..n,有多少個(gè)不同的出棧序列?
2、有2n個(gè)人排成一行進(jìn)入劇場(chǎng)。入場(chǎng)費(fèi)5元。其中只有n個(gè)人有一張5元鈔票,另外n人只有10元鈔票,劇院無(wú)其它鈔票,問(wèn)有多少中方法使得只要有10元的人買(mǎi)票,售票處就有5元的鈔票找零?(將持5元者到達(dá)視作將5元入棧,持10元者到達(dá)視作使棧中某5元出棧)。
將多邊行劃分為三角形問(wèn)題
1、將一個(gè)凸多邊形區(qū)域分成三角形區(qū)域的方法數(shù)?
2、一位大城市的律師在她住所以北n個(gè)街區(qū)和以東n個(gè)街區(qū)處工作。每天她走2n個(gè)街區(qū)去上班。如果她從不穿越(但可以碰到)從家到辦公室的對(duì)角線,那么有多少條可能的道路?
3、在圓上選擇2n個(gè)點(diǎn),將這些點(diǎn)成對(duì)連接起來(lái)使得所得到的n條線段不相交的方法數(shù)? 給頂節(jié)點(diǎn)組成二叉樹(shù)的問(wèn)題 給定N個(gè)節(jié)點(diǎn),能構(gòu)成多少種不同的二叉樹(shù)?
1、16個(gè)人按順序去買(mǎi)燒餅,其中8個(gè)人每人身上只有一張5塊錢(qián),另外8個(gè)人每人身上只有一張10塊錢(qián)。燒餅5塊一個(gè),開(kāi)始時(shí)燒餅店老板身上沒(méi)有錢(qián)。16個(gè)顧客互相不通氣,每人只買(mǎi)一個(gè)。問(wèn)這16個(gè)人共有多少種排列方法能避免找不開(kāi)錢(qián)的情況出現(xiàn)。
h(8)=16!/(8!*9!)=1430,所以總數(shù)=h(8)*8!*8!=16!/9
2、在圖書(shū)館一共6個(gè)人在排隊(duì),3個(gè)還《面試寶典》一書(shū),3個(gè)在借《面試寶典》一書(shū),圖書(shū)館此時(shí)沒(méi)有了面試寶典了,求他們排隊(duì)的總數(shù)?
h(3)=6!/(3!*4!)=5,所以總數(shù)=h(3)*3!*3!=180
相關(guān)文章
C++?中如何結(jié)束?while?(cin>>str)?的輸入
這篇文章主要介紹了C++?中如何結(jié)束?while?(cin>>str)?的輸入,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-07-07C++ 賦值構(gòu)造函數(shù)注意點(diǎn)介紹
下面小編就為大家?guī)?lái)一篇C++ 賦值構(gòu)造函數(shù)注意點(diǎn)介紹。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-12-12Qt QFtp客戶(hù)端實(shí)現(xiàn)上傳下載文件
本文主要介紹了Qt QFtp客戶(hù)端實(shí)現(xiàn)上傳下載文件,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07C++深入學(xué)習(xí)之徹底理清重載函數(shù)匹配
C++ 不允許變量重名,但是允許多個(gè)函數(shù)取相同的名字,只要參數(shù)表不同即可,這叫作函數(shù)的重載,下面這篇文章主要給大家介紹了關(guān)于C++深入學(xué)習(xí)之徹底理清重載函數(shù)匹配的相關(guān)資料,需要的朋友可以參考下2019-01-01Protocol Buffer技術(shù)深入理解(C++實(shí)例)
C++實(shí)例Protocol Buffer技術(shù)詳解,感興趣的朋友可以了解下2013-01-01C語(yǔ)言實(shí)現(xiàn)旅游景點(diǎn)咨詢(xún)系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)旅游景點(diǎn)咨詢(xún)系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-12-12C語(yǔ)言 函數(shù)指針(指向函數(shù)的指針)詳解
本文主要介紹 C語(yǔ)言函數(shù)指針的知識(shí),這里整理了詳細(xì)的資料及示例代碼以便大家學(xué)習(xí)參考,有需要學(xué)習(xí)此部分知識(shí)的朋友可以參考下2016-08-08