【文章內(nèi)容簡介】 要做仔細(xì)分析，其實(shí)我們還可以得到以下的遞推公式： ? (1)當(dāng) i為奇數(shù)時(shí) ,h(i)=h(i1)。 ? (2) 當(dāng) i為偶數(shù)時(shí) ,h(i)=h(i1)+h(i/2)。 ? 【 思考 】 n=10000怎么計(jì)算； n=3000000怎么計(jì)算； 遞推的應(yīng)用（一般遞推問題） ? 例題 5：猴子吃桃問題 1538 ? 猴子吃桃問題。猴子摘了一堆桃，第一天吃了一半，還嫌不過癮，又吃了一個(gè)；第二天又吃了剩下的一半零一個(gè)；以后每天如此。到第 n天，猴子一看只剩下一個(gè)了。問最初有多少個(gè)桃子？ 【 擴(kuò)展練習(xí) 】 猴子分桃 【 問題描述 】 有一堆桃子和 N只猴子，第一只猴子將桃子平均分成了M堆后，還剩了 1個(gè)，它吃了剩下的一個(gè)，并拿走一堆。后面的猴子也和第 1只進(jìn)行了同樣的做法，請問 N只猴子進(jìn)行了同樣做法后這一堆桃子至少還剩了多少個(gè)桃子 (假設(shè)剩下的每堆中至少有一個(gè)桃子 )？而最初時(shí)的那堆桃子至少有多少個(gè)？ 【 文件輸入 】 輸入包含二個(gè)數(shù)據(jù)，數(shù)據(jù)間用空格隔開。第一個(gè)數(shù)據(jù)為猴子的只數(shù) N(1≤N≤10) ，第二個(gè)數(shù)據(jù)為桃子分成的堆數(shù)M(2≤M≤7) 。 【 文件輸出 】 輸出包含兩行數(shù)據(jù)，第一行數(shù)據(jù)為剩下的桃子數(shù)，第二行數(shù)據(jù)為原來的桃子數(shù)。 【 樣例輸入 】 3 2 【 樣例輸出 】 1 15 遞推的應(yīng)用（一般遞推問題） ? 【 例題 6】 傳球游戲（ NOIP2022普及） 2309 ? 【 問題描述 】 上體育課的時(shí)候，小蠻的老師經(jīng)常帶著同學(xué)們一起做游戲。這次，老師帶著同學(xué)們一起做傳球游戲。 游戲規(guī)則是這樣的： n（ 3=n=30）個(gè)同學(xué)站成一個(gè)圓圈，其中的一個(gè)同學(xué)手里拿著一個(gè)球，當(dāng)老師吹哨子時(shí)開始傳球，每個(gè)同學(xué)可以把球傳給自己左右的兩個(gè)同學(xué)中的一個(gè)（左右任意），當(dāng)老師再吹哨子時(shí)，傳球停止，此時(shí)，拿著球沒傳出去的那個(gè)同學(xué)就是敗者，要給大家表演一個(gè)節(jié)目。 聰明的小蠻提出一個(gè)有趣的問題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了 m（ 3=m=30）次后，又回到小蠻手里。兩種傳球被視作不同的方法，當(dāng)且僅當(dāng)這兩種方法中，接到球的同學(xué)按照順序組成的序列是不同的。比如 3個(gè)同學(xué) 1號(hào)、 2號(hào)、 3號(hào)，并假設(shè)小蠻為 1號(hào)，球傳了 3次回到小蠻手里的方式有 1231和 1321，共兩種。 分析 ? 設(shè) f[i][k]表示經(jīng)過 k次傳到編號(hào)為 i的人手中的方案數(shù)，傳到 i號(hào)同學(xué)的球只能來自于 i的左邊一個(gè)同學(xué)和右邊一個(gè)同學(xué)，這兩個(gè)同學(xué)的編號(hào)分別是i1和 i+1，所以可以得到以下的遞推公式： ? f[i][k]=f[i1][k1]+f[i+1][k1] ? f[1][k]=f[n][k1]+f[2][k1], 當(dāng) i=1時(shí) ? f[n][k]=f[n1][k1]+f[1][k1], 當(dāng) i=1時(shí) ? 邊界條件： f[1][0]=1；結(jié)果在 f[1][m]中。 參考代碼 cinnm。 memset(f,0,sizeof(f))。 f[1][0]=1。 for(k=1。k=m。k++) { f[1][k]=f[2][k1]+f[n][k1]。 for(i=2。i=n1。i++)f[i][k]=f[i1][k1]+f[i+1][k1]。 f[n][k]=f[n1][k1]+f[1][k1]。 } coutf[1][m]endl。 遞推的應(yīng)用（組合計(jì)數(shù)） ? Catalan數(shù) ? 定義： Cn=n+2條邊的多邊形，能被分割成三角形的方案數(shù)，例如 5邊型的分割方案有： ? 如圖，有一個(gè)正 n+2邊形。任取一邊，從這邊的端點(diǎn)開始，依次給頂點(diǎn)編號(hào)為： 0,1,2,3,… .,n,n+1(所取的邊端點(diǎn)編號(hào)為 :0,n+1)。這樣，除線段所在頂點(diǎn)外，還有 n個(gè)頂點(diǎn)：1,2,3,… ,n。我們以該線段為三角形的一條邊，另一個(gè)頂點(diǎn)為 i(1=i=n)。 ? 我們設(shè)題意要求的三角形剖分方案數(shù)為 H(n)，即除線段頂點(diǎn) (編號(hào) 0與 n+1)外，還有 n個(gè)頂點(diǎn)時(shí)的三角形剖分方案為 H(n)。則以頂點(diǎn) 0,i為指定線段(上面還有 1,2,… ,i1，共 i1個(gè)頂點(diǎn) )的剖分?jǐn)?shù)位H(i1)；以頂點(diǎn) n+1， i為指定線段的剖分?jǐn)?shù)為H(ni)。根據(jù)乘法原理，以 0,i,n+1為一剖分三角形的剖分?jǐn)?shù)應(yīng)為： H(i1)*H(ni)， i=1,2,… ,n，所得的剖分各不相同，根據(jù)加法原理則有： ? 這與 Catalan數(shù) C(n)的表達(dá)式是一致的。故本題答案為 H(n)=C(n)。 ?????niinHiHnH1)(*)1()(具體實(shí)現(xiàn)時(shí) ， 若直接用上述公式計(jì)算 ， 對數(shù)字的精度要求較高 。 可將其化為遞推式 )1(1 )12(*2)( ?? ?? nfn nnf再進(jìn)行遞推計(jì)算 ， 并且注意類型的定義要用 long long長整型 。 Catalan數(shù)的應(yīng)用（部分和序列） ? 問題： n個(gè) 1和 n個(gè) 0組成一 2n位的二進(jìn)制，要求從左到右掃描，1的累計(jì)數(shù)不小于 0的累計(jì)數(shù)，試求滿足這條件的數(shù)有多少？ ? 【 類似 1】 將 n個(gè) 1和 n個(gè) 1排成一行，要求第 1個(gè)數(shù)至第 k個(gè)數(shù)的累加和均非負(fù)，問有幾種排列方法？ ? 【 類似 2】 有 2n個(gè)人排成一行進(jìn)入劇場。入場費(fèi) 5元。其中只有 n個(gè)人有一張 5元鈔票，另外 n人只有 10元鈔票，劇院無其它鈔票，問有多少種方法使得只要有 10元的人買票，售票處就有 5元的鈔票找零？ Catalan數(shù)的應(yīng)用（棧 NOIp2022） ? 問題：一個(gè)棧 (無窮大 )的進(jìn)棧序列為 1,2,3,..n，有多少個(gè)不同的出棧序列？ Catalan數(shù)的應(yīng)用（加括號(hào)） ? P=A1 A2 A3 …… An，依據(jù)乘法結(jié)合律，不改變其順序，只用括號(hào)表示成對的乘積，試問有幾種括號(hào)化的方案？ 【 分析 】 P(4)：即 4個(gè)數(shù)相乘的情況如下： (((a1a2)a3)a4)。((a1(a2a3))a4)。 ((a1a2)(a3a4))。(a1((a2a3)a4))。(a1(a2(a3a4)))。不失一般性，可以假設(shè)最后一次乘法運(yùn)算如下： (a1…ar)(ar+1…an),(1=r=n) 。令 P(n)表示 n個(gè)數(shù)乘積的 n1對括號(hào)插入的不同方案數(shù)，則： P(n)=p1pn1+p2pn2+….+pn 1p1,p1=p2=1 有： P(n+1)=p1pn+p2pn1+….+pnp1 (1) 令 C(k)=P(k+1),k=1,2,…,n ，代入 (1)式，有： C(n)=C(0)*C(n1)+C(1)*C(n2)+…+C(n 1)*C(0) = 因此，本題的答案為 C(n1)。 ?? ??ni inCiC1 )(*)1(遞推的應(yīng)用（組合計(jì)數(shù)） 錯(cuò)排問題 （ 經(jīng)典問題 ） ? n個(gè)數(shù)，分別為 1~n，排成一個(gè)長度為 n的排列。若每一個(gè)數(shù)的位置都與數(shù)的本身不相等，則稱這個(gè)排列是一個(gè)錯(cuò)排。例如， n=3，則錯(cuò)排有 2 3 3 1 2。編寫程序，求 n的錯(cuò)排個(gè)數(shù) 分析 ? 我們設(shè) k個(gè)元素的錯(cuò)位全排列的個(gè)數(shù)記做： f(k)。 ? 四個(gè)元素的錯(cuò)位排列 f(4)我們用窮舉法可以找到如下 9個(gè)： (4,3,2,1)。(3,4,1,2)。(2,1,4,3) (4,3,1,2)。(2,4,1,3)。(2,3,4,1) (4,1,2,3)。(3,4,2,1)。(3,1,4,2) 它們有什么規(guī)律呢？ 通過反復(fù)的試驗(yàn) ， 我們發(fā)現(xiàn)事實(shí)上有兩種方式產(chǎn)生 錯(cuò)位排列 ： k與 (1， 2， ? ， k1)的某一個(gè)數(shù)互換 ， 其他 k2個(gè)數(shù)進(jìn)行錯(cuò)排 ， 這樣可以得到 (k1) f(k2)個(gè)錯(cuò)位排列 。 k1個(gè)元素的