ACM母函數(shù)080421ppt課件

1、ACM程序設(shè)計(jì)程序設(shè)計(jì)杭州電子科技大學(xué) 劉春英上一周，上一周，你你 了嗎？了嗎？練習(xí)每周一星每周一星7 7）：）：0705420207054202第八講第八講母函數(shù)及其應(yīng)用母函數(shù)及其應(yīng)用（Generation function）從遞推關(guān)系說(shuō)起從遞推關(guān)系說(shuō)起研究以下多項(xiàng)式乘法：研究以下多項(xiàng)式乘法：可以看出：可以看出：x2x2項(xiàng)的系數(shù)項(xiàng)的系數(shù)a1a2+a1a3+.+an-1ana1a2+a1a3+.+an-1an中所有的項(xiàng)包括中所有的項(xiàng)包括n n個(gè)個(gè)元素元素a1a1，a2a2， anan中取兩個(gè)組合的全體；中取兩個(gè)組合的全體；同理：同理：x3x3項(xiàng)系數(shù)包含了從項(xiàng)系數(shù)包含了從n

2、n個(gè)元素個(gè)元素a1a1，a2a2， anan中取中取3 3個(gè)元素組合的全體；個(gè)元素組合的全體；以此類推。以此類推。 (81)若令a1=a2= =an=1，在8-1式中a1a2+a1a3+.+an-1an項(xiàng)系數(shù)中每一個(gè)組合有1個(gè)貢獻(xiàn)，其他各項(xiàng)以此類推。故有：（82）特例：母函數(shù)定義：母函數(shù)定義：n對(duì)于序列對(duì)于序列a0a0，a1a1，a2a2，構(gòu)造一函數(shù)：構(gòu)造一函數(shù)： n稱函數(shù)稱函數(shù)G(x)G(x)是序列是序列a0a0，a1a1，a2a2，的的母函數(shù)母函數(shù) For example:(1+x)n是序列C(n,0),C(n,1),.,C(n,n)的母函數(shù)。 如若已知序列a0，a1，a2，則對(duì)應(yīng)的母函數(shù)

3、G(x)便可根據(jù)定義給出。反之，如若已經(jīng)求得序列的母函數(shù)G(x)，則該序列也隨之確定。 序列a0，a1，a2，可記為an 。 實(shí)實(shí) 例例 分分 析析例例1 1：若有：若有1 1克、克、2 2克、克、3 3克、克、4 4克的砝碼各一克的砝碼各一 枚，枚，能稱出哪幾種重量？各有幾種可能方案？能稱出哪幾種重量？各有幾種可能方案？ 如何解決這個(gè)問(wèn)題呢？考慮構(gòu)造母函數(shù)。如果用x的指數(shù)表示稱出的重量，那么：1個(gè)1克的砝碼可以用函數(shù)1+x表示，1個(gè)2克的砝碼可以用函數(shù)1+x2表示，1個(gè)3克的砝碼可以用函數(shù)1+x3表示，1個(gè)4克的砝碼可以用函數(shù)1+x4表示，幾種砝碼的組合可以稱重的情況，可幾種砝碼的組合可以稱

4、重的情況，可以用以上幾個(gè)函數(shù)的乘積表示：以用以上幾個(gè)函數(shù)的乘積表示：(1+x)(1+x2)(1+x3)(1+x4)(1+x)(1+x2)(1+x3)(1+x4)=(1+x+x2+x3)(1+x3+x4+x7)=(1+x+x2+x3)(1+x3+x4+x7)=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10 =1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10 從上面的函數(shù)知道：可稱出從從上面的函數(shù)知道：可稱出從1 1克到克到1010克，系數(shù)便克，系數(shù)便是方案數(shù)。是方案數(shù)。例如右端有例如右端有2x5 2x5 項(xiàng)，即稱出項(xiàng)，即稱出5 5克的方案有克的方

5、案有2 2：5=3+2=4+15=3+2=4+1；同樣，；同樣，6=1+2+3=4+26=1+2+3=4+2；10=1+2+3+410=1+2+3+4。故稱出故稱出6 6克的方案有克的方案有2 2，稱出，稱出1010克的方案有克的方案有1 1 例例2：求用：求用1分、分、2分、分、3分的郵票貼分的郵票貼出不同數(shù)值的方案數(shù)出不同數(shù)值的方案數(shù) n因郵票允許重復(fù)，故母函數(shù)為：因郵票允許重復(fù)，故母函數(shù)為：n以展開(kāi)后的以展開(kāi)后的x4x4為例，其系數(shù)為為例，其系數(shù)為4 4，即，即4 4拆拆分成分成1 1、2 2、3 3之和的拆分?jǐn)?shù)為之和的拆分?jǐn)?shù)為4 4；n即即 ：4=1+1+1+1=1+1+2=1+3=2

6、+24=1+1+1+1=1+1+2=1+3=2+2概念：整數(shù)拆分概念：整數(shù)拆分 n所謂整數(shù)拆分即把整數(shù)分解成若干整所謂整數(shù)拆分即把整數(shù)分解成若干整數(shù)的和相當(dāng)于把數(shù)的和相當(dāng)于把n n個(gè)無(wú)區(qū)別的球放個(gè)無(wú)區(qū)別的球放到到n n個(gè)無(wú)標(biāo)志的盒子，盒子允許空，個(gè)無(wú)標(biāo)志的盒子，盒子允許空，也允許放多于一個(gè)球）。也允許放多于一個(gè)球）。n整數(shù)拆分成若干整數(shù)的和，辦法不一，整數(shù)拆分成若干整數(shù)的和，辦法不一，不同拆分法的總數(shù)叫做拆分?jǐn)?shù)。不同拆分法的總數(shù)叫做拆分?jǐn)?shù)。 練習(xí)寫出以下問(wèn)題的母函數(shù)）：練習(xí)寫出以下問(wèn)題的母函數(shù)）：n例例3 3：若有：若有1 1克砝碼克砝碼3 3枚、枚、2 2克砝碼克砝碼4 4枚、枚、4 4克砝

7、碼克砝碼2 2枚，問(wèn)能稱出哪幾種重量？枚，問(wèn)能稱出哪幾種重量？各有幾種方案？各有幾種方案？ n例例4: 4: 整數(shù)整數(shù)n n拆分成拆分成1 1，2 2，3 3，m m的和，求其母函數(shù)。的和，求其母函數(shù)。n例例5 5：如若上例中：如若上例中m m至少出現(xiàn)一次，至少出現(xiàn)一次，其母函數(shù)又如何？其母函數(shù)又如何？ 如何編寫程序如何編寫程序?qū)崿F(xiàn)母函數(shù)的應(yīng)用呢？實(shí)現(xiàn)母函數(shù)的應(yīng)用呢？核心問(wèn)題核心問(wèn)題關(guān)鍵：對(duì)多項(xiàng)式展開(kāi)關(guān)鍵：對(duì)多項(xiàng)式展開(kāi)以整數(shù)拆分為例：以整數(shù)拆分為例：觀察以下的母函數(shù)：觀察以下的母函數(shù)：首先思考：如果讓你手工計(jì)算，你是怎樣處理的？首先思考：如果讓你手工計(jì)算，你是怎樣處理的？實(shí)際編程：讓計(jì)算機(jī)按照

8、自己的思路計(jì)算即可實(shí)際編程：讓計(jì)算機(jī)按照自己的思路計(jì)算即可/ Author by lwg#include using namespace std;const int lmax=10000; int c1lmax+1,c2lmax+1;int main()int n,i,j,k;while (cinn)for (i=0;i=n;i+) c1i=0;c2i=0; for (i=0;i=n;i+) c1i=1; for (i=2;i=n;i+)for (j=0;j=n;j+)for (k=0;k+j=n;k+=i) c2j+k+=c1j; for (j=0;j=n;j+) c1j=c2j;c2j=0

9、; coutc1nendl;return 0;主打例題：主打例題：HDOJ_1398 Square Coins HDOJ_1398 Square Coins Sample InputSample Input2 2101030300 0 Sample OutputSample Output1 14 42727算法分析：算法分析：典型的利用母函數(shù)可解的題目。典型的利用母函數(shù)可解的題目。G(x)=(1+x+x2+x3+x4+)(1+x4+x8+x12+)(1+x9+x18+x27+)/HDOJ_1398 Square Coins#include using namespace std;const i

10、nt lmax=300;int c1lmax+1,c2lmax+1;int main(void)int n,i,j,k;while (cinn & n!=0)for (i=0;i=n;i+)c1i=1;c2i=0;for (i=2;i=17;i+)for (j=0;j=n;j+)for (k=0;k+j=n;k+=i*i)c2j+k+=c1j;for (j=0;j=n;j+)c1j=c2j;c2j=0;coutc1nn & n!=0)for (i=0;i=n;i+)c1i=1;c2i=0;for (i=2; i=17; i+)for (j=0;j=n;j+)for (k=0;k+j=n; k+

11、=elemi-1 ) c2j+k+=c1j;for (j=0;j=n;j+)c1j=c2j;c2j=0;coutc1nendl;return 0;考慮考慮1）：）：nHDOJ_1028HDOJ_1028nIgnatius and the Ignatius and the Princess IIIPrincess III考慮考慮2）：）：nHDOJ_1085HDOJ_1085nHolding Bin-Laden Holding Bin-Laden Captive!Captive!考慮考慮3）：）：nHDOJ_1171HDOJ_1171nBig EventBig Eventnin HDUin HDU考慮考慮4）：）：nHDOJ_1709HDOJ_1709The BalanceThe BalanceAny questions?Any questions?附：相關(guān)作業(yè)附：相關(guān)作業(yè)(hdoj)：2019Exercise(9)_2