(HDUACM09)母函数教程.ppt

下载文档 降价啦

6
0
约 28页
2017-04-24 发布于湖北
举报
版权申诉
保障服务

(HDUACM09)母函数教程.ppt

1、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

(HDUACM09)母函数教程

ACM程序设计;期中了——;每周一星（8）：;第九讲;研究以下多项式乘法：; 若令a1=a2= …=an=1，在（8-1）式中a1a2+a1a3+...+an-1an项系数中每一个组合有1个贡献，其他各项以此类推。故有：;母函数定义：; For example:;实例分析;例1：若有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？各有几种可能方案？?;几种砝码的组合可以称重的情况，可以用以上几个函数的乘积表示：;例2：求用1分、2分、3分的邮票贴出不同数值的方案数—— ;概念：整数拆分 ;练习（写出以下问题的母函数）：;如何编写程序实现母函数的应用呢？;以整数拆分为例：;// Author by lwg #include iostreamusing namespace std;const int lmax=10000; int c1[lmax+1],c2[lmax+1];int main(){ int n,i,j,k; while (cinn) {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; } } coutc1[n]endl; } return 0; };主打例题：HDOJ_1398 Square Coins ;算法分析：;//HDOJ_1398 Square Coins #include iostream using namespace std; const int lmax=300; int c1[lmax+1],c2[lmax+1]; int main(void) { int n,i,j,k; while (cinn 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; } } coutc1[n]endl; } return 0; };//HDOJ_1398 Square Coins //变化一点，灵活多多 … int main(void) { int n,i,j,k; int elem[17]={1,4,9,16,25,36,…,169,196,225,256,289} while (cinn 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; } } coutc1[n]endl; } return 0; } ;思考（1）：;思考（2）：;思考（3）：;思考（4）：;Any questions?;附：相关作业(hdoj)：;Welcome to HDOJ