分类加法计数原理与分类加法计数原理与分步乘法计数原理的应用分步乘法计数原理的应用 ( (习题课习题课) )第一课时第一课时知识回顾知识回顾 1. 1.分类加法计数原理：分类加法计数原理：完成一件事有两类不同方案，在第完成一件事有两类不同方案，在第1 1类方类方案中有案中有m种不同的方法，在第种不同的方法，在第2 2类方案中类方案中有有n 种不同的方法，那么完成这件事共种不同的方法，那么完成这件事共有有Nmn种不同的方法种不同的方法.推广：推广：如果完成一件事有如果完成一件事有n n类不同方案，类不同方案，在第在第1 1类方案中有类方案中有m1 1种不同的方法，在第种不同的方法，在第2 2类方案中有类方案中有m2 2种不同的方法，种不同的方法，在第，在第n n类方案中有类方案中有mn n种不同的方法，那么完成种不同的方法，那么完成这件事的方法总数为这件事的方法总数为N Nm1 1m2 2mn n 2. 2.分步乘法计数原理：分步乘法计数原理：完成一件事需要两个步骤，做第完成一件事需要两个步骤，做第1 1步有步有m种不同的方法，做第种不同的方法，做第2 2步有步有n 种不同的方种不同的方法，那么完成这件事共有法，那么完成这件事共有N Nmn种不同种不同的方法的方法. . 推广：推广：如果完成一件事需要如果完成一件事需要n n个步骤，做个步骤，做第第1 1步有步有m1 1种不同的方法，做第种不同的方法，做第2 2步有步有m2 2种不同的方法，种不同的方法，做第，做第n n步有步有mn n种不同种不同的方法，那么完成这件事的方法总数为的方法，那么完成这件事的方法总数为N Nm1 1m2 2mn n应用举例应用举例 例例1 1 给程序模块命名，需要用给程序模块命名，需要用3 3个字个字符，其中首字符要求用字母符，其中首字符要求用字母A AG G或或U UZ Z，后两个要求用数字，后两个要求用数字1 19 9，问最多可以，问最多可以给多少个程序命名？给多少个程序命名？最多可以给最多可以给10531053个程序命名个程序命名 例例2 2 核糖核酸（核糖核酸（RNARNA）分子是在生物细胞）分子是在生物细胞中发现的化学成分，一个中发现的化学成分，一个RNARNA分子是一个有着分子是一个有着数百个甚至数千个位置的长链，长链中每一数百个甚至数千个位置的长链，长链中每一个位置上都由一种称为碱基的化学成分所占个位置上都由一种称为碱基的化学成分所占据据. .总共有总共有4 4种不同的碱基，分别用种不同的碱基，分别用A A，C C，G G，U U表示表示. .在一个在一个RNARNA分子中，各种碱基能够以任分子中，各种碱基能够以任意次序出现，所以在任意一个位置上的碱基意次序出现，所以在任意一个位置上的碱基与其他位置上的碱基无关与其他位置上的碱基无关. .假设有一类假设有一类RNARNA分分子由子由100100个碱基组成，那么能有多少个不同的个碱基组成，那么能有多少个不同的RNARNA分子？分子？A AG GC CU UA AA AA AU U G GG GC CC C4 4100100个个 例例3 3 电子元件很容易实现电路的通与断、电位电子元件很容易实现电路的通与断、电位的高与低等两种状态，而这也是最容易控制的两种的高与低等两种状态，而这也是最容易控制的两种状态状态. .因此计算机内部就采用了每一位只有因此计算机内部就采用了每一位只有0 0或或1 1两两种数字的记数法，即二进制种数字的记数法，即二进制. .为了使计算机能够识为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由储的最小计量单位，每个字节由8 8个二进制位构成个二进制位构成. .问：问：（1 1）一个字节（）一个字节（8 8位）最多可以表示多少个不同的位）最多可以表示多少个不同的字符？字符？（2 2）计算机汉字国际码（）计算机汉字国际码（GBGB码）包含了码）包含了6 7636 763个汉个汉字，一个汉字为一个字符，要对这些汉字进行编码，字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？每个汉字至少要用多少个字节表示？ 256256个个 2 2个个 例例4 4 计算机编程人员在编写好程序以后需计算机编程人员在编写好程序以后需要对程序进行测试，程序员需要知道到底有要对程序进行测试，程序员需要知道到底有多少条执行路径（即程序从开始到结束的路多少条执行路径（即程序从开始到结束的路线），以便知道需要提供多少个测试数据线），以便知道需要提供多少个测试数据. .一一般地，一个程序模块由许多子模块组成般地，一个程序模块由许多子模块组成. .如图如图所示是一个具有许多执行路径的程序模块所示是一个具有许多执行路径的程序模块. .（1 1）这个程序模块有多少条执行路径；）这个程序模块有多少条执行路径； （2 2）为了减少测试时间，程序员需要设法减）为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试少测试次数，你能帮助程序员设计一个测试方法，以减少测试次数吗？方法，以减少测试次数吗？开始开始子模块子模块1 11818条执行路径条执行路径子模块子模块5 54343条执行路径条执行路径子模块子模块4 43838条执行路径条执行路径子模块子模块3 32828条执行路径条执行路径子模块子模块2 24545条执行路径条执行路径结束结束A A73717371条条178178次次 例例5 5 随着人们生活水平的提高，某随着人们生活水平的提高，某城市家庭汽车拥有量迅速增长，汽车牌城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容照号码需要扩容. .交通管理部门出台了一交通管理部门出台了一种汽车牌照组成方法，每一个汽车牌照种汽车牌照组成方法，每一个汽车牌照都必须有都必须有3 3个不重复的英文字母和个不重复的英文字母和3 3个不个不重复的阿拉伯数字，并且重复的阿拉伯数字，并且3 3个字母必须合个字母必须合成一组出现，成一组出现，3 3个数字也必须合成一组出个数字也必须合成一组出现现. .那么这种办法共能给多少辆汽车上牌那么这种办法共能给多少辆汽车上牌照？照？共能给共能给22 464 00022 464 000辆汽车上牌照辆汽车上牌照. . 思考：思考： 如何计算集合如何计算集合A A a1 1，a2 2，an n 共有共有多少个子集？多少个子集？作业：作业：P10P10练习：练习：1 1，2 2，3 3，4.4.