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

1、acm程序設(shè)計(jì)程序設(shè)計(jì)杭州電子科技大學(xué) 劉春英2021-11-222上一周，上一周，你你 了嗎？了嗎？練習(xí)2021-11-223每周一星每周一星（7 7）：）：07054202070542022021-11-224第八講第八講母函數(shù)及其應(yīng)用母函數(shù)及其應(yīng)用（generation function）2021-11-225從遞推關(guān)系說(shuō)起從遞推關(guān)系說(shuō)起2021-11-226研究以下研究以下多項(xiàng)式乘法多項(xiàng)式乘法：可以看出：可以看出：x x2 2項(xiàng)的系數(shù)項(xiàng)的系數(shù)a a1 1a a2 2+a+a1 1a a3 3+.+a+.+an-1n-1a an n中所有的項(xiàng)包括中所有的項(xiàng)包括n n個(gè)元個(gè)元素素a a1

2、1，a a2 2， a an n中取兩個(gè)組合的全體；中取兩個(gè)組合的全體；同理：同理：x x3 3項(xiàng)系數(shù)包含了從項(xiàng)系數(shù)包含了從n n個(gè)元素個(gè)元素a a1 1，a a2 2， a an n中取中取3 3個(gè)個(gè)元素組合的全體；元素組合的全體；以此類(lèi)推。以此類(lèi)推。 (81)2021-11-227若令a1=a2= =an=1，在（8-1）式中a1a2+a1a3+.+an-1an項(xiàng)系數(shù)中每一個(gè)組合有1個(gè)貢獻(xiàn)，其他各項(xiàng)以此類(lèi)推。故有：（82）特例：2021-11-228母函數(shù)定義：母函數(shù)定義：n對(duì)于序列對(duì)于序列a a0 0，a a1 1，a a2 2，構(gòu)造一函數(shù)：構(gòu)造一函數(shù)： n稱(chēng)函數(shù)稱(chēng)函數(shù)g(xg(x) )

3、是序列是序列a a0 0，a a1 1，a a2 2，的的母函數(shù)母函數(shù)2021-11-229 for example:for example:(1+x)n是序列c(n,0),c(n,1),.,c(n,n)的母函數(shù)。 如若已知序列a0，a1，a2，則對(duì)應(yīng)的母函數(shù)g(x)便可根據(jù)定義給出。反之，如若已經(jīng)求得序列的母函數(shù)g(x)，則該序列也隨之確定。 序列a0，a1，a2，可記為an 。 2021-11-2210實(shí)實(shí) 例例 分分 析析2021-11-2211例例1 1：若有：若有1 1克、克、2 2克、克、3 3克、克、4 4克的砝碼各一克的砝碼各一 枚，枚，能稱(chēng)出哪幾種重量？各有幾種可能方案？能稱(chēng)

4、出哪幾種重量？各有幾種可能方案？ 如何解決這個(gè)問(wèn)題呢？考慮構(gòu)造母函數(shù)。如果用x的指數(shù)表示稱(chēng)出的重量，則：1個(gè)1克的砝碼可以用函數(shù)1+x表示，1個(gè)2克的砝碼可以用函數(shù)1+x2表示，1個(gè)3克的砝碼可以用函數(shù)1+x3表示，1個(gè)4克的砝碼可以用函數(shù)1+x4表示，2021-11-2212幾種砝碼的組合可以稱(chēng)重的情況，可幾種砝碼的組合可以稱(chēng)重的情況，可以用以上幾個(gè)函數(shù)的乘積表示：以用以上幾個(gè)函數(shù)的乘積表示：(1+x)(1+x(1+x)(1+x2 2)(1+x)(1+x3 3)(1+x)(1+x4 4) )=(1+x+x=(1+x+x2 2+x+x3 3)(1+x)(1+x3 3+x+x4 4+x+x7 7

5、) )=1+x+x=1+x+x2 2+2x+2x3 3+2x+2x4 4+2x+2x5 5+2x+2x6 6+2x+2x7 7+x+x8 8+x+x9 9+x+x1010 從上面的函數(shù)知道：從上面的函數(shù)知道：可稱(chēng)出從可稱(chēng)出從1 1克到克到1010克，系數(shù)便克，系數(shù)便是方案數(shù)。是方案數(shù)。例如右端有例如右端有2x2x5 5 項(xiàng)，即稱(chēng)出項(xiàng)，即稱(chēng)出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。故稱(chēng)出故稱(chēng)出6 6克的方案有克的方案有2 2，稱(chēng)出，稱(chēng)出1010克的方案有克的方案有

6、1 1 2021-11-2213例例2 2：求用求用1 1分、分、2 2分、分、3 3分的郵票貼分的郵票貼出不同數(shù)值的方案數(shù)出不同數(shù)值的方案數(shù) n因郵票允許重復(fù)，故母函數(shù)為：因郵票允許重復(fù)，故母函數(shù)為：n以展開(kāi)后的以展開(kāi)后的x x4 4為例，其系數(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+24=1+1+1+1=1+1+2=1+3=2+22021-11-2214概念：整數(shù)拆分概念：整數(shù)拆分 n所謂整數(shù)拆分即把整數(shù)分解成若干整所謂整數(shù)拆分即把整數(shù)分解成若干整數(shù)的和（相當(dāng)于把數(shù)的和（

7、相當(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ù)。 2021-11-2215練習(xí)練習(xí)（寫(xiě)出以下問(wèn)題的母函數(shù)）：（寫(xiě)出以下問(wèn)題的母函數(shù)）：n例例3 3：若有：若有1 1克砝碼克砝碼3 3枚、枚、2 2克砝碼克砝碼4 4枚、枚、4 4克砝碼克砝碼2 2枚，問(wèn)能稱(chēng)出哪幾種重量？枚，問(wèn)能稱(chēng)出哪幾種重量？各有幾種方案？各有幾種方案？ n例例4: 4: 整數(shù)整數(shù)n n拆分成拆分成1

8、 1，2 2，3 3，m m的和，求其母函數(shù)。的和，求其母函數(shù)。n例例5 5：如若上例中：如若上例中m m至少出現(xiàn)一次，至少出現(xiàn)一次，其母函數(shù)又如何？其母函數(shù)又如何？ 2021-11-2216如何編寫(xiě)程序如何編寫(xiě)程序?qū)崿F(xiàn)母函數(shù)的應(yīng)用呢？實(shí)現(xiàn)母函數(shù)的應(yīng)用呢？核心問(wèn)題核心問(wèn)題關(guān)鍵：關(guān)鍵：對(duì)多項(xiàng)式展開(kāi)對(duì)多項(xiàng)式展開(kāi)2021-11-2217以以整數(shù)拆分整數(shù)拆分為例：為例：觀察以下的母函數(shù)：觀察以下的母函數(shù)：首先思考：首先思考：如果讓你手工計(jì)算，你是怎樣處理的？如果讓你手工計(jì)算，你是怎樣處理的？實(shí)際編程：實(shí)際編程：讓計(jì)算機(jī)按照自己的思路計(jì)算即可讓計(jì)算機(jī)按照自己的思路計(jì)算即可/ author by lwg#

9、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; coutc1nendl;return 0;2021-11-2219主打例題：主打例題：

10、hdoj_1398 square coinshdoj_1398 square coins sample inputsample input2 2101030300 0 sample outputsample output1 14 427272021-11-2220算法分析：算法分析：典型的利用母函數(shù)可解的題目。典型的利用母函數(shù)可解的題目。g(x)=(1+x+x2+x3+x4+)(1+x4+x8+x12+)(1+x9+x18+x27+)2021-11-2221/hdoj_1398 square coins#include using namespace std;const int lmax=30

11、0;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+=e

12、lemi-1 ) c2j+k+=c1j;for (j=0;j=n;j+)c1j=c2j;c2j=0;coutc1nendl;return 0;2021-11-2223思考思考（1 1）：）：nhdoj_1028hdoj_1028ignatius and the princess ignatius and the princess iiiiii2021-11-2224思考思考（2 2）：）：nhdoj_1085hdoj_1085holding bin-laden captive!holding bin-laden captive!2021-11-2225思考思考（3 3）：）：nhdoj_1171hdoj_1171big eventbig eventin hduin hdu2021-11-2226思考思考（4 4）：）：nhdoj_1709hdoj_1709the balancethe balanceany questions?any questions?2021-11-2228附：相關(guān)作業(yè)附：相關(guān)作業(yè)(hdoj)(hdoj)：20082008acm programmingacm programmingexercise(9exe