试题-全国-2019_三年级数学上册 竞赛 第5讲 字典排列法与树形图法（pdf，无答案） 新人教版.pdf

字典排列法与树形图法课本5字典排列法与树形图法在上一讲中我们学习了简单的枚举法——直接把所有情况一一列举出来．但如果问题较为复杂，直接枚举很有可能产生重复或者遗漏，这时就需要有一些特别的方法来帮助我们枚举出所有情况．本讲就主要介绍两种枚举的方法：字典排列法和树形图法．同学们可以翻一下英汉字典，不难发现字典中单词排列的规律：整本字典按首字母从a到z排列，首字母相同的单词都在一起．在首字母相同的单词中，再按照第2个字母从a到z的顺序排列，然后是第3个字母，第4个字母，⋯⋯所谓“字典排列法”，就是指在枚举时，像字典里的单词顺序那样排列出所有答案．例如，用1、2、3各一次可以组成多少个不同的三位数？用字典排列法枚举时，每个位置都按从小到大排列，枚举的顺序是：123，132，213，231，312，321．下面我们用字典排列法来解决几个问题．25三年级上册第5讲例题1卡莉娅、墨莫、小高三个人去游乐园玩，三人在藏宝屋中一共发现了5件宝物，三人找到的宝物数量共有多少种不同的可能？（可以有人没有发现宝物）分析每个人最少找到几件宝物？最多呢？练习1.老师准备了6个笔记本奖励萱萱、小高和墨莫三人，每人至少得到1本笔记本．请问：老师有多少种不同的奖励方法？字典是如何排序的？ 在英语词典中，两个单词的位置是这样决定的：从第一个字母开始比较，如果相同，那么就看下一个字母；如果不同，那么就按照从a到z的顺序进行排列．比如说：book和look这两个单词，第一个字母分别是b和l，b排在l前面，所以book排在look之前．再比如说：book和boat这两个单词，前两个字母都是bo，所以就看第三个字母，o在a之后，所以词典里book出现在boat之后．再来看看中文字典，现在的中文字典主要采用的都是按拼音字母的顺序进行排序，方法与英语字典相同．其实在使用拼音之前我国古代的字典一般都是按照部首以及笔画来排序的，比如著名的《康熙字典》就是这样排序的：先按部首排序，每个部首之中再按剩下的笔画数从少到多进行排序．中文字典除了按拼音、部首等顺序排列之外，还有四角号码、笔顺等多种排序方法．例题2老师要求每个同学写出3个自然数，并且要求这3个数的和是8．如果两个同学写出的3个自然数相同，只是顺序不一样，则算是同一种写法．请问：同学们最多能得出多少种不同的写法？分析注意顺序不同算一种写法，也就是三个数分别为（1、2、5）、（2、5、1）和（5、26字典排列法与树形图法课本1、2）都算同一种写法．练习2.三个大于0的整数之和（数与数可以相同）等于10，共有多少组这样的三个数？在上一讲中说过，对于枚举法而言，问题到底是“有顺序”还是“无顺序”非常关键，在使用字典排列法时也是这样．往往题目要求“有顺序”，那么枚举的每个结果里就没有明确的顺序关系；而题目要求“无顺序”，那么枚举时要注意每个结果中应该都符合一定的顺序关系．例如：例题2中要求说交换顺序算同一种写法，所以题目要求是“无顺序”的．那么在枚举的时候就要把数从小到大排列顺序，也就是第二个数不会比第一个数小，第三个不会比第二个数小．当然，有些题目还会在基本的枚举中加上一些限制条件，做题时不要忘了这些限制条件．例题3商店里有12种不同的签字笔，价格分别是1、2、3、4、5、⋯、11、12元．卡莉娅准备买3支不同价钱的签字笔，并且希望恰好花掉15元．请问：卡莉娅一共有多少种不同的买法？分析买笔的顺序不同有没有区别呢？依次买1元、5元、9元的笔和买9元、5元、1元的笔最后结果有区别吗？练习3.3个互不相同的自然数之和为8，一共有多少种不同的可能？对于一个数的分拆，经常使用字典排列法，而如果是对某件事情过程的枚举，一般会使用另一种方法：树形图法．所谓树形图法就是用像树一样的、不断分叉的图来表示出所有情况的方法．27三年级上册第5讲画树形图与一棵树的生长过程类似，先从“树根”开始，然后不断长出新的“树枝”，每次长出新的“树枝”时都有可能产生分叉，最后长满了“叶子”．这样一直下去把所有情况都画完，最后数一下“叶子”的数目即可．例题4王老师有一个带密码锁的公文包，但是他忘记了密码．只记得密码是一个三位数．这个三位数的个位数字比十位数字大，十位数字比百位数字大，并且没有比5大的数字．试问：王老师最多需要试多少次就肯定能打开这个公文包？分析百位数字最小，有几种情况？把这些情况分别作为“树根”，画出树形图．练习4.一个三位数，百位比十位大，十位比个位大，个位不小于5，那么这样的三位数一共有几个？例题5常昊与古力两人进行围棋赛，谁先胜三局就赢得比赛．如果最后常昊获胜了，那么比赛的进程有多少种可能？分析试着把每场比赛的结果用树形图表示出来．注意：不会有古——常——古——古——常——常这样的过程出现，因为在这种情况下，赛完第4场后古力已经获胜，不符合题意．