图形计数和最短路线新.doc

《图形计数和最短路线新.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.最短路线这一讲里，我们将会解决这个特殊的计数问题：最短路线问题。怎样计数从A到B的最短路线的条数呢？我们将介绍一种非常巧妙的方法——对角线法（也叫标号法）。一、长方形方格标号：【例1】咱们先做个游戏：在方格纸上任取一点A作为起点，再在A的右上方任取一点B作为终点划一条由A到B的最短路线。聪明的小朋友，你能划出来吗？总共能划出几条呢？分析：教师可提问如ACIHGFB是最短路线吗？为什么不是？如果要划从A到B的最短路线，那么从A点出发只能向上或向右（每一条都是横划2格竖划2格），可以是ACDEB、ACIEB、

2、ACIFB、AHGFB、AHIEB、AHIFB这六条路线。在上面这个游戏中，你是用什么方法找到从A到B的最短路线呢？如果A、B两点变成图1、2、3的位置，那么从A到B的最短路线有几条呢？分析：图1、2、3中从A到B的最短路线均为6条。例2、按图中箭头所示的方向行走，从A点走到B点的不同路线共有多少条?资料..【分析】如下图，为了方便叙述，我们将某些点边标上字母，按箭头所示，走有一条路，到有2种办法；再往下到有从走和走两种方法，这样到有3条路线；到可从、走，有5种方法到．过可从、走，共有8条路线；到可走、，这

3、样共有13种走法；经过可从、两条路走，有21种方法都到；到达可以走和，因而有34种路线到达．这样由A到B，可经过和两个交叉点，共有34+21=55条路线，如图所示．因此，从A点到B点的不同路线共有55条．例3：动物园的门票1元1张，每人限购1张。现在有10个小朋友排队买票，其中5个小朋友只有1元的钞票，另外5个小朋友只有2元的钞票.售票员没有准备零钱，问有多少种排队的方法能够使售票员找得开零钱？分析与解答：假设拿1元的5个小朋友无差别,拿2元的5个小朋友也无差别.AB42111111144223452591

4、451428用标数法求共有多少种排队方法.如图用横线表示拿1元的小朋友,用竖线表示拿2元的小朋友,从A到B只能向右或向上走(从任何一个持有2元钞票的小朋友向前看，持1元钞票的小朋友都要多一些),共有42种走法,即有42种排队方法.我们再考虑拿1元的小朋友有差别，共有=5×4×3×2×1＝120（种）,同理拿2元的小朋友有差别，共有=5×4×3×2×1＝120（种）.根据乘法原理排队方法共有42×120×120=604800（种）.二、不规则图形标号：【例4】下图是小明家和学校的示意图，你们觉得小明从家到学校

5、一共有几条最短路线呢？资料..分析：我们采用对角线法（如图），但本题图形有变化，，例如D点：从学校到C点有2种走法，再到D点最短路线的选择只能从C点走，所以从学校到D点有2种走法。请教师根据学生的理解情况灵活把握，选择几个点讲透彻。从而得到小明可以选择的最短路线共有12条。从而得到小明可以选择的最短路线共有12条。分析：教师讲解时要注意阶梯形与前几题的不同。我们采用对角线法（如图），从学校到李家村共有126种不同的最短路线。【例5】“五一”长假就要到了，小新和爸爸决定去黄山玩。聪明的小朋友请你找找看从北京到

6、黄山的最短路线共有几条呢？分析：我们采用对角线法（如图）这道题的图形与前几题的图形又有所区别，在解题时要格外注意是D、G、K、E、H、L这样的点共有几条最短路线，具体是怎么走的，即由哪两点的数之和来确定另一点的。从北京到黄山最近的道路共有10条。【例6】大熊和美子准备去看望养老院的李奶奶，可是市中心在修路(城市的街道如图所示),他们从学校到养老院最短路线共有几条呢？聪明的小朋友，请你们快想想吧！　资料..分析：（解法1）先假设直接学校到养老院（也就是说可以经过市中心，也可以不经过市中心）对角线法共126条。

7、再减去必经过市中心的60条，即得126-60=66（条）。（解法2）可以直接求，即把含有市中心的田字格挖去（或者认为市中心那一点标“0”），共有66条。【例7】第三届希望杯五年级2试试题）右图中的“我爱希望杯”有______种不同的读法。（咱们三年级的小朋友都会做五年级的竞赛题了，真聪明！）分析：本题实际是最短路线问题，从我（1个）、爱（2个）、希（3个）、望（4个）、杯（5个）中组成“我爱希望杯”即相同的字只能选一个而且不能重复选，所以共有16种。对角线法，其实最短路线问题还有【附1】类型，教师可选讲。【

8、附】假如直线AB是一条公路，公路两侧有甲、乙两个村庄。现在要在公路上建一个汽车站，让两个村子的人到汽车站的路线之和最短，问汽车站建在哪？资料..分析：找到甲村关于AB的对称点C，连接C和乙村交AB的那一点即为汽车站。课后练习：1、从X到Y最短路线共有多少种不同的走法？分析：对角线法。共20种。2.如图，从A到B，最短路线有几条？分析：共有41条3.如图，从P点出发到Q点，走最短的路程，有多少种不同的走法？分析：共