搜索
查看: 2189|回复: 16

[五年级数学] 原谅我的智商 题目也看不懂 谁能解惑下

[复制链接]
发表于 2018-4-15 10:09 | 显示全部楼层 |阅读模式 来自: 中国上海
解惑 看也看不懂

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?注册

x
发表于 2018-4-15 10:18 | 显示全部楼层 来自: 中国上海
路线上有费用,把所有相较更贵的路线去除。这是哪里的题目。
发表于 2018-4-15 10:45 来自手机浏览器 | 显示全部楼层 来自: 中国上海
sh329000 发表于 2018-4-15 10:18
路线上有费用,把所有相较更贵的路线去除。这是哪里的题目。

能做下吗 看看思路
发表于 2018-4-15 10:55 | 显示全部楼层 来自: 中国上海
每个城市只要两条路即可,除了a和f一条路即可,从最贵的开始看凡事有三条路的把最贵那条路去掉
发表于 2018-4-15 11:00 来自手机浏览器 | 显示全部楼层 来自: 中国上海
邮路问题
我记得好像有结论,但是似乎结论的证明并不完美
发表于 2018-4-15 11:21 | 显示全部楼层 来自: 中国
a到I直线成本25。 但是从A-B-I成本20。所以砍掉成本25的
发表于 2018-4-15 12:10 | 显示全部楼层 来自: 中国浙江
意思是,研究一个可以无脑操作的套路,所有这样的问题,都可以套路一下得到答案。比如,查看整个平面图像有几个三角形,几个四边形,几个五边形,如果是三角形,去掉最贵的一条边,如果是四边形,去掉最贵的两条边。如果是五边形,去掉最贵的三条边。如果去掉一条边会导致有些点,不再相连,就不去掉。
发表于 2018-4-15 12:49 | 显示全部楼层 来自: 中国江苏苏州
可以用暴力解法
发表于 2018-4-15 17:55 | 显示全部楼层 来自: 中国上海
无向图,最优路径
发表于 2018-4-15 19:06 | 显示全部楼层 来自: 中国上海
这是计算机科学的经典问题——求解图的最小(各边的费用和最小)生成(包含原图全部顶点, 边全部来自原图的边)树(任意两个顶点之间都有路径可到达且无回路)。一个易于理解的算法:
step1. 初始状态:图G=原图的边集合。T=生成树的边集合,初始为空集
step2. 从图G中取出一条费用最小的边,如果该边不与T中现有的边构成回路(比如T中已经有了AB和BI,再将AI放入就构成ABI回路),则放入T中;如果构成回路,丢弃。
step3. 如果T中的边还没有包含原图所有顶点,回到step2;否则结束,生成树T就构造好了。

以本题为例:
首先费用最小的是BI=8,放入T,T={BI},剩下边中费用最小的是BC=10,BC与T中各边不构成回路,可以放入,T={BC,BI}。剩下边中费用最小的是AB=12,与T中各边不构成回路,可以放入,T={BC,BI,AB}。剩下边中费用最小的是AI=25,但与T中的边AB和BI构成ABI回路,丢弃AI……以此类推


发表于 2018-4-15 20:57 | 显示全部楼层 来自: 中国上海
楼上都好牛
发表于 2018-4-16 11:11 | 显示全部楼层 来自: 中国上海
本帖最后由 zorrollt 于 2018-4-16 11:41 编辑
满爸 发表于 2018-4-15 19:06
这是计算机科学的经典问题——求解图的最小(各边的费用和最小)生成(包含原图全部顶点, 边全部来自原图 ...


                                        .
发表于 2018-4-16 11:29 | 显示全部楼层 来自: 中国上海
本帖最后由 zorrollt 于 2018-4-16 11:34 编辑
满爸 发表于 2018-4-15 19:06
这是计算机科学的经典问题——求解图的最小(各边的费用和最小)生成(包含原图全部顶点, 边全部来自原图 ...


所以按照方法最后一路舍弃,就是从左边的图(  舍弃的是 AI  BH CG DE  )变成了 右边的图。所有城市都能相通了,没有回路。所以右边的图其实就是答案?题目只是叫我们思考左图变成右边图的方法是怎么得到的?为自己的智商捉急~~~
发表于 2018-4-16 12:27 | 显示全部楼层 来自: 中国上海

6年级不敢保证,试试吧。可以完全不提“最小生成树”的概念,直接说解题思路,其实是贪心算法。贪心算法思想简单粗暴,不管三七二十一,每一步都选当前的最优(每次都从没选过的边中取一条费用最小的)。但注意不要出现回路(回路意味着多余。比如AB和BI已经连接,那么ABI三点两两之间都可以到达,如果再引入AI就是多余,导致不必要的费用增加,与费用和最小的目标矛盾)。
发表于 2018-4-16 12:29 | 显示全部楼层 来自: 中国上海
zorrollt 发表于 2018-4-16 11:29
所以按照方法最后一路舍弃,就是从左边的图(  舍弃的是 AI  BH CG DE  )变成了 右边的图。所有城市都 ...


对的,其实这题不是让你给出某个具体图的解法,而是要你对这一类问题给出通用的算法。话说你这是哪来的题目啊,对6年级学生来说要求太高了
发表于 2018-4-16 12:46 | 显示全部楼层 来自: 中国上海
本帖最后由 zorrollt 于 2018-4-16 12:48 编辑
满爸 发表于 2018-4-16 12:29
对的,其实这题不是让你给出某个具体图的解法,而是要你对这一类问题给出通用的算法。话说你这是哪来的 ...


今年朋友学校参加夏令营的闯关题,(通不过可能就没资格参加了吧)这年头真不容易,贪心法看懂额, 简单明了,谢谢~~~
发表于 2018-4-16 13:17 | 显示全部楼层 来自: 中国上海
这是不是把环路变成支干路的做法,昨天xrs统筹规划中好像提过一题。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|千帆网 ( 沪ICP备15002998号-1 )上海千教教育科技有限公司,邮箱:admin@qianfanedu.cn 举报电话:54804512

GMT+8, 2024-3-29 17:16 , Processed in 0.066289 second(s), 16 queries .

快速回复 返回顶部 返回列表