离散数学第七章计数.ppt

第七章 计数 7.1 基本计数原理 1.加法原理 2.乘法原理 加法原理 加法原理又称为和计数原理，也称和规则，存 在三种表述形式，其本质是说，整体等于其部分之和 。 若集合X是不相交非空子集S1，S2，Sm 的并，则|X|= 若E1，E2，Em是彼此互斥事件，并且 E1发生有e1种方式，E2发生有e2种方式，Em发生 有em种方式，则E1或E2或或Em发生有e1+e2+em 种方式。 应该指出的是，事件E1和E2互斥是说，E1和E2 发生但两者不能同时发生。 l 如果选择事物O1有n1种方法，选择 事物O2有n2种方法，选择事物Om有nm种 方法，并且选择诸事物方法不重叠，则选取O1 或O2或或Om有n1+n2+nm种方法。 加法原理 l例7.1.1 一个学生想选修一门数学课或 一门生物学课，但不能同时选修两门课。如果 该生对5门数学课和3门生物学课具有选课条件 ，试问该生有多少方式来选修课程？ 乘法原理 l乘法原理又称有序计数原理，也称积规 则，类似加法原理，也有三种表述形式。 l 若S1，S2，Sm是非空集合，则 笛卡尔积S1S2Sm的元素个数是 l 若事件E1，E2，Em发生分别有 e1，e2，em种方式，并且诸事件是独立的 ，则事件E1或E2或或Em依次发生有 e1e2em种方式。 乘法原理 l 如果选取事物O1，O2，Om分别 有n1，n2，nm种方法，并且选取诸事物方 法不重叠，则事物O1与O2与与Om依次选取 有n1n2nm种方法。 乘法原理 l例7.1.2 一个学生要选修两门课，第一 门课在上午4小时内任选1小时，第二门课在下 午3小时内也可任选1小时，试问该生有多少种 可能的时间安排？ l例7.1.3 计数因特网地址。在由计算机的物 理网络互连而构成的因特网中，每台计算机的网 络连接被分配一个因特网地址。在网际协议版本 IPV4中，一个地址是32位的位串，它以网络标识 netid开始，后跟随主机标识hostid，该标识把一个 计算机认定为某个指定网络成员。 乘法原理 乘法原理 l根据网络标识和主机标识位数的不同目前使 用3类地址形式： l用于最大规模网络的A类地址，由0后跟7位网 络标识和24位的主机标识构成。 l用于中等规模网络的B类地址，由位串10后跟 14位的网络标识和16位的主机标识构成。 l用于最小规模网络的C类地址，由位串110后 跟21位的网络标识和8位的主机标识构成。 l此外，又规定位串1111111在A类的网络标识 中是无效的，全0和全1组成的主机标识对任何网络都 是无效的。试计数因特网上的计算机有多少不同的有 效IPV4地址？ 乘法原理 l令D是因特网上计算机的有效地址数， DA,DB,DC分别表示A类B类和C类的有效地址， 根据加法原理D= DA+DB+DC lA类的网络标识有27-1=127个（ 1111111无效），主机标识224-2=16777214（ 全0和全1组成的主机标识无效），根据乘法原 理，DA=127*16777214 乘法原理 lB类的网络标识有214个，主机标识216- 2个，根据乘法原理，DB= 214 * （216-2） lC类的网络标识有221个，主机标识28-2 个，根据乘法原理，DB= 221 * （28-2） lD= DA+DB+DC=3737091842 7.2 鸽洞原理 l若n+1只鸽子入住n个鸽洞，则至少有1 个鸽洞里至少有2只鸽子。 l例7.2.1 在任意一群366人中，至少有2 人生日相同。 l例7.2.2 抽屉里有3副手套，随意抽出4 只手套，则其中至少有一副手套。 鸽洞原理 l例7.2.3 一个学生用37天准备考试。根 据以往的经验他知道需要复习的时间不超过60 个小时，他打算每天至少复习1小时，证明不 管他如何安排学习时间表（假定每天学习时数 为整数），必存在相继的若干天，他恰好共学 习13小时。 鸽洞原理 l设t1是第一天学习的时数，t2是前2天 学习时数，t3是前3天学习时数 l因为每天至少学习1小时，所以t11,数 列t1,t2,t37是严格单调递增的： t11，c为正实数， 则 下面举一例说明定理7.5.1的应用 例如，分析二分检索算法。若n为偶数时 ，二分检索算法把对某个元素在长度为n的搜 索序列中的搜索转化为对一元素在长度为n/2 的搜索序列中的二分检索。因此，规模为n的 问题被分解成规模为n/2的问题。为执行这个 分解需要2次比较，1次是为了确定要用到表的 哪一半，另1次是为了确定表是否还有项留下 来。所以，若f(n)是在规模为n的搜索序列中搜 索一个元素所需要的比较次数，则当n是偶数 时，f(n)=f(n/2)+2。根据定理7.5.1知，a=1， b=2，c=2，因此f(n)是O(log2n)。