欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2013年05月28日 17:49:23   作者:  
本篇文章是對卡特蘭數(shù)及其應(yīng)用進行了詳細的分析介紹,需要的朋友參考下
Catalan number,卡特蘭數(shù)又稱卡塔蘭數(shù),是組合數(shù)學(xué)中一個常出現(xiàn)在各種計數(shù)問題中出現(xiàn)的數(shù)列。以比利時的數(shù)學(xué)家歐仁·查理·卡塔蘭 (1814–1894)命名。
令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)
catalan數(shù)公式的一般是形式為:
                                                         C_n = \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{(n+1)!n!}

遞推關(guān)系:

C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\mbox{for }n\ge 0.

它也滿足

C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n, 
這提供了一個更快速的方法來計算卡塔蘭數(shù)。

卡特蘭數(shù)的應(yīng)用n個元素順序入棧,出棧順序有多少種?此問題是一個卡特蘭數(shù)問題,證明過程如下:

令1表示進棧,0表示出棧,則可轉(zhuǎn)化為求一個2n位、含n個1、n個0的二進制數(shù),滿足從左往右掃描到任意一位時,經(jīng)過的0數(shù)不多于1數(shù)。顯然含n個1、n個0的2n位二進制數(shù)共有{2n \choose n}個,下面考慮不滿足要求的數(shù)目。

考慮一個含n個1、n個0的2n位二進制數(shù),掃描到第2m+1位上時有m+1個0和m個1(容易證明一定存在這樣的情況),則后面的0-1排列中必有n-m個1和n-m-1個0。將2m+2及其以后的部分0變成1、1變成0,則對應(yīng)一個n+1個0和n-1個1的二進制數(shù)。

反過來,任何一個由n+1個0和n-1個1組成的2n位二進制數(shù),由于0的個數(shù)多2個,2n為偶數(shù),故必在某一個奇數(shù)位上出現(xiàn)0的累計數(shù)超過1的累計數(shù)。同樣在后面部分0和1互換,使之成為由n個0和n個1組成的2n位數(shù),即n+1個0和n-1個1組成的2n位數(shù)必對應(yīng)一個不符合要求的數(shù)。
因而不合要求的2n位數(shù)與n+1個0,n-1個1組成的排列一一對應(yīng)。 顯然,不符合要求的方案數(shù)為c(2n,n+1)。

從而C_n = {2n \choose n} - {2n \choose n + 1} = \frac{1}{n+1}{2n \choose n}。證畢。

括號化問題   如,矩陣鏈乘: P=a1×a2×a3×……×an,依據(jù)乘法結(jié)合律,不改變其順序,只用括號表示成對的乘積,試問有幾種括號化的方案?(h(n)種)

出棧次序問題  
1、一個棧(無窮大)的進棧序列為1,2,3,..n,有多少個不同的出棧序列?
2、有2n個人排成一行進入劇場。入場費5元。其中只有n個人有一張5元鈔票,另外n人只有10元鈔票,劇院無其它鈔票,問有多少中方法使得只要有10元的人買票,售票處就有5元的鈔票找零?(將持5元者到達視作將5元入棧,持10元者到達視作使棧中某5元出棧)。

將多邊行劃分為三角形問題  
1、將一個凸多邊形區(qū)域分成三角形區(qū)域的方法數(shù)?
2、一位大城市的律師在她住所以北n個街區(qū)和以東n個街區(qū)處工作。每天她走2n個街區(qū)去上班。如果她從不穿越(但可以碰到)從家到辦公室的對角線,那么有多少條可能的道路?
3、在圓上選擇2n個點,將這些點成對連接起來使得所得到的n條線段不相交的方法數(shù)?

給頂節(jié)點組成二叉樹的問題  給定N個節(jié)點,能構(gòu)成多少種不同的二叉樹?

一些筆試題
1、16個人按順序去買燒餅,其中8個人每人身上只有一張5塊錢,另外8個人每人身上只有一張10塊錢。燒餅5塊一個,開始時燒餅店老板身上沒有錢。16個顧客互相不通氣,每人只買一個。問這16個人共有多少種排列方法能避免找不開錢的情況出現(xiàn)。
h(8)=16!/(8!*9!)=1430,所以總數(shù)=h(8)*8!*8!=16!/9
2、在圖書館一共6個人在排隊,3個還《面試寶典》一書,3個在借《面試寶典》一書,圖書館此時沒有了面試寶典了,求他們排隊的總數(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)?的輸入

    這篇文章主要介紹了C++?中如何結(jié)束?while?(cin>>str)?的輸入,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-07-07
  • C++ 賦值構(gòu)造函數(shù)注意點介紹

    C++ 賦值構(gòu)造函數(shù)注意點介紹

    下面小編就為大家?guī)硪黄狢++ 賦值構(gòu)造函數(shù)注意點介紹。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-12-12
  • Qt QFtp客戶端實現(xiàn)上傳下載文件

    Qt QFtp客戶端實現(xiàn)上傳下載文件

    本文主要介紹了Qt QFtp客戶端實現(xiàn)上傳下載文件,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-07-07
  • C++深入學(xué)習(xí)之徹底理清重載函數(shù)匹配

    C++深入學(xué)習(xí)之徹底理清重載函數(shù)匹配

    C++ 不允許變量重名,但是允許多個函數(shù)取相同的名字,只要參數(shù)表不同即可,這叫作函數(shù)的重載,下面這篇文章主要給大家介紹了關(guān)于C++深入學(xué)習(xí)之徹底理清重載函數(shù)匹配的相關(guān)資料,需要的朋友可以參考下
    2019-01-01
  • 詳解C++中的左值,純右值和將亡值

    詳解C++中的左值,純右值和將亡值

    C++中本身是存在左值,右值的概念,但是在C11中又出現(xiàn)了左值,純右值,將亡值得概念;這里我們主要介紹這些值的概念,感興趣的可以了解一下
    2022-09-09
  • C++印刷模板使用方法詳解

    C++印刷模板使用方法詳解

    模板是C++支持參數(shù)化多態(tài)的工具,使用模板可以使用戶為類或者函數(shù)聲明一種一般模式,使得類中的某些數(shù)據(jù)成員或者成員函數(shù)的參數(shù)、返回值取得任意類型
    2022-11-11
  • Protocol Buffer技術(shù)深入理解(C++實例)

    Protocol Buffer技術(shù)深入理解(C++實例)

    C++實例Protocol Buffer技術(shù)詳解,感興趣的朋友可以了解下
    2013-01-01
  • C++使用jsoncpp庫解析Json

    C++使用jsoncpp庫解析Json

    對json的解析操作是我們?nèi)粘i_發(fā)中經(jīng)常會遇到的一個需求,下面這篇文章主要給大家介紹了關(guān)于C++使用jsoncpp庫解析Json的相關(guān)資料,需要的朋友可以參考下
    2021-06-06
  • C語言實現(xiàn)旅游景點咨詢系統(tǒng)

    C語言實現(xiàn)旅游景點咨詢系統(tǒng)

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)旅游景點咨詢系統(tǒng),文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-12-12
  • C語言 函數(shù)指針(指向函數(shù)的指針)詳解

    C語言 函數(shù)指針(指向函數(shù)的指針)詳解

    本文主要介紹 C語言函數(shù)指針的知識,這里整理了詳細的資料及示例代碼以便大家學(xué)習(xí)參考,有需要學(xué)習(xí)此部分知識的朋友可以參考下
    2016-08-08

最新評論