2015浙江衢州公务员考试行测备考—1+1解决“最短路径问题”

衢州公务员考试网提醒您关注浙江衢州公务员考试，欢迎您关注衢州中公教育微信号：qzoffcn

衢州公考交流群：234787506

【2015年衢州公职考试大家谈】

推荐:衢州2015年省考公务员考试新大纲课程

衢州省考史上最强大冲刺课程预约中【只需99元】

2015衢州省考公告、大纲、职位表所有信息汇总

“最短路径问题”是公务员考试数学运算经常涉及的一种题型。所谓最短路径问题是指在行程路线中，如何确定从某处到另一处最短路线的条数。比如：

【例】下图是一个街道的平面图，纵横各有7条路， 某人从最左上处的点到最右下处，共有多少条最短路线?

为方便大家理解，中公教育先从纵横各有2条路开始讲起，如下图：

注：第一行街道交叉点分别用A1、A2、A3表示，第二行街道交叉点分别用B1、B2、B3表示，第三行街道分别用C1、C2、C3表示。

如果从最左上角(A1)到最右下角(C3)所走路径最短，则该人只能往右走或往下走，不能走回头路。因为如果走回头路，所走路线肯定不是最短。按照只能往右走或 往下走，最短路线有：A1-A2-A3-B3-C3、A1-A2-B2-B3-C3、A1-A2-B2-C2-C3、A1-B1-B2-B3-C3、A1-B1-B2-C2-C3、

A1-B1-C1-C2-C3。这道题比较简单，可以一一列举，但是当街道数比较多的时候，一一列举就太麻烦了，中公教育带领大家从另外一个思路来求解。要想到达C3，必须先到B3或者C2，到B3之后直接往下走即可，到C2之后直接往右走即可，所以到达C3的最短路径条数就应该等于到达B3最短路径条数加到达C2最短路径条数。同理，想到达B3必须先到A3或者B2，所以 到达B3最短路径条数等于到A3最短路径条数加到B2最短路径条数。依次递推，得到下图：

注：每点所标数字为从A1点到达该点最短路径条数。

通过该图：我们可以发现每点所标数字都等于紧挨的上面点所标数字和紧挨的左面点所标数字和，这就是最短路径问题的规律，就像1+1=2那么简单。小伙伴，你会了吗?试试最开始的那道纵横各有7条街道的吧。

在考试的时候，如果命题人设置一些变化，考生应如何应对呢?中公教育建议各位考生不必慌，你只需分析清楚题干即可。比如：

【例】下图是一个街道的平面图，纵横各有6条路， 某人从最左上处的点(A)到最右下处的点B，中间有事必须过C点，共有多少条最短路线?

各位小伙伴，你想到怎么做了吗?中公教育提醒各位：既然必须过C点，我们只需先求出从A到C的最短路径条数，再求从B到C的最短路径条数即可。

 

独家推荐：

衢州省考史上最强大冲刺课程预约中【只需99元】

衢州2015年省考公务员考试新大纲辅导课程

2015年江山市省考课程直击

2015年龙游县省考课程直击

 

现场报名：

衢州分部地址：衢州市柯城区上街26号四楼(供销大厦正对面)。

江山分部地址：江山市鹿溪中路367幢3号(公交北关站旁)。

龙游分部地址：龙游县荣昌路金泽大厦1层26号(供电局附近)。

衢州电话：0570-3169002 3169001 13306703966

龙游电话：0570-7030729 7030739 13325700260

江山电话：0570-4036200 4036201 15355247621

 

交流平台：

微信号：qzoffcn

衢州公考群：234787506

江山公考群：333696941

龙游公考群：335187796

常山公考群：271653246

开化公考群：322426106

衢州银行考试群：80887096

 

---