11分类加法计数原理与分步乘法计数原理时.pptx

1.1分类计数原理分类计数原理与分步计数原理分步计数原理3huhu 2.如图如图,该电路该电路,从从A到到B共有多少条不同的线路共有多少条不同的线路可通电？可通电？AB在解题有时既要分类又要分步。在解题有时既要分类又要分步。解解:从总体上看由从总体上看由A到到B的通电线路可分三类的通电线路可分三类,第一类第一类,m1=3 条条 第二类第二类,m2=1 条条 第三类第三类,m3=22=4,条条 所以所以,根据分类原理根据分类原理,从从A到到B共有共有 N=3+1+4=8 条不同的线路可通电。条不同的线路可通电。例例 有架楼梯共有架楼梯共6 6级，每次只允许级，每次只允许上一级或两级，求上完这架楼梯共有上一级或两级，求上完这架楼梯共有多少种不同的走法？多少种不同的走法？第第1 1类：走类：走3 3步步第第2 2类：走类：走4 4步步第第3 3类：走类：走5 5步步第第4 4类：走类：走6 6步步1 1种走法种走法6 6种走法种走法5 5种走法种走法1 1种走法种走法N N1 16 65 51 11313（种）（种）例：在例：在1 1，2 2，3 3，200200这些自这些自然数中，各个数位上都不含数字然数中，各个数位上都不含数字8 8的的自然数共有多少个？自然数共有多少个？不含不含8 8的一位数的一位数不含不含8 8的二位数的二位数不含不含8 8的三位数的三位数8 8个个8 89=729=72个个9 99+1=829+1=82个个N N8 872728282162162（个）（个）例例8.计算机编程人员在编写好程序以后要对计算机编程人员在编写好程序以后要对程序进行测试。程序员需要知道到底有多少程序进行测试。程序员需要知道到底有多少条执行路（即程序从开始到结束的线），以条执行路（即程序从开始到结束的线），以便知道需要提供多少个测试数据。一般的，便知道需要提供多少个测试数据。一般的，一个程序模块又许多子模块组成，它的一个一个程序模块又许多子模块组成，它的一个具有许多执行路径的程序模块。问具有许多执行路径的程序模块。问：这个程：这个程序模块有多少条执行路径序模块有多少条执行路径？另外为了减少测？另外为了减少测试时间，程序员需要设法减少测试次数，你试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方式，以减少测能帮助程序员设计一个测试方式，以减少测试次数吗？试次数吗？开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A分析：分析：整个模块的任意一条整个模块的任意一条路径都分两步完成路径都分两步完成：第第1步是从开始执行到步是从开始执行到A点；点；第第2步是从步是从A点执行到结束。点执行到结束。第一步可由子模块第一步可由子模块1或子模或子模块块2或子模块或子模块3来完成；来完成；第二步可由子模块第二步可由子模块4或子模或子模块块5来完成。来完成。因此，分析一条指令在整个因此，分析一条指令在整个模块的执行路径需要用到两模块的执行路径需要用到两个计数原理。个计数原理。开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A解：由分类加法计数原理，子模块 1、2、3 中的子路径共有 18+45+28=91（条）;子模块 4、5 中的子路径共有38+43=81（条）.由分步乘法计数原理，整个模块的执行路径共有9181=7 371（条）.开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A2）在实际测试中，）在实际测试中，程序员总是把每一个程序员总是把每一个子模块看成一个黑子模块看成一个黑箱，即通过只考察是箱，即通过只考察是否执行了正确的子模否执行了正确的子模块的方式来测试整个块的方式来测试整个模块。这样，他可以模块。这样，他可以先分别单独测试先分别单独测试5个个模块，以考察每个子模块，以考察每个子模块的工作是否正常。模块的工作是否正常。总共需要的测试次数总共需要的测试次数为为：18+45+28+38+43=172。开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A再测试各个模块之间再测试各个模块之间的信息交流是否正的信息交流是否正常，即第一步的子模常，即第一步的子模块与第二步的子模块块与第二步的子模块是否正常，需要测试是否正常，需要测试的次数为：的次数为：3*2=6。如果每个子模块都正如果每个子模块都正常工作，并且各个子常工作，并且各个子模块之间的信息交流模块之间的信息交流也正常，那么整个程也正常，那么整个程序模块就正常。序模块就正常。这样，测试整个这样，测试整个模块的次数就变为模块的次数就变为 172+6=178（次）（次）用两个计数原理解决计数问题时，最重要的是在开始计算之前要进行仔细分析，需要分类还是需要分步分类要做到“不重不漏”分类后再分别对每一类进行计数，最后用分类加法计数原理求和，得到总数分步要做到“步骤完整”完成了所有步骤，恰好完成任务，当然步与步之间要相互独立分步后再计算每一步的方法数，最后根据分步乘法计数原理，把完成每一步的方法数相乘，得到总数练习练习1、乘积、乘积 展开后共有几项？展开后共有几项？2、某商场有、某商场有6个门，如果某人从其中的任意一个个门，如果某人从其中的任意一个门进入商场，并且要求从其他的门出去，共有多门进入商场，并且要求从其他的门出去，共有多少种不同的进出商场的方式？少种不同的进出商场的方式？