分类计数原理与分步计数原理[整理]

《分类计数原理与分步计数原理[整理]》由会员分享，可在线阅读，更多相关《分类计数原理与分步计数原理[整理]（18页珍藏版）》请在金锄头文库上搜索。

1、 卡斯帕罗夫：卡斯帕罗夫：俄罗斯人，国际象棋棋手，世界顶尖俄罗斯人，国际象棋棋手，世界顶尖高手，纵横国际棋坛二十余年，无人能敌。高手，纵横国际棋坛二十余年，无人能敌。 但但19971997年年5 5月月1111日，日，卡斯帕罗夫卡斯帕罗夫在美国纽约与在美国纽约与“深蓝深蓝”（IBM IBM 公司公司超级计算机超级计算机）之间的）之间的“最后决战最后决战” ” 中以中以3.53.5比比2.52.5的总的总比分比分告负告负！分类计数原理与分步分类计数原理与分步计数原理计数原理224325问题问题1、西部某省的贫困生，由于家庭经济原因，午饭只能买、西部某省的贫困生，由于家庭经济原因，午饭只能买 一盘

2、菜一盘菜，学校食堂的菜单如下，请问有多少种不同的选法。，学校食堂的菜单如下，请问有多少种不同的选法。 萝卜花菜蔬菜类蔬菜类牛肉猪肉总总 数数肉肉 类类( 菜单菜单1 )菜的种类菜的种类 菜的样式菜的样式每类数量每类数量(菜单菜单 2 ) 萝卜花菜蔬蔬 菜类菜类牛肉猪肉总数总数肉肉 类类白菜 菜的种类菜的种类 菜的样式菜的样式 每类每类 数量数量问：对比两个表格你能得到问：对比两个表格你能得到每类数量每类数量与与总数总数间的关系？间的关系？问题问题1、西部某省的贫困生，由于家庭经济原因，午饭只能买西部某省的贫困生，由于家庭经济原因，午饭只能买 一盘菜一盘菜，学校食堂的菜单如下，请问有多少种不同的

3、选法。，学校食堂的菜单如下，请问有多少种不同的选法。菜汤菜汤羊肉羊肉竹笋竹笋豆汤豆汤蛋汤蛋汤第第 n 类类每类数量菜的样式菜的种类萝卜萝卜花菜花菜第第 1 类类牛肉牛肉猪肉猪肉总总 数数第第 2 类类 菜菜 单单 4mnm1m2m1 + m2 + + mn羊肉羊肉竹笋竹笋每类数量菜的样式菜的种类萝卜萝卜花菜花菜蔬菜类蔬菜类牛肉牛肉猪肉猪肉总总 数数肉肉 类类( 菜单菜单3 )m1m2m1+m2 分类计数原理：分类计数原理： 完完成成一一件件事事情情，有有 n 类类办办法法，在在第第1类类办办法法中中有有m1种种不不同同的的方方法法，在在第第2类类办办法法中中有有m2种种不不同同的的方方法法在在

4、第第n类类办办法法中中有有mn种种不不同同的的方方法法.那那么么完成这件事共有完成这件事共有 N=m1 + m2 + + mn 种不同的方法种不同的方法.（又称加法原理）（又称加法原理）问题问题2、国务院总理温家宝在十届全国人大三次会议上作政府工国务院总理温家宝在十届全国人大三次会议上作政府工作报告时表示，补助贫困学生生活费。假设补助后西部某省的贫作报告时表示，补助贫困学生生活费。假设补助后西部某省的贫困生午饭可买困生午饭可买两盘菜两盘菜（蔬菜类蔬菜类 + 肉类肉类），学校食堂的菜单如下表，），学校食堂的菜单如下表，请问有多少种不同的选法。请问有多少种不同的选法。 萝卜花菜蔬菜类蔬菜类牛肉猪肉

5、总总 数数肉肉 类类( 菜单菜单1 )菜的种类菜的种类菜的样式菜的样式每类数量每类数量所有选法所有选法花菜 + 猪肉花菜 + 牛肉萝卜 + 猪肉萝卜 + 牛肉224(菜单菜单 2 ) 萝卜花菜蔬蔬 菜类菜类牛肉猪肉总数总数肉肉 类类白菜 菜的种类菜的种类菜的样式菜的样式每类数量每类数量326所有选法所有选法花菜 + 猪肉花菜 + 牛肉萝卜 + 猪肉萝卜 + 牛肉白菜 + 牛肉白菜 + 猪肉 变题变题1、 国务院总理温家宝在十届全国人大三次会议上作政府国务院总理温家宝在十届全国人大三次会议上作政府工作报告时表示，补助贫困学生生活费。假设补助后西部某省的工作报告时表示，补助贫困学生生活费。假设补助

6、后西部某省的贫困生午饭可买贫困生午饭可买 两盘菜两盘菜 （蔬菜类蔬菜类 + 肉类肉类），）， 学校食堂学校食堂的菜单如下表，请问有多少种不同的选法。的菜单如下表，请问有多少种不同的选法。豆汤豆汤蛋汤蛋汤汤类汤类每类数量每类数量菜的样式菜的样式菜的种类菜的种类 萝卜 青菜蔬蔬 菜类菜类 猪肉总数总数肉肉 类类(菜单菜单 3)三盘菜三盘菜(蔬菜类蔬菜类 + 肉类肉类 + 汤类汤类), 2124请同学们对菜单进行大胆的扩展。请同学们对菜单进行大胆的扩展。菜汤菜汤羊肉羊肉竹笋竹笋mn豆汤豆汤蛋汤蛋汤第第 n 类类每类数量蔬菜样式蔬菜类型m1萝卜萝卜青菜青菜第第 1 类类m2牛肉牛肉猪肉猪肉总总 数数第

7、第 2 类类 变题变题2、 国务院总理温家宝在十届全国人大三次会议上作政府国务院总理温家宝在十届全国人大三次会议上作政府工作报告时表示，补助贫困学生生活费。假设补助后西部某省的工作报告时表示，补助贫困学生生活费。假设补助后西部某省的贫困生午饭可买贫困生午饭可买 n 盘菜盘菜（每类每类 1 盘盘），）， 学校食堂的菜单如下表，学校食堂的菜单如下表，请问有多少种不同的选法。请问有多少种不同的选法。m1m2mn完完成成一一件件事事情情，需需要要分分成成n个个步步骤骤，做做第第1步步有有m1种种不不同同的的方方法法，做做第第2步步有有 m2 种种不不同同的的方方法法做第做第 n 步有步有 mn 种不同

8、的方法种不同的方法.那么完成这件事共有那么完成这件事共有N = m1 m2 mn种不同的方法种不同的方法.分步计数原理分步计数原理: （又称乘法原理）例例 题题1.1.填空：填空：一一件件工工作作可可以以用用2 2种种方方法法完完成成，有有 5 5 人人会会用用第第1 1种种方方法法完完成成， 另另有有4 4人人会会用用第第2 2种种方方法法完完成成， 从从中中选选出出1 1人来完成这件工作，不同选法的种数是人来完成这件工作，不同选法的种数是 . .从从A A村去村去B B村的道路有村的道路有3 3条，从条，从B B村去村去C C村的道路有村的道路有2 2条，条，从从A A村经村经B B村去村

9、去C C村，不同的路线有村，不同的路线有 条条. .4 （针对的是针对的是“分类分类”问题问题） 用其中任何一种方法均可独立完成这件事。用其中任何一种方法均可独立完成这件事。 分类计数原理：分类计数原理： 各类的方法间关系是相互独立。各类的方法间关系是相互独立。 同一类中的各种方法也是相对独立。同一类中的各种方法也是相对独立。（针对的是针对的是“分步分步”问题问题）分步计数原理：分步计数原理： 各个步骤中的方法相互依存。各个步骤中的方法相互依存。 只有各个步骤都完成，才算完成这件事。只有各个步骤都完成，才算完成这件事。注意：注意： 完成的事件是什么！完成的事件是什么！原理的选择。原理的选择。例

10、例2.2.书架的书架的第第1 1层层放有放有4 4本不同的计算机书，本不同的计算机书，第第2 2层层放有放有3 3本本 不同的文艺书，不同的文艺书，第第3 3层层放有放有2 2本不同的体育书。本不同的体育书。 （1 1）从书架上任取）从书架上任取1 1本书，有多少种不同的取法本书，有多少种不同的取法? ?（2 2）从书架的第）从书架的第1 1、2 2、3 3层层各各取取1 1本不同的书，有多少种不同本不同的书，有多少种不同 的取法？的取法？ 解：解：（1）从书架上任取）从书架上任取1本书，有本书，有3类办法：类办法： （2）从书架的第）从书架的第1、2、3层各取层各取1本书，可分本书，可分3个

11、步骤完成：个步骤完成：第第1类办法是从第类办法是从第1层取层取1本计算机书，有本计算机书，有4种办法；种办法；第第2类办法是从第类办法是从第2层取层取1本文艺书，有本文艺书，有3种办法；种办法；第第3类办法是从第类办法是从第3层取层取1本体育书，有本体育书，有2种办法；种办法；根据分类计数原理，不同取法的种数是根据分类计数原理，不同取法的种数是 N=4+3+2=9答：从书架上任取1本书，有9种不同的取法。第第1步从第步从第1层取层取1本计算机书，有本计算机书，有4种办法；种办法；第第2步从第步从第2层取层取1本文艺书，有本文艺书，有3种办法；种办法；第第3步从第步从第3层取层取1本体育书，有本

12、体育书，有2种办法；种办法；第第3步从第步从第3层取层取1本体育书，有本体育书，有2种办法；种办法；根据分步计数原理，不同取法的种数是根据分步计数原理，不同取法的种数是 N=432=24答：从书架的第1、2、3层各取1本书，有24种不同的取法。练习练习. 3、 国务院总理温家宝在十届全国人大三次会议上作政府工作报国务院总理温家宝在十届全国人大三次会议上作政府工作报告时表示，补助贫困学生生活费。假设补助后西部某省的贫困生告时表示，补助贫困学生生活费。假设补助后西部某省的贫困生午饭可买午饭可买 两盘菜两盘菜（蔬菜类蔬菜类 + 肉类肉类），）， 学校食堂的菜单如学校食堂的菜单如下表，请问有下表，请问

13、有 种不同的选法。种不同的选法。问：在菜单不变的前提下，尝试在蓝色方框内给出一个条件，问：在菜单不变的前提下，尝试在蓝色方框内给出一个条件， 给出一个新题给出一个新题!豆汤豆汤蛋汤蛋汤汤类汤类菜的样式菜的样式菜的种类菜的种类 萝卜 花菜蔬蔬 菜类菜类猪肉肉肉 类类( 菜单菜单 )白菜 两个思想两个思想:两个原理：两个原理：课课 堂堂 小小 结结特殊到一般、分类讨论。特殊到一般、分类讨论。分类计数原理、分步计数原理分类计数原理、分步计数原理课外作业课外作业 1课本第课本第87页的习题页的习题10.1第第1，3题题马马炮炮炮炮卒卒图1图2探究：探究：1、图、图1中中, “红马红马” 在最少在最少步

14、数内吃到步数内吃到“兰炮兰炮”的的不同方法数有几种不同方法数有几种?2、图、图2中中“兰炮兰炮”在兰色在兰色区域内且在区域内且在4步之内吃到步之内吃到“红马红马”的不同方法数有的不同方法数有几种？几种？马马谢谢 谢谢 ！例例3、一种号码锁有、一种号码锁有4个拨号盘，每个拨号盘上有从个拨号盘，每个拨号盘上有从0到到9共共10个数字，这个数字，这4个拨号盘可以组成多少个个拨号盘可以组成多少个四位数字四位数字号码号码?解：由于号码锁的每个拨号盘有从解：由于号码锁的每个拨号盘有从0到到9这这10个数字，每个拨号个数字，每个拨号盘上的数字有盘上的数字有10种取法。根据分步计数原理，种取法。根据分步计数原理，4个拨号盘上各取个拨号盘上各取1个数字组成的四位数字号码的个数是个数字组成的四位数字号码的个数是 N=10101010=10000 答：可以组成答：可以组成10000个四们数字号码。个四们数字号码。