c遞推算法詳解

1、遞 推 算 法遞推問題求解過程確定狀態(tài)確定遞推關(guān)系和邊界條件程序?qū)崿F(xiàn)例1：計算系數(shù)(NOIP2011day2)【題目描述】給定一個多項式(ax+by)k,請求出多項式展開后xnym項的系數(shù)【輸入】共一行，包含5個整數(shù)，分別為a,b,k,n,m，每兩個整數(shù)之間用一個空格隔開?！据敵觥枯敵龉?行，包含一個整數(shù)，表示所求的系數(shù)，這個系數(shù)可能很大，輸出對10007 取模后的結(jié)果?！据斎胼敵鰳永?1 1 3 1 2 3【數(shù)據(jù)范圍】 對于 30%的數(shù)據(jù)，有0k10； 對于 50%的數(shù)據(jù)，有a = 1，b = 1； 對于 100%的數(shù)據(jù)，有0k1,000，0n, mk， 且n + m = k，0a，b1,

2、000,000。方法一根據(jù)二項式定理可知： (ax+by)k= = 取i=n,xnym的系數(shù)為其中an和bm可以用快速冪來計算，在lg(n)+lg(m)內(nèi)完成。計算 可以用遞推來求解。狀態(tài)：fi,j表示從i個數(shù)中選j個數(shù)的方案數(shù)。fk,n就是答案。根據(jù)第i數(shù)選還是不選來進行分析： 1.選擇第i個數(shù)：此情況的方案數(shù)等價于從i-1個數(shù)中選擇j-1個數(shù)的方案數(shù)即fi-1,j-1; 2.不選第i個數(shù)：此情況的方案數(shù)等價于從i-1個數(shù)中選擇j個數(shù)的方案數(shù)即fi-1,j 所以fi,j=fi-1,j-1+fi-1,j邊界條件：fi,0=1,fi,i=1。 時間復(fù)雜度為O(n*k)。 方法二當(dāng)k達到106的時

3、候，方法一會超時。由于10007是素數(shù)，在計算C(k,n)mod 10007時可以采用擴展GCD來解決。時間復(fù)雜度為O(k)。參考代碼：#include #include using namespace std;ifstream fin(factor.in);ofstream fout(factor.out); const int MAXN=1005;int dpMAXNMAXN,a,b,k,n,m,ans; int main()finabknm;dp11=dp12=1;for (int i=2;i=k;i+)for (int j=1;j=i+1;j+)dpij = (dpi-1j + dpi

4、-1j-1) % 10007;ans = dpkm+1;for (int i=1;i=n;i+)ans= (ans%10007) * (a%10007) % 10007;for (int i=1;i=m;i+)ans= (ans%10007) * (b%10007) % 10007;foutansendl;return 0;例2：B光滑數(shù)【問題描述】B為一個正整數(shù)，如果一個自然數(shù)N的質(zhì)因子分解式中沒有大于B的因子，我們就稱N是一個B光滑數(shù)。請你編一個程序，求出某個區(qū)間中所有的B光滑數(shù)的個數(shù)。輸入：輸入文件名為，僅有一行，包含三個用空格隔開的整數(shù)N,M,B,其中1=N=2，000，000，000

5、,1=M=100，000，000,1=Bx2F=x2-x1+1 x2=prib可直接驗證 x1=x2F=trunc(log2(x2)-trunc(log2(x1) b=1例3：出棧序列統(tǒng)計【問題描述】棧是常用的一種數(shù)據(jù)結(jié)構(gòu)，有n個元素在棧頂端一側(cè)等待進棧，棧頂端另一側(cè)是出棧序列。你已經(jīng)知道棧的操作有兩種：push和pop，前者是將一個元素進棧，后者是將棧頂元素彈出?，F(xiàn)在要使用這兩種操作，由一個操作序列可以得到一系列的輸出序列。請你編程求出對于給定的n，計算并輸出由操作數(shù)序列1，2，n，經(jīng)過一系列操作可能得到的輸出序列總數(shù)。【輸入】 【輸出】就一個數(shù)n(1n1000)。 一個數(shù)，即可能輸出序列的

6、總數(shù)目?！緲永? 5【算法分析】我們通過回溯的方法計算并輸出不同的出棧序列，這里只要求輸出不同的出棧序列總數(shù)目，所以我們希望能找出相應(yīng)的遞推公式進行處理。 從排列組合的數(shù)學(xué)知識可以對此類問題加以解決。 我們先對n個元素在出棧前可能的位置進行分析，它們有n個等待進棧的位置，全部進棧后在棧里也占n個位置，也就是說n個元素在出棧前最多可能分布在2*n位置上。 出棧序列其實是從這2n個位置上選擇n個位置進行組合，根據(jù)組合的原理，從2n個位置選n個，有C(2n,n)個。但是這里不同的是有許多情況是重復(fù)的，每次始終有n個連續(xù)的空位置，n個連續(xù)的空位置在2n個位置里有n+1種，所以重復(fù)了n+1次。所以出棧

7、序列的種類數(shù)目為：【算法分析】 C(2n,n)/(n+1)=2n*(2n-1)*(2n-2)*(n+1)/n!/(n+1)=2n*(2n-1)*(2n-2)*(n+2)/n!。 考慮到這個數(shù)據(jù)可能比較大，所以用高精度運算來計算這個結(jié)果。 本題實際是一個經(jīng)典的Catalan數(shù)模型。有關(guān)Catalan數(shù)的詳細解釋請參考組合數(shù)學(xué)等書。參考程序：#include #include using namespace std;typedef long long lld;lld i,n,ans;lld h1000;int main()freopen (stack.in,r,stdin);freopen (st

8、ack.out,w,stdout);h2=1;cinn;n=n+2; for (lld i=3;i=n;i+)for (lld k=2;ki;k+)hi=hi+hk*hi-k+1;couthn=3)邊界條件：f1=1,f2=2遞推關(guān)系式 1 i=1fi= 2 i=2 fi-1+fi-2 i=3答案為fn，時間復(fù)雜度為O(n)。方法二對于i=3,分析第一列的兩個格子覆蓋情況，有兩種情況： 1.用1*2的骨牌豎著覆蓋第一列，這種情況的方案數(shù)等于后面2*(i-1)的長方形的覆蓋方案數(shù)，即fi-1； 2.用兩個1*2的骨牌橫著覆蓋，這種情況的方案數(shù)等于后面2*(i-2)的長方形的覆蓋方案數(shù)，即fi-2

9、。 所以fi=fi-1+fi-2 方法三分析用1*2的骨牌覆蓋列的位置來計算方案數(shù)1.如果i為偶數(shù)，覆蓋方案分為兩類： (1)沒有豎立覆蓋其中一列的情況：全部用橫向覆蓋的方案，方案數(shù)為1； (2)有豎立覆蓋的情況：為了避免重復(fù)，考慮第一次豎立覆蓋的位置在x列，x必須是奇數(shù)，而且前1到x-1列覆蓋方法唯一，全部采用橫向覆蓋，方案數(shù)等于后面i-x列的覆蓋情況，即fi-x。所以當(dāng)i為偶數(shù)時,fi=1+f1+f3+.+fi-3+fi-1 2.如果i是奇數(shù)，一定有豎立覆蓋的情況，fi=1+f2+f4+.+fi-3+fi-1如何證明該遞推關(guān)系式等價于fi=fi-1+fi-2？試著用橫向覆蓋的來分析遞推關(guān)系式。 方法四分治，一分為二來考慮,左邊為n div 2列，右邊為n-n div 2列，如果左右獨立則方案數(shù)為fn div 2*fn-n div 2,如果有橫向覆蓋第n div 2列和第n div 2+1列，則方案數(shù)為fn div 2-1*fn-n div 2-1所以fn= fn div 2*fn-n div 2+fn div 2-1*fn-n div 2-1參考代碼：#include using namespac