《算法合集之母函数的性质及应用幻灯片.ppt》由会员分享，可在线阅读，更多相关《算法合集之母函数的性质及应用幻灯片.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法合集之母函数的性质及应用第1页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v定义 v母函数是用于对应一个无穷序列的幂级数，一般来说母函数有形式：第2页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v举一个例子：闭形式不考虑收敛问题！第3页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v基本操作v1放缩：第4页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v2加减法：第5页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v3右移:第6页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v4.求导：第7页，共26页
2、，编辑于2022年，星期一母函数的性质母函数的性质v举一个求导的例子：第8页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v5卷积规则：组合问题第9页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v简单的序列所对应的母函数不定方程非负整数解的个数第10页，共26页，编辑于2022年，星期一母函数的应用母函数的应用v例1原创题 v例3Sweets第11页，共26页，编辑于2022年，星期一母函数的应用母函数的应用v例1小明出门旅游，需要带一些食物，包括薯片，巧克力，矿泉水，汉堡，牛奶和糖果。经过估计，他觉得带n(n=10100)件食物比较合适，但他还有一些癖好：最多带
3、1个汉堡巧克力的块数是5的倍数最多带4瓶矿泉水薯片的包数是一个偶数最多带3罐牛奶糖果的个数是4的倍数v问你小明有多少种方式来准备这次旅行所带的食物。第12页，共26页，编辑于2022年，星期一母函数的应用母函数的应用v汉堡v巧克力v薯片v矿泉水v牛奶v糖果第13页，共26页，编辑于2022年，星期一母函数的应用母函数的应用v运用卷积规则第14页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v指数型母函数复杂简单！第15页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v最基本的指数型母函数Taylor公式 名称来源第16页，共26页，编辑于2022年，星期一母函数的性
4、质母函数的性质v乘积 排列问题！第17页，共26页，编辑于2022年，星期一母函数的应用母函数的应用v例2Chocolatev例4证明题第18页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v母函数型Plya定理v（Plya定理）设G是n个对象的一个置换群，用m种颜色涂染这n个对象，则不同染色方案数为 不够具体！第19页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v把m种颜色具体表示出来！母函数型Plya定理 第20页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v一个具体的例子：有4颗珠子绕成一圈，用两种颜色染色，旋转后重叠的方案算一种。置换群G：
5、Plya定理 第21页，共26页，编辑于2022年，星期一母函数的性质母函数的性质v母函数型Plya定理得具体的方案 2黑2白的有两种，4黑，4白，3黑1白，3白1黑的都只有1种 第22页，共26页，编辑于2022年，星期一母函数的应用母函数的应用v例5 IOI2003国家集训队难题讨论活动0015 Polygon第23页，共26页，编辑于2022年，星期一总结总结离散数学连续数学母函数v解决问题v优化算法v证明命题第24页，共26页，编辑于2022年，星期一参考文献v1 吴文虎，王建德.信息学奥林匹克竞赛指导组合数学的算法与程 序设计.清华大学出版社，2002v2 刘汝佳，黄亮.算法艺术与信
6、息学竞赛.清华大学出版社，2004v3 Ronald L.Graham，Donald E.Knuth，Oren Patashnik.Concrete MathematicsA Foundation for Computer Science(2nd Edition).Addison-Wesley Professional，1994v4 卢开澄.组合数学（第三版）.清华大学出版社，2002v5 周源.NOI冬令营讲稿.2008v6 雷环中，金恺.IOI中国国家集训队难题讨论活动解题报告，2003第25页，共26页，编辑于2022年，星期一Thats all.Thank you!欢迎提问！第26页，共26页，编辑于2022年，星期一