越算越乱的最短路径数

2020-03-13 08:16李如
数学大王·中高年级 2020年3期
关键词:小红帽路线图条路

李如

小红帽的外婆住在森林中的一个小村子里,小红帽每个周末都会独自从家出发,前往外婆家看望她,顺便给外婆带上一些美味的食物。狡猾的大灰狼不知从哪里知道了小红帽这个习惯,想要埋伏在路边袭击小红帽,把她抓回去吃掉,还好小红帽的妈妈早有准备。

在小红帽出门之前,妈妈拿了一张从家到外婆家的路线图给小红帽。妈妈嘱咐小红帽,每次从家出发去外婆家的路线都要不同,而且尽量选择较短的路线,这样遇到大灰狼的概率就会大大减少。

“老实”的算法VS“聪明”的算法

小红帽拿到路线图的时候看了一下,上面给出了所有从自己家到外婆家可以走的小路。因为外婆家在小红帽家的东南方向,所以她要么先向南走,要么先向东走,这样就能顺利到达外婆家。那么,她到底有多少条路线可以选择呢?

小红帽用笔在路线图上将路线一条一条地画了出来,不一会儿,路线图就被弄花了。她数了数,有9条路线可以选择。

妈妈看着小红帽一个人趴在桌子上对着路线图写写画画,便问她:“你在干什么呢?”

“妈妈,我想算一算从咱们家到外婆家一共有几条不同的路线可以选择。”小红帽向妈妈求助,“我一共算出9条,您看看我算得对吗?”

妈妈看着被小红帽弄花的路线图笑了笑:“我教你用另外一种方法来算,保证简单,一学就会!”

“真的吗?快教教我。”小红帽迫不及待地想让妈妈教她另一种计算方法。

妈妈接过笔,在路线图上标出了数字“1”和“F”,说道:“你看,在与起点相邻的两条道路上分别标上1,说明起点附近有2条路可以走。

如果我们想去起点所在的对角线的另一端F,是不是有2条路可以走?”小红帽点点头。

“既然这样,我们在F后边做个标记。你看,标记的‘(2)其实是与起点相邻的两个1的和。代表从起点,也就是我们家,到F有2条路可以走。”小红帽一看,還真是这样。

妈妈继续说:“我们继续按照这样的方法来算算到外婆家有几条路线可以选择吧!如果用A表示我们家、用L表示外婆家,那么,我们的目的就是从A出发到达L。”为了方便小红帽理解,妈妈继续在路线图上标出了一些不同的字母。

“从A出发有2条路可以走,分别是‘A→B和‘A→E。

到达B、E后再出发,各有2条路可以走。

按照刚刚标记路线的方法,我们把能到达这几个地方的路线数标记上去。

我们不断地按照这个方法画下去,最终就可以得到从A到L的最短路径数。”最后,妈妈在路线图上标出的数是这样的:

“这样算下来,一共有10条路线可以选择呢!之前是我算错了。”小红帽羞愧地说。

妈妈笑了笑:“没关系,你现在学会了这个方法,既可以简便地算出结果,又不会出现遗漏。”

另一种“聪明”的算法

“其实还有另一种‘聪明的计算方法。”妈妈决定多教小红帽一点,“这个方法比上一个方法难一点,你可要开动脑筋,好好思考。”

小红帽立马端正地坐下来:“妈妈您快说。”

“我们先来看看路线图。”

妈妈拿出另一张崭新的路线图,慢慢地画出几条线:“你发现了吗?无论你选择哪条路线,都至少要走3条横向的路和2条竖向的路。”

“实际上,我们只需要确定走的是哪2条竖向的路,就能确定最短路径数。但是这竖向的路不能随便选。”妈妈举了一个例子,“例如,你选择了下边这种路线,就必须要走回头路或者绕远路。”

“对这2条竖向的路的选择还真不能马虎。”小红帽若有所思地说。

妈妈也紧接着说道:“是的,这样的话,我们就要分情况来考虑了。从竖向的路来看,如果我们选择了‘A→E这条路,那么接下来竖向的路,共有4种选择。

如果我们选择了‘A→B→F,那么接下来竖向的路就有3种选择。

如果我们选择了‘A→B→C→G

这条路,接下来竖向的路就有2种选择;最后,如果我们选择‘A→B→C

→D→H这条路,就只剩下‘H→L这1种选择了。”

“把不同情况下的路线数加起来,一共是4+3+2+1=10(条)。”小红帽高兴地说道,“和用第一种方法算出来的结果一样呢!”

妈妈点点头,说道:“在现实生活中,这个路线图的模型算是非常简单的了。今天你学习了新的数学知识,可一定要牢牢记住哟!”

猜你喜欢
小红帽路线图条路
这条路
路线图,作用大
描述路线图
这条路
把小红帽吐出来
多点执业这条路还没有修好
这条路
小红帽