算法合集之《母函数的性质及应用》PPT_第1页
算法合集之《母函数的性质及应用》PPT_第2页
算法合集之《母函数的性质及应用》PPT_第3页
算法合集之《母函数的性质及应用》PPT_第4页
算法合集之《母函数的性质及应用》PPT_第5页
已阅读5页，还剩21页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

母函数的性质及应用,2009国家集训队论文毛杰明南京外国语学校Email:maojm517邮政编码：210008,1,母函数的性质,定义母函数是用于对应一个无穷序列的幂级数，一般来说母函数有形式：,2,母函数的性质,举一个例子：,闭形式,不考虑收敛问题！,3,母函数的性质,基本操作1放缩：,4,母函数的性质,2加减法：,5,母函数的性质,3右移:,6,母函数的性质,4.求导：,7,母函数的性质,举一个求导的例子：,8,母函数的性质,5卷积规则：,组合问题,9,母函数的性质,简单的序列所对应的母函数,不定方程非负整数解的个数,10,母函数的应用,例1原创题例3Sweets,11,母函数的应用,例1小明出门旅游，需要带一些食物，包括薯片，巧克力，矿泉水，汉堡，牛奶和糖果。经过估计，他觉得带n(n=10100)件食物比较合适，但他还有一些癖好：最多带1个汉堡巧克力的块数是5的倍数最多带4瓶矿泉水薯片的包数是一个偶数最多带3罐牛奶糖果的个数是4的倍数问你小明有多少种方式来准备这次旅行所带的食物。,12,母函数的应用,汉堡巧克力薯片矿泉水牛奶糖果,13,母函数的应用,运用卷积规则,14,母函数的性质,指数型母函数,复杂,简单！,15,母函数的性质,最基本的指数型母函数,Taylor公式,名称来源,16,母函数的性质,乘积,排列问题！,17,母函数的应用,例2Chocolate例4证明题,18,母函数的性质,母函数型Plya定理（Plya定理）设G是n个对象的一个置换群，用m种颜色涂染这n个对象，则不同染色方案数为,不够具体！,19,母函数的性质,把m种颜色具体表示出来！,母函数型Plya定理,20,母函数的性质,一个具体的例子：有4颗珠子绕成一圈，用两种颜色染色，旋转后重叠的方案算一种。,置换群G：,Plya定理,21,母函数的性质,母函数型Plya定理得具体的方案,2黑2白的有两种，4黑，4白，3黑1白，3白1黑的都只有1种,22,母函数的应用,例5IOI2003国家集训队难题讨论活动0015Polygon,23,总结,离散数学,连续数学,母函数,解决问题优化算法证明命题,24,参考文献,1吴文虎，王建德.信息学奥林匹克竞赛指导组合数学的算法与程序设计.清华大学出版社，20022刘汝佳，黄亮.算法艺术与信息学竞赛.清华大学出版社，20043RonaldL.Graham，DonaldE.Knuth，OrenPatashnik.ConcreteMathematicsAFoundationforComputerScience(2ndEdition).Addison-WesleyProfessional，19944卢开澄.组合数学（第三版）.清华大学出版社，20025周源.NOI冬令营讲稿.20086雷环中
人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论