加法原理之树形图及标数法(三)教师版
cad2007中文版-广西分数线
7-1-3.加法原理之树形图及标数法
教学目标
1.使学生掌握加法原理的基本内容;
2.掌握加法原理的运用以及与乘法原理的区别;
3.培养学生分类讨论问题的能力,了解分类的主要方法和遵循的主要原则.
加法原理的数学
思想主旨在于分类讨论问题,教授本讲的目的也是为了培养学生分类讨论问题的习惯,锻
炼思维的周全细
致.
知识要点
一、加法原理概念引入
生活中常有这样的情况,就是在
做一件事时,有几类不同的方法,而每一类方法中,又有几种可能的做
法.那么,考虑完成这件事所有可
能的做法,就要用加法原理来解决.
例如:王老师从北京到天津,他可以乘火车也可以乘长途汽车,现
在知道每天有五次火车从北京到天津,
有4趟长途汽车从北京到天津.那么他在一天中去天津能有多少种
不同的走法?
分析这个问题发现,王老师去天津要么乘火车,要么乘长途汽车,有这两大类走法,如果
乘火车,有5
种走法,如果乘长途汽车,有4种走法.上面的每一种走法都可以从北京到天津,故共有5
+4=9种不同的走
法.
在上面的问题中,完成一件事有两大类不同的方法.在具体做的时候
,只要采用一类中的一种方法就可
以完成.并且两大类方法是互无影响的,那么完成这件事的全部做法数
就是用第一类的方法数加上第二类的
方法数.
二、加法原理的定义
一般地,如果完
成一件事有k类方法,第一类方法中有
m
1
种不同做法,第二类方法中有
m<
br>2
种不同做法,…,
第k类方法中有
m
k
种不同做法,则完成
这件事共有
N m
1
m
2
……m
k
种不同方法,这就是加法原理.
加法原理运用的
范围:完成一件事的方法分成几类,每一类中的任何一种方法都能完成任务,这样的问
题可以使用加法原
理解决.我们可以简记为:“加法分类,类类独立”.
分类时,首先要根据问题的特点确定一个适合于
它的分类标准,然后在这个标准下进行分类;其次,分
类时要注意满足两条基本原则:
①
完成这件事的任何一种方法必须属于某一类;
② 分别属于不同两类的两种方法是不同的方法.
只有满足这两条基本原则,才可以保证分类计数原理计算正确.
运用加法原理解题时,关键是
确定分类的标准,然后再针对各类逐一计数.通俗地说,就是“整体等于局
部之和”.
三、加法原理解题三部曲
1、完成一件事分N类;
2、每类找种数(每类的一种情况必须是能完成该件事);
3、类类相加
枚举法:枚举法又叫穷举法,就是把所有符合条件的对象一一列举出来进行计数.
分类讨论的
时候经常会需要把每一类的情况全部列举出来,这时的方法就是枚举法.枚举的时候要注意
顺序,这样才
能做到不重不漏.
例题精讲
模块一、树形图法
“树形图法”实际上是枚举的一种,但是它借助
于图形,可以使枚举过程不仅形象直观,而且有条理又不
重复遗漏,使人一目了然.
【例 1】 A、B、C三个小朋友互相传球,先从A开始发球(作为第一次传球),这样经过了5次传
球后,球恰
巧又回到A手中,那么不同的传球方式共多少种?
【考点】加法原理之树形图法
【难度】3星 【题型】解答
【关键词】2005年,小数报
【解析】
如图,
A
第一次传给
B
,到第五次传回
A
有5种不同方式.
同理,
A
第一次传给
C
,也有5种不同方式.
所以,根据加法原理,不同的传球方式共有
5510
种. B
A
AB
A
C
B
C
C
B
B<
br>C
C
A
【答案】
10
【巩固】 一只青
蛙在A,B,C三点之间跳动,若青蛙从A点跳起,跳4次仍回到A点,则这只青蛙一共有
多少种不同的
跳法?
【考点】加法原理之树形图法 【难度】3星
【题型】解答
【解析】 6种,如图,第1步跳到
B
,4步回到
A
有3种方法;同样第1步到
C
的也有3种方法.根据加法原
理,共有
33
6
种方法.
B
A
AB
C
C
B
A
A
A
【答案】
6
【例 2】 甲、乙二人打乒乓球,谁先
连胜两局谁赢,若没有人连胜头两局,则谁先胜三局谁赢,打到决出输
赢为止.问:一共有多少种可能的
情况?
【考点】加法原理之树形图法 【难度】3星
【题型】解答
【解析】 如下图,我们先考虑甲胜第一局的情况:
图中打√的为胜者,一共有7种可能的情况.同理,乙胜第一局也有 7种可能的情况.一共有
7+
7=14(种)可能的情况.
【答案】
14
【例
3】 如图,从起点走到终点,要求取出每个站点上的旗子,并且每个站点只允许通过一次,有
种不同
的走法。
起点
终点
【考点】加法原理之树形图法 【难度】3星 【题型】填空
【关键词】2009年,希望杯,第七届,五年级,一试,第3题
【解析】
给这些点依次标上字母(如左图),然后采用枚举法(如右图):
bd
d
b
c
d
e
e
d
e
f
f
f
f
a
f
a
ce
c
e
c
bd
共4种不同的走法。
【答案】
4
种
模块二、标数法
适用于最短路线问题,需要一步一步标出所有相关点
的线路数量,最终得到到达终点的方法总数.标数
法是加法原理与递推思想的结合.
(一)简单图形的标数法
【例 4】
如图所示,沿线段从A到B有多少条最短路线?
1
3
2
1
63
1
10
4
1
E
C
F
B
1<
br>B
D
G
A
【考点】加法原理之标数法
【难度】2星 【题型】解答
【解析】 图中
B
在A的右上方
,因此从A出发,只能向上或者向右才能使路线最短,那么反过来想,如果到
达了某一个点,也只有两种
可能:要么是从这个点左边的点来的,要么是从这个点下边的点来的.那
么,如果最后到达了B,只有两
种可能:或者经过C来到B点,或者经D来到B点,因此,到达B
的走法数目就应该是到达C点的走法数
和到达D点的走法数之和,而对于到达C的走法,又等于到
达
E
和到达
F的走法之和,到达
D
的走法也等于到达
F
和到达
G
的走
法之和,这样我们就归纳出:
到达任何一点的走法都等于到它左侧点走法数与到它下侧点走法数之和,根
据加法原理,我们可以
从
A
点开始,向右向上逐步求出到达各点的走法数.如图所示,
使用标号方法得到从
A
到
B
共有10
种不同的走法.
【答案】
10
【巩固】
如图,从
A
点到
B
点的最近路线有多少条?
B
1
1
1
4
3
2
10
6
3
20
10
4
A
B
111
A
A
【考点】加法原理之标数法 【难度】2星
【题型】解答
【解析】 使用标号法得出到
B
点的最近路线有20条.
【答案】
20
【例 5】 如图,某城市的街道由5条东西向马
路和7条南北向马路组成,现在要从西南角的
A
处沿最短的路
线走到东北角
B
出,由于修路,十字路口
C
不能通过,那么共有____种不同走法.
B
1
1
1
1
A
B
51535
55
81
120
4
10
202026
39
3610C
613
2
3
4567
C
A
1
1
1
11
1
【考点】加法原理之标数法 【难度】3星 【题型】解答
【解析】 本题是最短路线问题.要找出共有多少 种不同走法,关键是保证不重也不漏,一般采用标数法.如
上图所示,共有120种.
另解: 本题也可采用排除法.由于不能经过
C
,可以先计算出从
A
到
B的最短路线有多少条,再去
掉其中那些经过
C
的路线数,即得到所求的结果. < br>对于从
A
到
B
的每一条最短路线,需要向右6次,向上4次,共有10 次向右或向上;而对于每一条
最短路线,如果确定了其中的某6次是向右的,那么剩下的4次只能是向上 的,从而该路线也就确
6
定了.这就说明从
A
到
B
的最短路 线的条数等于从10次向右或向上里面选择6次向右的种数,为
C
10
.
m
一般地,对于
mn
的方格网,相对的两个顶点之间的最短路线有
C
mn
种.
6
本题中,从
A
到
B
的最短路线共有
C
10
种;从
A
到
C
的最短路线共有
C< br>6
2
种,从
C
到
B
的最短路线共
2
有
C
4
2
种,根据乘法原理,从
A
到
B
且 必须经过
C
的最短路线有
C
6
2
C
4
种 ,所以,从
A
到
B
且不经
62
C
6
2< br>C
4
21090120
种. 过
C
的最短路线有
C
10
【答案】
120
【例 6】 如图所示,从A点到B点,如果要求经过C点或D点的最近路线有多少条?
【考点】加法原理之标数法 【难度】3星 【题型】解答
【解析】 1、方格图里两点的最短路径,从位置低的点向位置高的点出发的话,每到 一点(如C、D点)只能
向前或者向上.
2、题问的是经过C点,或者D点;那么A到B点就可以分成两条路径了 A--C---B;A--- D---B,那
么也就可以分成两类.但是需要考虑一个问题——A到B点的最短路径会同时经过C和D 点吗?最
短路径只能往上往前,经过观察发现C、D不会同时出现在最短路径上了.
3、A ---C---B,那么C就是必经之点了,就需要用到乘法原理了.A--- C,最短路径用标数法标出,
同样C---B点用标数法标注,然后相乘
A---D--- B,同样道理.最后结果是735+420=1155条.
【答案】
1155
【例 7】 如图
1
为一幅街道图,从
A
出发经过十字路 口
B
,但不经过
C
走到
D
的不同的最短路线有 条.
【考点】加法原理之标数法 【难度】4星 【题型】解答
【解析】 到各点的走法数如图
2
所示.
D
6
12
18
D
66
C
6
1
1
A
3
2< br>1
6
B
3
1
B
A
所以最短路径有
1 8
条.
【答案】
18
C
【例 8】 小王在一年中去少年宫学习56次,如图所示,小王家在
P
点,他去少年宫都是走最近的路,且每
次去时所走的路线正好互不相同,那么少年宫在__
______点处.
P
人工湖
B
超市
A
D
E
C
【考点】加法原理之标数法 【难度】3星 【题型】解答
【解析】 本题属最短路线问题.运用标数法分别计算出从小王家
P
点到
A<
br>、
B
、
C
、
D
、
E
点的不同路线有
多少条,其中,路线条数与小王学习次数56相等的点即为少年宫.
因为,从小王家
P
点到
A
点共有不同线路84条;到
B
点共有不同线路56条;到<
br>C
点共有不同线路
71条;到
D
点共有不同线路15条;到
E
点共有不同线路36条.所以,少年宫在
B
点处.
【答案】
B
【例 9】 一只兔子沿着方格的边从
A<
br>到
B
,规定上只能往上或往右走,但是必须经过一座独木桥
MN
,这只
兔
子有( )种不同的走法
B
M
N
A
【考点】加法原理之标数法 【难度】3星
【题型】填空
【关键词】2010年,第8届,走美杯,3年级,初赛,第15题
【解析】
标数法
6
6
12
6
18
6
1
1
1
3
2
1
6
3
1
【答案】
18
种
【例 10】
在下图的街道示意图中,有几处街区有积水不能通行,那么从A到B的最短路线有多少种?
A
A
1
1
1
1
1
1
2
3
4
5
6
1
3
1
4
1
5
5
1
6
11
11
5
111111
11
22
【考点】加法原理之标数法 【难度】3星 【题型】解答
【解析】 因为
B
在
A
的右下方,由标号法可知,从
A到
B
的最短路径上,到达任何一点的走法数都等于到它
左侧点的走法数与到它上侧
点的走法数之和.有积水的街道不可能有路线经过,可以认为积水点的
走法数是0.接下来,可以从左上
角开始,按照加法原理,依次向下向右填上到各点的走法数.如
B
1
B
右上图,从
A
到
B
的最短路线有22条.
【答案】
22
条
(二)不规则图形的标数法
【例
11】 在下图的街道示意图中,C处因施工不能通行,从A到B的最短路线有多少条?
B
C
1
1
1
2
1
A
3
2
2
1
0
2
B
6
3
3
1
C
【考点】加法原理之标数法 【难度】3星 【题型】解答
【解析】 因为
B
在
A
的右上方,由标号法可知,从
A到
B
的最短路径上,到达任何一点的走法数都等于到它
左侧点的走法数与到它下侧
点的走法数之和.而
C
是一个特殊的点,因为不能通行,所以不可能有
路线经过
C
,可以认为到达
C
点的走法数是0.接下来,可以从左下角开始,按照加法原理,
依次
向上向右填上到各点的走法数.如图,从
A
到
B
的最短路线有6
条.
【答案】
6
条
【巩固】 小群家到学校的道路如图4所示
。从小君家到学校有_________种不同的走法。(只能沿图中向右向
下的方向走)
小君家
A
1
学校
【考点】加法原理之标数法 【难度】3星
【题型】填空
【关键词】2007年,希望杯,第五届,六年级,一试,第15题
【解析】
小君家
1
11
2
2
4
7
3
1
1
2
1
3
1
2
10
学校
所
以有10种.
【答案】
10
【例 12】 如下表,请读出“
我们学习好玩的数学”这9个字,要求你选择的9个字里能连续(即相邻的字在
表中也是左右相邻或上下
相邻),这里共有多少种完整的“我们学习好玩的数学”的读法.
1
1
1
1
1
1
2
3
4
5
1
3
6
10
15
1
4
10
20
35
1
5
15
35
70
【考点】加法原理之标数法
【难度】3星 【题型】解答
【解析】
方法一:标数法.第一个字只能选位于左上角的“我”,以后每一个字都只能选择前面那个字的下方
或右方的字,所以本题也可以使用标号法来解:(如右上图,在格子里标数)共70种不同的读法. <
br>方法二:组合法.仔细观察我们可以发现,按“我们学习好玩的数学”走的路线就是向右走四步,向
下走四步的路线,而向下和向右一个排列顺序则代表了一种路线.所以总共有
C
8
4
70
种不
同的读法.
【答案】
70
【例 13】 在下图中,用水平或者垂直的线段连接相邻的字母,当沿着这些线段行走是,
正好拼出“APPLE”
的路线共有多少条?
A
|
1
|
A—P—A
| | |
1—3
—1
|
| |
A—P—P—P—A
| | | | |
1—2—7 —2—1
|
| | | |
A—P—P—L—P—P—A
| |
| | | | |
1—2—4—15—4—2—1
| |
| | | | |
【考点】加法原理之标数法 【难度】3星 【题型】解答
【解析】 要想拼出英语“APPLE”的单词,必须按照“A→P→P→L→E”的次序拼写.在图中
的每一种拼写方式
都对应着一条最短路径.如下图所示,运用标号法原理标号得出共有31种不同的路径
.
【答案】
31
【巩固】 如图,用水平线或竖直线连结相邻
汉字,沿着这些线读下去,正好可以读成“祖国明天更美好”,那
么可读成“祖国明天更美好”的路线有
条.
【考点】加法原理之标数法 【难度】3星
【题型】解答
【解析】 如图2所示,利用加法原理,将读到各个字的路线数写在每个字下方,共有
不同的路线
2
7
1127
(条).
A—P—P—L—E—L—P—P—A
1—2—4—8—31—8—4—2—1
【答案】
127
【巩固】 如图,用水平线或竖直线连结相邻汉
字,沿着这些线读下去,正好可以读成“我爱学而思”,那么可
读成“我爱学而思”的路线有
条.
我
我
我
我
我
爱
爱
学
爱学
而
爱
学
而
思
我
爱
学
而我
爱
学
我
爱
我
【考点】加法原理之标数法 【难度】3星 【题型】填空
【关键词】2009年,学而思杯,4年级,第3题
【解析】 只有一个思,可以从后向前考
虑,用标数法。共有
14641464131
种。
1
4
6
4
11
3
1
3
2
1
1
1
1
4
3
2
1
6
3
1
4
11
【答案】
31
种
【巩固】右图中的“我爱希望杯”有______种不同的读法.
我
爱
希
望
杯
爱
希
希
望
望
杯
杯
望
杯
杯
1
我
1
爱
1希
1
望
1
爱
2
希
1
希
1
望
3
望
1
杯
杯
5
3
望
杯
11
杯15<
br>
【考点】加法原理之标数法 【难度】3星
【题型】解答
【关键词】2005年,第3届,希望杯,4年级,1试
【解析】
“我爱希望杯”的读法也就是从“我”走到“杯”的方法.如上右图所示,共16种方法.
【答案】
16
【例 14】
如图,沿着“北京欢迎你”的顺序走(要求只能沿着水平或竖直方向走),一共有多少种不同的走
法?
1
北
131
北京北
北京欢京北
1272
1
2112
欢迎欢
11
你
【考点】加法原理之标数法
【难度】3星 【题型】解答
【解析】 沿着“北京欢迎你”的顺序沿水平或竖
直方向走,北以后的每一个字都只能选择上面的或左右两边的
字,按加法原理,用标号法可得右上图.所
以一共有
11
种走法.
【答案】
11
【例
15】 如图所示,科学家“爱因斯坦”的英文名拼写为“Einstein”,按图中箭头所示方向有
种不同的
方法拼出英文单词“Einstein”.
E
i
n
s<
br>t
e
i
n
i
n
s
t
e
i<
br>n
s
t
i
n
s
1
1
s
n<
br>4
t
10
i
1
E
i
3
s
1
0
e
30
n
2
n
6
t
20
ii
1
1
n
4
t
10
i
s
1<
br>杯
16
3
s
10
e
30
n
【考点】加法原理之标数法 【难度】3星 【题型】解答
【解析】 由
E→i→n→s→t→e→i→n
的拼法如图
2
所示.
根据加法原理可得
共有
303060
(种)不同拼法.
【答案】
60
【例 16】 图中有10个编好号码的房间,你
可以从小号码房间走到相邻的大号码房间,但不能从大号码走
到小号码,从1号房间走到
10号房间共有多少种不同的走法?
【考点】加法原理之标数法
【难度】4星 【题型】解答
【解析】
我们可以把这个图展开,用箭头标出来就更直观了,然后采用我们学的标数法.
【答案】
22
【例 17】
国际象棋中“马”的走法如图
1
所示,位于○位置的“马”只能走到标有×的方格中, 类似于
中国象
棋中的“马走日”.如果“马”在
88
的国际象棋棋盘中位于第一行第二列(
图
2
中标有△的位置),要
走到第八行第五列(图
2
中标有@的位置
),最短路线有________条.
@
图1图
@
图2
第
题
【考点】加法原理之标数法
【难度】4星 【题型】解答
【关键词】2008年,迎春杯
【解析】 最后一步的可能如图
1
,倒数第二步的可能如图
2
,倒数
第三步的可能如图
3
.
最后
36312
(种). 1
11
2
1
1
1
2
1
2
1<
br>1
3
2
6
1
1
3
2
1
2<
br>1
1
@
图1
@
图2
@
图3
【答案】
12
【例 18】 如图所示,一个花坛的道路由3个圆和5条线段组成
,小兔要从A处做到B处,如果它在圆上
只能顺时针方向走,在线段上只能从小圆走向大圆,且每条道路
最多走一次,那么小兔可以选择的
不同路线有 条.
4
2
2
A
1
2
1
2
6
A
2
【考点】加法原理之标数法 【难度】5星
【题型】填空
【关键词】2008年,迎春杯,中年级,复赛,第2题
【解析】
采用标数法,如图所示,不同路线共有6条.
【答案】
6
条
【例 19】 蜜蜂王国为了迎接2010年春节的到来,特地筑了一个蜂巢如下.每个正六边形蜂窝中
,有由蜂
蜜凝结而成的数字0、1或2.春节到来之时,群蜂将在巢上跳起舞步,舞步的每个节拍恰好走
过的
四个数字:2010(从某个2出发最后走完四步后又回到2,如图中箭头所示为一个舞步),且蜜
蜂每
B
2
B
一步都只能从一个正六边形移动到与之有公共边的
正六边形上.蜜蜂要经过四个正六边形且所得数
字依次为2010,共有 种方法.
【考点】加法原理之标数法 【难度】5星 【题型】填空
【关键词】2010年,迎春杯,高年级,复赛,8题
【解析】
图中标2的六边形分两类,第一类如上左图所示,第二类如上右图所示.
从第一类六边形出
发,每个六边形都只有1种走法,因此共有6种走法.从第二类六边形出发,每
个六边形有4种不同的走
法,其中两种是环形回路(细线表示),两种是原路返回(粗线表示),因
此共有
4624
种走法.综上所述,共有
24630
种不同的走法.
【答案】
30
(三)立体图形标数法
【例
20】 从北京出发有到达东京、莫斯科、巴黎和悉尼的航线,其他城市间的航线如图所示(虚线表示在
地球背面的航线),则从北京出发沿航线到达其他所有城市各一次的所有不同路线有多少?
莫斯科
巴黎
北京
东京
纽约
【考点】加法原理之标数法 【难度】4星 【题型】解答
【解析】 第一站到东京的路线有10条:
<
br>纽约
莫斯科巴黎悉尼
悉尼巴黎莫斯科
巴黎悉尼
纽约
悉尼巴黎
北京东京
莫斯科
纽约悉尼
巴黎
悉
尼纽约
巴黎莫斯科
纽
约
莫斯科巴黎
悉尼
<
br>
纽约莫斯科
巴黎
莫斯科纽约
同理,第一站到悉尼、巴黎、莫斯科的路线各有10条,
不同的路线共有
10440
条.
悉尼
【答案】
40
条
【例 21】
如图,8个单位正方体拼成大正方体,沿着面上的格线,从A到B的最短路线共有 条。
B
【考点】加法原理之标数法 【难度】3星
【题型】解答
【关键词】2007年,第五届,走美杯,五年级,初赛,第15题
【解析】
直接用标数法,即可。观察发现,从A点出发的三个面左面、下面、前面所标数相等,则上面的中
间填6
,进而中间右填18。类似的,即可得到到达B段的方法总共有:18×3=54。
6
31
3
3
2
1
1
2
2
1
33
3
1
6
6
18
6
6
6
18
18
54
A
B
A
1
【答案】
54
条
【例 22】
如图,27个单位正方体拼成大正方体,沿着面上的格线,从A到B的最短路线共有 条。
B
A
【考点】加法原理之标数法 【难度】4星 【题型】填空
【关键词】2007年,第五届,走美杯,初赛,六年级,第15题
【解析】
最短路线有条384条。
20
10
4
1
4
8
10
18
18
20
56
36
56128
128
B
128
36
18
1
3
6
10
18
56
8
1
2
34
10
4
20
A
1
1
1
【答案】
384
条