《分类加法计数原理与分步乘法计数原理时.pptx》由会员分享，可在线阅读，更多相关《分类加法计数原理与分步乘法计数原理时.pptx（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 2.如图,该电路,从A到B共有多少条不同的线路可通电？AB第1页/共34页第2页/共34页第3页/共34页第4页/共34页第5页/共34页第6页/共34页第7页/共34页第8页/共34页第9页/共34页第10页/共34页第11页/共34页第12页/共34页第13页/共34页第14页/共34页第15页/共34页第16页/共34页第17页/共34页第18页/共34页第19页/共34页在解题有时既要分类又要分步。解:从总体上看由A到B的通电线路可分三类,第一类,m1=3 条 第二类,m2=1 条 第三类,m3=22=4,条 所以,根据分类原理,从A到B共有 N=3+1+4=8 条不同的线路可通电。
2、第20页/共34页 例 有架楼梯共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（种）第21页/共34页 例：在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（个）第22页/共34页例8.计算机
3、编程人员在编写好程序以后要对程序进行测试。程序员需要知道到底有多少条执行路（即程序从开始到结束的线），以便知道需要提供多少个测试数据。一般的，一个程序模块又许多子模块组成，它的一个具有许多执行路径的程序模块。问：这个程序模块有多少条执行路径？另外为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方式，以减少测试次数吗？第23页/共34页开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A第24页/共34页开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块43
4、8条执行路径结束A分析：整个模块的任意一条路径都分两步完成：第1步是从开始执行到A点；第2步是从A点执行到结束。第一步可由子模块1或子模块2或子模块3来完成；第二步可由子模块4或子模块5来完成。因此，分析一条指令在整个模块的执行路径需要用到两个计数原理。第25页/共34页开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A解：由分类加法计数原理，子模块 1、2、3 中的子路径共有 18+45+28=91（条）;子模块 4、5 中的子路径共有38+43=81（条）.由分步乘法计数原理，整个模块的执行路径共有9181=7 371（
5、条）.第26页/共34页开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A2）在实际测试中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执行了正确的子模块的方式来测试整个模块。这样，他可以先分别单独测试5个模块，以考察每个子模块的工作是否正常。总共需要的测试次数为：18+45+28+38+43=172。第27页/共34页开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A再测试各个模块之间的信息交流是否正常，即第一步的子模块与第二步的子模块是否正常
6、，需要测试的次数为：3*2=6。如果每个子模块都正常工作，并且各个子模块之间的信息交流也正常，那么整个程序模块就正常。这样，测试整个模块的次数就变为 172+6=178（次）第28页/共34页第29页/共34页第30页/共34页第31页/共34页用两个计数原理解决计数问题时，最重要的是在开始计算之前要进行仔细分析，需要分类还是需要分步分类要做到“不重不漏”分类后再分别对每一类进行计数，最后用分类加法计数原理求和，得到总数分步要做到“步骤完整”完成了所有步骤，恰好完成任务，当然步与步之间要相互独立分步后再计算每一步的方法数，最后根据分步乘法计数原理，把完成每一步的方法数相乘，得到总数第32页/共34页练习1、乘积 展开后共有几项？2、某商场有6个门，如果某人从其中的任意一个门进入商场，并且要求从其他的门出去，共有多少种不同的进出商场的方式？第33页/共34页感谢您的观赏第34页/共34页