探索 数学趣味类-《你知道这个图中最长和最短各是多少么？》

fspider

这个是比较有趣的数学几何题，看谁灵光闪现……

jingmouren

不同颜色表示不同距离
看晕了

最短路可以用DIJKSTRA  Bellman-Rord算法找到
最长路是NP-Hard。只好枚举

wsbswdx

这道题是图论中最长(最短)路径问题

fspider

友情提示：注意问题2中的提示哦！

秋水小柯

我觉得最长的是从左上角到右上角，从一点出发，到交点处比较下面线路的条数以及选择含有较长线路或没有最短线路的

theoplant

不知道怎么证明，

我觉得最长应该是最左边的那个点到最右边的那个点　或者　最上面的那个点到最下面的那个点

944f4fe875fb39d

用动态规划法求解。如果我不色盲的话应该是 320。

=1000]
  
[/hide]

磁铁

擒贼先擒王，找到老挝再说

944f4fe875fb39d

fspider

6楼结果正确，但这个图相对来说还比较简单，正如题2中所提示的，如果十分庞大，可有其他更简单的解法，甚至都不用需要计算机而解呢？

944f4fe875fb39d

［hide=1000]
拿把有刻度的尺划一组平行线即可。注意平行线的长度与路程成比例，注意线段的联结点不要搞错。
[/hide]

这样就可以不用任何计算就得到结果，当然路程是多少还是要算一下。

944f4fe875fb39d

]这就是几何作图法，再加一把圆规，那么分岔部分就可以用射线来表示，用同心圆来确定取舍。路程是多少都不要算了，直接量就是了。但要比按动态规划法用计算器计算要慢些。[/hide]

此问题比较简单。如果有回路，那么上述方法可能就不方便了，还是用动态规划法来得方便。

比如，把题目改一下，将某些点再用线段连起来。题目是，鬼子抓住了嘎子，要他带路，嘎子就带鬼子走最远的路，但每条路都不重复（可能经过同一个村庄，那没关系，这次村东，下次就村西），最后把鬼子累垮了，再让八路军收拾他们。呵呵。

磁铁

这个课件对间谍通话次数那个题也好有用处呢

niegm04

问题a：直觉，顺着路走，走一段，看一段，区分需不需要走回头路，不得返回哦，所以，凭肉眼观察再稍加计算就可以啦。计算机为何不能计算，这就是计算机不能思维，呵呵，人类最大的优势就是思考！
问题b：最长为315，把图分为三部分，给出示意图

13楼的路线是正确的，但长度应该是320，不是315。

demoner99

感觉那些线的颜色跟他们之间的距离有一定的比例来的

所以只要在中心一点的位置 ,选择一个点

然后尽量找通过它的点的颜色的最多的路线

shenxiu

这个看中间交点，看到交点的最长距离
具体也是从边界向中间找啊

欧阳静茹

可否考虑把这些距离变换为水平或垂直方向，然后考虑横坐标和纵坐标来分析呢？

引用第17楼欧阳静茹于2008-01-03 19:55发表的 :
可否考虑把这些距离变换为水平或垂直方向，然后考虑横坐标和纵坐标来分析呢？

很受启发！！

尤里卡！尤里卡！

磁铁

引用第18楼shinbade于2008-01-03 20:40发表的 :


很受启发！！

尤里卡！尤里卡！

知识拓展一下，因为有关科学，


尤里卡

[尤里卡时刻]“尤里卡”原是古希腊语，意思是：“好啊！有办法啦！”古希腊学者阿基米德，有一次在浴盆里洗澡，突然来了灵感，发现了他久未解决的计算浮力问题的办法，因而惊喜地叫了一声“尤里卡”，从此发现了阿基米德定律。 尤里卡计划是西欧在面临巨大挑战和压力的情况下“自我觉醒”的产物。 [/url][尤里卡计划]20世纪70年代中期，西欧在科技，尤其是高科技方面渐渐落后于美国和日本，进入80年代后，差距进一步拉大。西欧如果不采取措施奋起直追，到20世纪末就有可能成为技术上的“不发达大陆”。同时西欧各国也意识到，在这场决定未来命运的高科技竞赛中，只有一个把“人力、物力和财力都集中起来的欧洲，才能卓有成效地保持自己在将来世界上的经济地位”。此外，美国提出的“星球大战”计划和美苏之间激烈的军事竞赛，也在客观上促进了西欧的振作和团结，使西欧产生了必须走联合的道路，集各国之长，在高技术领域迎头赶上美国、日本的强烈紧迫感。尤里卡计划是法国和原联邦德国外长于1985年3月共同酝酿，4月17日由法国总统密特朗正式提出的。尤里卡这个响亮的名字一经呼出，很快受到西欧大多数国家的关注和欢迎。6月底，欧洲共同体首脑会议对尤里卡计划表示原则同意。7月17日，西欧17国外长和科研部长在法国巴黎召开第一次尤里卡会议(第二次尤里卡会议又吸收了土耳其)，初步商定了尤里卡计划的轮廓，18日发表公报宣布，尤里卡正式诞生。 “尤里卡”计划建议西欧各国加强在尖端技术领域的合作，逐步成立“欧洲技术共同体”。具体合作内容最初包括五个方面：(1)计算机：建立欧洲软件工程中心，发展高级微型信息处理机等；(2)自动装置：研制民用安全自动装置和全部自动化工厂等；(3)通讯联络：发展为科研服务的信息网，研制大型数据交换机等；(4)生物工程：研究人造种子、控制工程等；(5)新材料：研究新型材料结构，发展高效涡轮机等。项目达三百多个，其中有24个重点攻关项目。 到1993年底，尤里卡共举行了11次部长会议。成员除欧共体委员会外由17个增加到22个国家。1992年匈牙利作为东欧第一个国家加入了尤里卡。1993年俄国也申请加入了尤里卡。此外，美国、日本、加拿大、以色列和波兰等12个非尤里卡成员国的企业和科研机构也先后参加了26个尤里卡的研究项目。尤里卡计划的实施，不仅对欧洲，而且对整个世界的经济，政治都产生了重大影响。 [url=http://baike.baidu.com/view/548525.html?wtp=tt#][The Eureka尤里卡钻石]尤里卡，又名欧瑞利(O"Reilly)。原生石重21.25克拉，它是在南非发现的第一颗钻石，虽然其重量不大，但其重要的历史意义使它成为世界名钻。 尤里卡钻石是在1866年，由南非的一个牧童在砍柴的路上发现的，当时他见到这个亮亮的石头，觉着好玩，便拿回家去让妹妹玩耍。后来牧童的母亲无意中给来作客的修克（后发现名钻南非之星的人）提起这块石头，修克建议用它划刻玻璃，果然玻璃被刻了一道痕迹，便开始怀疑它可能为钻石，但仍没太上心。一年之后，有一个叫欧瑞利的猎人自告奋勇，愿带它去哥士堡鉴定。最后经几方专家综合鉴定才确认其为钻石。并将其以欧瑞利的名字命名，又名为尤里卡(Eureka)，意指“我找到了”，亦含有南非终于找到了钻石之意。 1867年后，该原石被切割成10．73克拉的椭圆形钻石。 1966年戴比尔斯公司将其买下，并将它送给现在被称为世界钻石城的开普顿的开普顿会议，陈列供人参观。