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

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

 更新時(shí)間:2013年05月28日 17:49:23   作者:  
本篇文章是對(duì)卡特蘭數(shù)及其應(yīng)用進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
Catalan number,卡特蘭數(shù)又稱(chēng)卡塔蘭數(shù),是組合數(shù)學(xué)中一個(gè)常出現(xiàn)在各種計(jì)數(shù)問(wèn)題中出現(xiàn)的數(shù)列。以比利時(shí)的數(shù)學(xué)家歐仁·查理·卡塔蘭 (1814–1894)命名。
令h(0)=1,h(1)=1,catalan數(shù)滿(mǎn)足遞推式: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.

它也滿(mǎn)足

C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_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ù)共有{2n \choose n}個(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)。

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

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

出棧次序問(wèn)題  
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)?的輸入

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

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

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

    Qt 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-07
  • C++深入學(xué)習(xí)之徹底理清重載函數(shù)匹配

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

    C++ 不允許變量重名,但是允許多個(gè)函數(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)的工具,使用模板可以使用戶(hù)為類(lèi)或者函數(shù)聲明一種一般模式,使得類(lèi)中的某些數(shù)據(jù)成員或者成員函數(shù)的參數(shù)、返回值取得任意類(lèi)型
    2022-11-11
  • Protocol Buffer技術(shù)深入理解(C++實(shí)例)

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

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

    C++使用jsoncpp庫(kù)解析Json

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

    C語(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-12
  • C語(yǔ)言 函數(shù)指針(指向函數(shù)的指針)詳解

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

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

最新評(píng)論