2015河南乡镇公务员选调生考试行测备考11解决最短路径问题_第1页
2015河南乡镇公务员选调生考试行测备考11解决最短路径问题_第2页
2015河南乡镇公务员选调生考试行测备考11解决最短路径问题_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、2004年，世界著名科学杂志物理世界举行了一场别开生面的评选活动，邀请世界各地的读者评选出自己心目中最伟大、最喜爱的公式、定理或定 律。最终的结果出乎很多人的意料，连幼儿园的小孩都知道的公式“1+1=2”不仅入选，而且还高居第一。无独有偶，尼加拉瓜这个国家在鼎盛时期发行了一套 纪念邮票改变世界面貌的十个数学公式，排在第一位仍然是“1+1=2”这个公式。下面带大家来看看这个公式是如何解决行测中“最短路径问题”的。“最短路径问题”是公务员考试数学运算经常涉及的一种题型。所谓最短路径问题是指在行程路线中，如何确定从某处到另一处最短路线的条数。比如：【例】下图是一个街道的平面图，纵横各有7条路， 某人

2、从最左上处的点到最右下处，共有多少条最短路线?为方便大家理解，先从纵横各有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。这道题比较简单，

3、可以一一列举，但是当街道数比较多的时候，一一列举就太麻烦了，京佳教育专家带领大家从另外一 个思路来求解。要想到达C3，必须先到B3或者C2，到B3之后直接往下走即可，到C2之后直接往右走即可，所以到达C3的最短路径条数就应该等于到达 B3最短路径条数加到达C2最短路径条数。同理，想到达B3必须先到A3或者B2，所以 到达B3最短路径条数等于到A3最短路径条数加到B2最短路径条数。依次递推，得到下图：注：每点所标数字为从A1点到达该点最短路径条数。通过该图：我们可以发现每点所标数字都等于紧挨的上面点所标数字和紧挨的左面点所标数字和，这就是最短路径问题的规律，就像1+1=2那么简单。小伙伴，你会了吗?试试最开始的那道纵横各有7条街道的吧。在考试的时候，如果命题人设置一些变化，考生应如何应对呢?京佳教育专家建议各位考生不必慌，你只需分析清楚题干即可。比如：【例】下图是一个街道的平面图，纵横各有6条路， 某人从最左上处的点(A)到最右下处的点B，中间有事必须过C点，共有多少条最短路线?各位小伙伴，你想到怎么做了吗

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论