洋葱头历险记-革命先烈的故事

枚举法中的字典排列

如果我把这三个东西都带回去,
天吃
1
个，还可以再吃
3
天呢？
我明天先吃什么呢？先吃汉堡，不不，还
但如果问题较为复杂，直
是先吃玉米，哎，还是先吃
饼干吧！到底 先吃什么呢？共有多少种不
同的吃法？
基础例题:
在上一讲中我们学习了简单的枚举法一一直接把所有情况一一列举出来.
接枚举很有可能产生重复或者遗漏， 这时就需要有一些特别的方法来帮助我们枚举出所有情况.
本讲就

主要介绍两种枚举的方法：字典排列法和树形图法.









同学们可以翻一下英汉字典，不难发现字典中单词排列的规律：整本字典按首字母从
首字母相同的单词都在一起 在首字母相同的单词中,
再按照第
2
个字母从
a
到
z
的顺序排列,
a
到
z
排列,
然后是

个字母，第
4
个字母
所谓“字典排列法” ，就是指在枚举时，像字典里的单词顺序那样排列出
3
各一次可以组成多少个不同的三位数？用字典排列法枚举时，每个位置都勒*
123
,
132
,
213
,
231
,
312
,
321
.下面我们用字典排列法来解决几个

按从小到大排列，枚举的顺序是：
问题.
例题
1
.卡莉娅、墨莫、小高三个人去游乐园玩，三人在藏宝屋中一共发现了
的宝物数量共有多少种不同的可能？（可能有人没有发现宝物）
分析：每个人最少找到几件宝物？最多呢？
5
件宝物，三人找到
练习：
1.
老师准备了
6
个笔记本奖励萱萱、小高和墨莫三人，每人至少得到
多少种不同的奖励方法？
1
本笔记本，请问：老师有
例题
2
•老师要求每个同学写出
3
个自然数，并且要求这
3
个数的和是
8
•如果两个同学写出的
3
个自然数相 同，只是顺序不一
样，则算是同一种写法•试问：同学们最多能得出多少种不同的写法？
分析：注意顺序不同算一种写法，也就是三个数分别为（
算同一种写法.
1
、
2
、
5
）、（
2
、
5
、
1
）和（
5
、
1
、
2
）都
练习：
2.
三个大于
0
的整数之和（数与数可以相同）等于
10
，共有多少组这样的三个数?
用字典排序法枚举的时候，判断题目要求到底是“交换顺序后算作两种”还是“交换顺序后仍然是 同一种”非常关键•往往题目中
要求“交换顺序后仍然是同一种” ，那么枚举的每个结果里就没有明确
的顺序关系；反之，那么枚举时要注意每个结果中应该都符合一定的顺序关系.
在求解计数问题时，审题非常关键•往往一字之差就会有天壤之别.
枚举法是解决计数问题的基础，但是对于比较复杂的问题，如果直接枚举很容易出现重复或者遗
漏.这时就需要预先把所有情形分成若干小类，针对每一小类进行枚举.
例题3
如 下图所示，有7个按键，上面分别写着：1、2、3、4、5、6、7这七个数字
•
请
问：
（1）从中选出2个按键，使它们上面的数字的差等于2, 一共有多少种选法？
ftp f
1ft 0

(2)从中选出2个按键，使它们上面的数字的和大于

9,
一共有多少种选法
分析：第二问中的和大于
9
是什么意思？也就是最小等于
10
，那最大又是多少？和共有几种可能?
练习
3
有一次，著名的探险家大米得到一个宝箱，但是宝箱有密码锁，密码锁下边有一行小字：
密码 是和大于
11
的两个数，而且这两个数不能相同
•
不用考虑数的先后顺序，你 知道密码 共有多少种可能吗？



例题4
数一数下图中包含星星的长方形(包括正方形)有多少个?



☆
分析：含星星的长方形会由几个小方格组成呢？我们可以依据长方形的种类进行分类.
练习
4
数一数下图中包含星星的正方形有多少个？


☆




在分类时，一定注意类与类之间有没有重复的部分，
到“不重不漏”的前提下，才能够进行进一步的枚举.
或者还有没有漏掉的情况. 只有在分类已经做
例题5
妈妈买来7个鸡蛋，每天至少吃2个，吃完为止.如果天数不限.可能的吃法

多少种?
分析：虽然题目对天数没有限制，但要求每天至少吃
2
个•照此推算，最多能吃几天?
例题6
午餐的时候，食堂为同学们准备了苹果、桃子和桔子三种水果，每种
都有很
多.东东想要挑3个水果吃.请问东东有多少种不同的选法？
分析：仔细审题，挑的
3
个水果能不能是同种的水果？若要分类枚举，应该如何分类呢？
课堂内外
字典是如何排序的？
在英语字典中，两个单词的位置是这样决定的：从第一个字母开始比较，
如果相同，那么就看下一个字母；如果不同，那么就按照从
排列.比如说：
book
和
look
这两个单词，第一个字母分别是
a
到
z
的顺序进行
b
和
I
，
b
排在
I
前面，所以
book
排在
look
之前.再比如说：
book
和
boa t
这两个单词，前两个 字母都是
bo
，所
以就看第三个字母，
o< br>在
a
之后，所以字典里
book
出现在
boat
之后.
再来看看中文字典，现在的中文字典主要采用的都是按拼音字母的顺序进
行排序，方法与英语字典相同.其实在使用拼音之前我国古代的字典一般都是 按照部首以及笔画来
排序的，比如著名的《康熙字典》就是这样排序的：先按 部首排序，每个部首之中再按剩下的笔
画数从少到多进行排序.中文字典除了 按拼音、部首等顺序排列之外，还有四角号码、笔顺等多种
排序方法.

作业
1
2
4
支完全相同的铅笔要分给
3
位同学，每位同学至少分
1
支，共有多少种不同的分法?
有面值分别为
1
元、
10
元和
50
元的纸币若
任取
3
张，那么能组成的钱数共有多少种?
每种面值的纸币张数都大于
3
.如果从中
3
老师要求墨莫写
4
篇作文，题目不限，但是每天至少写
多少种不同的可能?
1
篇
那么墨莫完成这些作文共有
4
爷爷要墨莫多吃水果，于是给了他
一共有多少不同的吃法?
8
个苹果，要求每天至少吃
2
个，吃完为止.那么墨莫
5
体育馆里有很多足球和篮球，体育老师要小高从里面拿
4
个
择
？
请问小高有多少种不同的选
(7^

第二讲 枚举法中的字典排列
1.
例题
1
答案：
21
种
详解：按照字典排列法， 依次枚举卡莉娅、 墨莫和小高三人所找到的宝物数量， 由于每人最少 找到
0
件宝物，最
多找到
5
件，所以按（卡莉娅、墨莫、小高）的形式枚举出： （
0
、
0
、
5
）,
（0
、
1
、
4
） ,
5
、
0
） , （
1
、
0
、
4
）,
（
0
、
2
、
3
）, （
0
、
3
、
2
） , （
0
、
4
、
1
） , （
0
、
（
1
、
1
、
3
） , （
1
、
2
、
2
）, （
1
、
3
、
1
）, （
1
、
4
、
0
）, （
2
、
0
、
3
）, （
2
、
1
、
2
）, （
2
、
2
、
1
）, （
2
、
3
、
0
）, （
3
、
0
、
2
）,
（
3
、
1
、
1
）, （
3
、
2
、
0
）, （
4
、
0
、
1
）, （
4
、
1
、
0
）, （
5
、
0
、
0
）,共有
21
种不同的可能.
2.
例题
2
答案：
排

10
:
种
详解：由于题目要求三个数顺序不同算作同一种方法，
的 情 况 •用 字 典
所以在枚举时只需要考虑从小到大排列
列 法 不 难 得 到
8 0 0 8

0 1 7 0 2 6 0 3 5


0 4


4
1 1


6 1


2 5 13 4 2


2 4 2 3 3
，共有
10
:申不同的可能.
种
3.
例题
3
答案：
（1
5
种；（
2
）
6
种


（

1
7
和
5
,
6
和
4
,
5
和
3
,
详解：
）
）
（

2
和
6
•
）
例题
4
答案：
12
个
4
和
2
,
3
和
1
；

和为
10
：
7
和
3
,
6
和
4
;和为
11
：
7
和
4,（
6
和
5
；
和为
12
：
7
和
5
；
和为
13
：
7
4.
详解：按长方形的大小分类•一格的有
1
个，两格的有
3< br>个，三格的有
2
个，四格的有
3
个,
六格的有
2
个，八格的有
1
个•共有
1 3 2 3 2 1 12
个.
5.
例题
5
答案：
8
种 详解：天数最多
3
天•按天数分类•吃
1
天的有
1
种， 吃
2
天的有
4
种，吃
3
天的有
3
种•共 有
1 4 3 8
种.
6.
例题
6
答案：
10
种
详解：
3
个水果既可以同种，也可以不同种•因此可按所选水果的种类数量进行分类：
（
1
）只选
1
种水果：全苹果、全桃子、全桔子，共
个桃子、
2
个桃子
1
个桔子，共
6
种情况；
（
3
）
3
种水果都选：每种水果各
1
个，共
1
种情况. 综上所述，共有
3 6 1 10
种情况.
3
种情况；
（
2
）选
2
种水果：
2
个苹果
1
个桃子、
2
个桃子
1
个苹果、
2
个苹果
1
个桔子、
2
个桔子
1
个 苹果、
2
个桔子
1
7.
练习
1
答案：
10
种
简答：每人至少
1
本，人与人不同，所以是“有顺序”的问题，枚举可得共有
励方法.
10
种不同的奖
8.
练习
2
答案：
8
种
简答：题目要求是
3
个大于
0
的数组成一组，也就是“无顺序”，在枚举时要注意前后的大小 关系，共
8
种.
9.
练习
3

简答：按正方形的大小分类.一格的有
个.共有
14 4 1
1
个，四格的有
4
个，九格的有
4
个，十六格的有1
10
个.
11.
作业
1
答案：
3
种
简答：（
2
、
1
、
1
） （
1
、
2
、
1
） （
1
、
1
、
2
）;共
3
种.
12.
作业
2
答案：
10
种
简答：按取出的钱所含的面值种数分类，可能是
1
种面值，也可能是
2
种面值，也可能是
3
种面值.
3
类情形加起来
共有
10
种可能.
13.
作业
3
答案：
8
种
简答：根据天数分 类.
1
天、
2
天、
3
天、
4
天完成分别有 ：
1
、
3
、
3
、
1
种情况，共
8
种可能.
14.
作业
4
答案：
13
种
简答：按吃完的天数分类，分为
情况，共
13
种不同的情况.
4
类：
1
天、
2
天、
3
天、
4
天. 这四类分别有
1
、
5
、
6
、
1
种
15.
作业
5
答案：
5
种
简答：按取出的球的种类数量进行考虑：取出的球可能有
共有
5
种不同选择.
1
种或
2
种.分上述
2
类进行枚举，