ACM培训第十二讲-组合数学教程.ppt

ACM程序设计第十二讲-组合数学;组合数学简介;加法乘法原理;[ 例 ] 某班选修企业管理的有 18 人，不选 的有 10 人，则该班共有 18 + 10 = 28 人。;[例] 某种字符串由两个字符组成，第一个字符可选自{a，b，c，d，e}，第二个字符可选自{1，2，3}，则这种字符串共有5 ?3 = 15 个。;例 题;例 题;例 题;例 题;例 题;两个推论;两个推论;容斥原理;容斥原理两个基本公式;容斥原理指的就是以上两个基本公式。; 例 求不超过120的素数个数。; 注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7这四个数，又包含了1这个非素数。2， 3，5，7本身是素数。故所求的不超过 120的素数个数为： 27+4-1=30 ;　鸽巢原理;　鸽巢原理之二;鸽巢原理之二;例 题;定理;定理;定理