奥数 最短距离_第1页
奥数 最短距离_第2页
奥数 最短距离_第3页
奥数 最短距离_第4页
全文预览已结束

下载本文档

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

文档简介

1、最短路线例1.下图是从学校到邮局经过的所有马路，问从学校到邮局共有几 条最短路线？学校邮局思路分析：为了便于叙述，在各交叉点上标出字母.BEF要想从家到学校走的路程最短，就不能走回头路，这道题中，最短也 要走长方形ACGI的一个长和一个宽.为保证走得路线最短，只能向 下和向右走.如果我们一条一条地数，可以发现共有以下六条路线最短：ABCFI； ADGHI；ABEFI； ADEFI；ABEHI； ADEHI；但如果按上述方法找，难免发生重复遗漏的路线.下面我们观察 一下，看看是否有规律可循.从A点出发向下或向右走只能到达B、D两点，到B点有一种 走法，到D点同样只有一种走法，所以在B点、D点处各

2、标角码1， 表示从A点到此点的最近走法只有1种.从B点可以向右走到达C点，因为从A到C的最短路线也仅有 1条，所以角码为1.从B点向下可到E点，另外从D点到达E点的 距离也最短，所以E点角标角码2.如图所示.1iE211继续做下去，我们会发现，每一个小格右下角的数正好是这个小 格右上角与左下角的数的和，这个和就是从出发点A到I点所有最短 路线的条数.例2. 一个邮递员投送信件，街道如图所示，图上的数字表示各段 街道的公里数.他从邮局出发，走遍各街道，最后回到邮局，怎样走路线最合理？12421邮局思路分析：由于街道是含8个奇点的图形，所以，不可能不重复 地走遍所有街道，为了保证邮递员从邮局出发再

3、回到邮局，图形中8 个奇点都应变为偶点.即将奇点两两相配对用线连结，有很多连法， 下图仅列出了三种情形：添加的路线的里程分别是：（1）3X4=12（公里）（2）3X2 + 2X2 = 10（公里）（3）2X4 = 8（公里）由此可见邮递员按图（3）的路线走，重复的路最少，最合理.全 程共走：3X6 + 1X4 + 2X8 + 2X4 = 46（公里）例3.小刚家和小明家之间各条道路的示意图，请问要从小刚家到小 明家，最近路线有几条？思路分析：要求从小刚家到小明家的最近路线有几条，就是要求 从小刚家到小明家的最短路线.把各交点标上字母，如下图.这道题和前面例1有所不同，要格外注意由哪两点的和来确定另 一点的.由AB，AC各有1种走法，可以确定AD有1 + 1 = 2（种） 走法.由AI有1种走法，AD有2种走法，可以确定AJ有1 +2 = 3（种）走法.由AM有1种走法，AJ有3种走法，可以确定AN有1 + 3=4（种）走法.AE有2种走法，AJ有3种走法，AK有2 + 3 = 5（种）走 法.AE有2种走法，AG有2种走法，AH与2 + 2 = 4（种）走 法.AK有5种走法，AH有4种走法，AL有5 + 4 = 9（种）走 法.AN有4种走法，AK有5种走法，A

人人文库> 全部分类> 图纸下载 > 毕业设计

温馨提示

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

最新文档

评论

0/150

提交评论