• /  29
  • 下載費用: 9.90積分  

ACM課件 1 lecture_10 母函數及其應用_new.ppt

'ACM課件 1 lecture_10 母函數及其應用_new.ppt'
ACM 程序設計信息學院計算機應用系 余臘生*1今天,你 了嗎?ACDate2每周一星(9):ForYou Date3分組匯報…Date4第十講母函數及其應用(Generation function)Date5從遞推關系說起Date6研究以下等式: 可以看出:x2項的系數a1a2+a1a3+...+an-1an中所有的項包括n個元素a1,a2, …an中取兩個組合的全體;同理x3項系數包含了從n個元素a1,a2, …an中取3個元素組合的全體。以此類推。 Date7 若令a1=a2= …=an=1,在(2-1-1)式中a1a2+a1a3+...+an-1an項系數中每一個組合有1個貢獻,其他各項以此類推。故有:Date8母函數定義:對于序列a0,a1,a2,…構造一函數: 稱函數G(x)是序列a0,a1,a2,…的母函數Date9 For example: (1+x)n是序列C(n,0),C(n,1),...,C(n,n)的母函數。       如若已知序列a0,a1,a2,…則對應的母函數G(x)便可根據定義給出。 反之,如若已經求得序列的母函數G(x),則該序列也隨之確定。       序列a0,a1,a2,…可記為{an} 。 Date10實 例 分 析Date11例一、若有1克、2克、3克、4克的砝碼各一 枚,能稱出哪幾種重量?各有幾種可能方案? 如何解決這個問題呢?考慮構造母函數。如果用x的指數表示稱出的重量,則: 1個1克的砝碼可以用函數1+x表示, 1個2克的砝碼可以用函數1+x2表示, 1個3克的砝碼可以用函數1+x3表示, 1個4克的砝碼可以用函數1+x4表示,Date12幾種砝碼的組合可以稱重的情況,可以用以上幾個函數的乘積表示:(1+x)(1+x2)(1+x3)(1+x4)=(1+x+x2+x3)(1+x3+x4+x7)=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10 從上面的函數知道,可稱出從1克到10克,系數便是方案數。例如右端有2x5 項,即稱出5克的方案有2:5=3+2=4+1,同樣,6=1+2+3=4+2;10=1+2+3+4。故稱出6克的方案有2,稱出10克的方案有1  Date13例二、求用1分、2分、3分的郵票貼出不同數值的方案數。 因郵票允許重復,故母函數為 以展開后的x4為例,其系數為4,即4拆分成1、2、3之和的拆分數為4,即 :4=1+1+1+1=1+1+2=1+3=2+2Date14概念:整數拆分 所謂整數拆分即把整數分解成若干整數的和,相當于把n個無區別的球放到n個無標志的盒子,盒子允許空著,也允許放多于一個球。整數拆分成若干整數的和,辦法不一,不同拆分法的總數叫做拆分數。 Date15練習:例3:若有1克砝碼3枚、2克砝碼4枚、4克砝碼2枚,問能稱出哪幾種重量?各有幾種方案? 例4: 整數n拆分成1,2,3,…,m的和,求其母函數。如若其中m至少出現一次,其母函數又如何? 請自己寫出以上兩個問題的母函數。Date16如何編寫程序 實現母函數的應用呢? 關鍵:對多項式展開Date17以整數拆分為例:觀察以下的母函數:(這里以lwg寫的程序為例)Date18 #include using namespace std; const int lmax=10000; int c1[lmax+1],c2[lmax+1]; int main() { int n,i,j,k; while (cin>>n) {for (i=0;i<=n;i++) {c1[i]=0; c2[i]=0; } for (i=0;i<=n;i++) c1[i]=1; for (i=2;i<=n;i++) { for (j=0;j<=n;j++) for (k=0;k+j<=n;k+=i) { c2[j+k]+=c1[j]; } for (j=0;j<=n;j++) { c1[j]=c2[j]; c2[j]=0; } } cout<<c1[n]<<endl; } return 0; }Date19HDOJ_1398 Square Coins Sample Input 2 10 30 0 Sample Output 1 4 27Date20算法分析:典型的利用母函數可解的題目。G(x)=(1+x+x2+x3+x4+…)(1+x4+x8+x12+…)(1+x9+x18+x27+…)…Date21#include using namespace std;const int lmax=300;int c1[lmax+1],c2[lmax+1];int main(void){ int n,i,j,k; while (cin>>n && n!=0) { for (i=0;i<=n;i++) { c1[i]=1; c2[i]=0; } for (i=2;i<=17;i++) { for (j=0;j<=n;j++) for (k=0;k+j<=n;k+=i*i) { c2[j+k]+=c1[j]; } for (j=0;j<=n;j++) { c1[j]=c2[j]; c2[j]=0; } } cout<<c1[n]<>n && n!=0) { for (i=0;i<=n;i++) { c1[i]=1; c2[i]=0; } for (i=2; i<=17; i++) { for (j=0;j<=n;j++) for (k=0;k+j<=n; k+=elem[i-1] ) { c2[j+k]+=c1[j]; } for (j=0;j<=n;j++) { c1[j]=c2[j]; c2[j]=0; } } cout<<c1[n]<<endl; } return 0;}Date23Any Questions?Date24思考: HDOJ_1028 Ignatius and the Princess III Date25思考: HDOJ_1085 Holding Bin-Laden Captive! Date26思考: HDOJ_1171 Big Event in HDU Date27思考: HDOJ_1059 DividingDate28附:相關練習題(hdoj):1028 、1059 、10851171 、1398 、2069其它相關題目(比如求郵票、硬幣之類的組合數、整數的不同拆分數等)Date29
關 鍵 詞:
及其 lecture 母函數 10 應用 new acm
 天天文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:ACM課件 1 lecture_10 母函數及其應用_new.ppt
鏈接地址: http://www.476824.live/p-51617035.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服點擊這里,給天天文庫發消息,QQ:1290478887 - 聯系我們

本站為“文檔C2C交易模式”,即用戶上傳的文檔直接賣給(下載)用戶,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有【成交的100%(原創)】。本站是網絡服務平臺方,若您的權利被侵害,侵權客服QQ:1290478887 歡迎舉報。

[email protected] 2017-2027 http://www.476824.live 網站版權所有

粵ICP備19057495號 

收起
展開
球探网即时蓝球比分 山东11选5任一计划 河北体彩十一选五玩法 3d图谜,总汇全图牛彩网 白姐透特一肖 五粮液股票分析 欢乐彩是骗局么 正规彩票投注app 广东11选五怎么玩图片 3d预测软件 江西11选5选号