魔方吧·中文魔方俱乐部

标题: ★最短路径问题 [打印本页]

作者: 金眼睛 时间: 2008-5-18 12:40:53 标题: ★最短路径问题

             ┌┬┐B 
  ┌┬┬┼┼┤ 
  ├┼┼┼┼┤ 
  ├┼┼┼┼┤ 
A└┴┴┴┴┘
 
如图所示，这是一个5行6列的网，也可以看做是4行5列正方形格子的阵列，其中在左上方缺失了一部分。
一只小蚂蚁想从A处沿格子线爬到B处，最短的步数我们知道是9步，现在问，经过最短步数（9步）从A到B的路径有多少种？
 
这是我从小侄女的作业本上发现的，现在小孩的压力真是越来越大，这题目不适合小学生吧？<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/mad.gif" border=0 smilieid="11"> 
 
不要光给出答案，说出你的求解过程，呵呵！<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> 

[ 本帖最后由金眼睛于 2008-5-18 13:20 编辑 ]

附件: [网格] grid.JPG (2008-5-18 13:20:28, 7.6 KB) / 下载次数 59
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTY4Mjl8NDI1ODYwNjN8MTc0MDgwODAzMHwwfDA%3D

作者: kexin_xiao 时间: 2008-5-18 13:03:35

LZ的图片我刷了两遍都没看清,有问题吧?

作者: 金眼睛 时间: 2008-5-18 13:19:50

原帖由 kexin_xiao 于 2008-5-18 13:03 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=136260&ptid=8912" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> LZ的图片我刷了两遍都没看清,有问题吧?

没有图片，呵呵！好吧，我做一个图加在附件里，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/handshake.gif" border=0 smilieid="17"> 

[ 本帖最后由金眼睛于 2008-5-18 13:20 编辑 ]

作者: noski 时间: 2008-5-18 14:40:32

111么。。我用杨辉三角的方法，应该算标准方法了吧，呵呵。
 
图如下：
 路径数问题.jpg

[ 本帖最后由 noski 于 2008-5-18 14:55 编辑 ]

附件: 路径数问题.jpg (2008-5-18 14:55:31, 14.74 KB) / 下载次数 60
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTY4NDB8YTVkZjk2NTl8MTc0MDgwODAzMHwwfDA%3D

作者: 金眼睛 时间: 2008-5-18 15:26:19

原帖由 noski 于 2008-5-18 14:40 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=136359&ptid=8912" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 111么。。我用杨辉三角的方法，应该算标准方法了吧，呵呵。

<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> <IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/handshake.gif" border=0 smilieid="17"> ，对，我也是用类似的方法做的，能说出原理么？
 
再看看别人的答案，有没有理论点或者公式点的解答。

[ 本帖最后由金眼睛于 2008-5-18 15:47 编辑 ]

作者: 乌木 时间: 2008-5-18 15:31:34

B点的走法数是否改为0？否则，B点的“1”是不是解释为“不走也是一种走法”？

作者: 乌木 时间: 2008-5-18 15:54:16

本题是否可以参看参看这一帖：http://bbs.mf8-china.com/viewthr ... page%3D7&page=1

作者: 金眼睛 时间: 2008-5-18 16:17:53

我发现这道题等价于下面这个问题：
 
前三次从0~3中取数，最后两次从0~4中取数，并且每次取数要不小于前一次。
 
编程很容易解决这个问题，我算了一下是111，没错。
 
怎么用数学的方法解决这个问题呢？<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> ，希望大家集思广益

作者: 金眼睛 时间: 2008-5-18 16:23:24

原帖由 乌木 于 2008-5-18 15:54 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=136421&ptid=8912" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 本题是否可以参看参看这一帖：http://bbs.mf8-china.com/viewthread.php?tid=3563&extra=page%3D7&page=1

谢谢乌木，我看了，是一类的问题。
 
你胡思乱想的那种情况可以看做是取数过程加入了条件限制，在某一步不能够取某个数，不知道这样的问题如何用数学方法来描述，编程倒是很方便，加入限制不是程序的弱项，呵呵！

作者: 乌木 时间: 2008-5-18 16:27:47 标题: 回复 8# 的帖子

noski的答案应该就是数学方法（之一）吧？你的意思是否指别的数学方法？

作者: 金眼睛 时间: 2008-5-18 16:40:59

原帖由 乌木 于 2008-5-18 16:27 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=136450&ptid=8912" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> noski的答案应该就是数学方法（之一）吧？你的意思是否指别的数学方法？

是啊，我也是列表做的，如下表所示
 
    0       1     2      3      4
1  126   56   21    6      1
2  70     35   15    5      1
3  35     20   10    4      1
4  15     10   6      3      1
5  5       4     3      2      1
 
    0       1     2      3      4
1  5       4     3      2      1
2  1       9    12    14     15
 
126-15=111
 
只是觉得缺少理论支持，这样的问题不能总用列表来解决吧？<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/smile.gif" border=0 smilieid="1">  
 

[ 本帖最后由金眼睛于 2008-5-18 16:43 编辑 ]

作者: noski 时间: 2008-5-18 17:22:56

我是发现每个节点只能走到其右面和上面的节点，这样右面节点的路径数加上面节点的路径数，就是该节点的可能路径数，在图上就是做加法就可以了。B节点定为1更合理一点。。 
如果这个不够理论的话，可以把题中不规则的图拆成规则的长方形，然后用排列组合来算。。

作者: s-dilo 时间: 2008-5-18 17:25:50

N种走法哈哈 ~~~~~

作者: bbshanwei 时间: 2008-5-18 20:04:49

小学生的题啊！！！中国的教育在进步？？？还是。。。。

作者: halaqq 时间: 2008-5-18 20:27:28

呵呵，高中数学的老题了！其实很简单啊！而且不用一条条数！用统计学原理啊！

作者: Cielo 时间: 2008-5-18 23:15:31

先考虑把图补成一个完整长方形之后的情况，这时走了9步，每步向上或向右，其中5步向右，4步向上，就是说在9个空格里填入5个“向右”和4个“向上”，共 9C4 = 9C5 = (9 x 8 x 7 x6) / (4 x 3 x 2 x 1) = 126 再计算多算了的几种情况： 1，经过A正上方距离3步的C点，有 3C0 = 1 条 2，经过C右边的D点，有 4C1 = 4 条 3，经过D右边的E点，有 5C2 = 10 条 共多算了15条 所以共111种。 让小学生做真是难啊<img smilieid="10" src="http://bbs.mf8-china.com/images/smilies/default/sweat.gif" border="0">

作者: purple 时间: 2008-5-18 23:37:40

怎么感觉像算法中的动态规划！

作者: 金眼睛 时间: 2008-5-19 08:36:44

<CITE>Cielo，你真强！你的解答很令人满意，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> </CITE>
<CITE></CITE> 
<CITE>我昨天翻了一下《组合数学基础》，找到了解决这个问题的方法，如下：</CITE>
<CITE></CITE> 
<CITE>如果不缺那个角，这个问题相当与从0~4中取五次数，理解方法可以看附件中的图。</CITE>
<CITE></CITE> 
<CITE>设取出的0~4的个数分别为x0,x1,x2,x3,x4，则问题变为 x0+x1+x2+x3+x4=5</CITE>的非负解的个数。
 
对于x1+...+xn=r，非负解的个数为C(n+r-1,r)，对于本题为C(5+5-1，5)=C(9,5)。
 
原理是：相当于往r个球当中放入n-1个挡板，比如本题相当于往5个球中放4个挡板，也就是9个位置选4个
 
O|O|O|O|O，代表了x0=1,x1=1,x2=1,x3=1,x4=1，也就是01234。
|OOOO||O|，代表了x0=0,x1=4,x2=0,x3=1,x4=0，也就是11113。
 
最后问题的解是A-B的路径数减去A-C的路径数，因为经过C再到B的肯定也是最短路径
C(5+5-1,5)-C(5+2-1,2)=C(9,5)-C(6,2)=C(9,4)-C(6,2)=9*8*7*6/4/3/2-6*5/2=126-15=111
 
相对我的这个方法还是Cielo的方法理解简单一些。

[ 本帖最后由金眼睛于 2008-5-22 15:02 编辑 ]

附件: [路径转化数字] grid.JPG (2008-5-19 08:52:51, 16.74 KB) / 下载次数 37
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTY4NTR8NWMxNWNmYTZ8MTc0MDgwODAzMHwwfDA%3D

作者: whitetiger 时间: 2008-5-19 08:55:33

在高中学了“排列组合”后就好做了，但是高中生差一点的也做不出来（甚至是大学生）。
给小学生做么，用noski的方法，解释么，要走最短路径，只有横向、纵向两个方向，把两个方向的可能性加起来，就是这个结点的可能性了（唯一不足是，题目从A到B，他的解答是从B到A，不过都是一样的）。
这个题目，对于聪明的小学生来说也不难，因为只用到了很简单的原理（“加法原理”）和很简单的计算（加法），至少我当初读小学的时候能做出来。

作者: 金眼睛 时间: 2008-5-19 09:13:07

原帖由 whitetiger 于 2008-5-19 08:55 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=136829&ptid=8912" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 在高中学了“排列组合”后就好做了，但是高中生差一点的也做不出来（甚至是大学生）。给小学生做么，用noski的方法，解释么，要走最短路径，只有横向、纵向两个方向，把两个方向的可能性加起来，就是这个结点的可能 ...

恩，noski的方法很好很强大，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> ，对于小学生应该没什么障碍。
 
不过光是教小孩这些方法真是教育制度的悲哀啊，他们就不会仔细去思考过程了。
 
你也很强啊，我估计我小学肯定做不出来，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/sweat.gif" border=0 smilieid="10">

作者: warming 时间: 2008-5-21 22:03:29

找到规律了``可以去<A href="http://bbs.mf8-china.com/viewthread.php?tid=3563&extra=page%3D7&page=3">http://bbs.mf8-china.com/viewthread.php?tid=3563&extra=page%3D7&page=3</A>看看``
答案就在下面29楼

[ 本帖最后由 warming 于 2008-5-23 22:09 编辑 ]

作者: whitetiger 时间: 2008-5-22 09:32:20

原帖由 金眼睛 于 2008-5-19 09:13 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=136839&ptid=8912" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A>   恩，noski的方法很好很强大，，对于小学生应该没什么障碍。   不过光是教小孩这些方法真是教育制度的悲哀啊，他们就不会仔细去思考过程了。   你也很强啊，我估计我小学肯定做不出来，

“不过光是教小孩这些方法真是教育制度的悲哀啊，他们就不会仔细去思考过程了。”
不明白是什么意思？这个方法是很自然的，小孩子自己也能想出来，教这个才是数学的本质。很多学校里学的都是工具、方法，不是思想！
怎么叫“不会仔细去思考过程”？教育不是“填鸭”，要启发孩子自己去想，不要简单地写题目，然后说“这类题目该这么做”，至少归纳总结的工作要让孩子自己做。老师管得越多，学生学得越差！
 
原理么，就是“加法原理”，在高中学习组合数学的时候讲过的。
做成一件事有若干种途径，那么做成这件事的可能性就是这若干种途径可能性之和。
到一个点，要么从下往上，要么从左往右，那么到这个点的可能性是其下面的点和左面的点的可能性之和。（递推关系）
最下面的点都只有一种可能，最左面的点也只有一种可能。（初始条件）
然后就画图吧！

作者: 金眼睛 时间: 2008-5-22 11:36:34

LS的火气怎么这么大啊？呵呵！
 
你说的都对，我只是觉得这种题目不适合小学生，他们也许只会这么一加而不会去考虑为什么了，不是所有小孩都很聪明的。
 
对于我来说，画图毕竟不够完美，格子多了怎么办呢？<CITE>Cielo的方法就很好，是一种数学的方法，当然noski能这么快想到解决方法，也很聪明。</CITE>

作者: whitetiger 时间: 2008-5-22 13:59:19

原帖由 金眼睛 于 2008-5-22 11:36 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=138387&ptid=8912" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> LS的火气怎么这么大啊？呵呵！   你说的都对，我只是觉得这种题目不适合小学生，他们也许只会这么一加而不会去考虑为什么了，不是所有小孩都很聪明的。   对于我来说，画图毕竟不够完美，格子多了怎么 ...

不是火气大，只是有感而发。（只针对事）
 
对于小学生，只能用加法原理罗，能想到用加法的，已经很聪明了！（不是老师教的那种）
 
你认为Cielo的方法是数学方案，而noski的只是解决方法，那就是本末倒置了。
noski用的是小学生能理解的方法，用了最朴素的数学方法，适合于这种格子很少的题目。
（如果格子多了，当然也能做，要让小学生找规律来解决问题，简单地用加法就不行了。）
Cielo的方法只适合于学习过组合数的人，偏离了题目要求。不能因为用了复杂的公式或者算法就认为解法是高级的。本质还是noski的方法更明白！

作者: 金眼睛 时间: 2008-5-22 14:58:28

我把这道题放在这里，不是只为了得到答案，也不是要给小学生讲明白，而是想得到其中蕴含的数学原理。
 
noski的是加法原理，我觉得很好；Cielo用的是组合数学原理，更通用，数学上更“完美”一些，我觉得更好，这有什么本末倒置的？
 
到此为止吧，不是每个人的想法都一样，保留意见好了，呵呵！<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12">

作者: Cielo 时间: 2008-5-22 22:00:46

原帖由 金眼睛 于 2008-5-22 11:36 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=138387&ptid=8912" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
LS的火气怎么这么大啊？呵呵！
 
你说的都对，我只是觉得这种题目不适合小学生，他们也许只会这么一加而不会去考虑为什么了，不是所有小孩都很聪明的。
 
对于我来说，画图毕竟不够完美，格子多了怎么 ...

呵呵，我来说两句。 楼主可能不知道吧，noski很厉害的！他提供的方法是切合题目的，因为要求是要让小学生来做<img smilieid="12" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border="0">

作者: 金眼睛 时间: 2008-5-23 08:49:05

我要求了？<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/sweat.gif" border=0 smilieid="10"> ，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> ，好，知道了！
 
回到正题吧，请大家思考一下，对于网格中的每一小段网格线，它所承担的最短路径又是多少呢？

作者: 43297222 时间: 2008-5-23 11:08:39

你们是不是理解错了,说的是九步的路径.111条??是不是拐弯走风景好点呀?

[ 本帖最后由 43297222 于 2008-5-23 11:13 编辑 ]

作者: warming 时间: 2008-5-23 22:04:26 标题: 我知道规律了``

如图
<IMG src="file:///C:/mf8/01.bmp" border=0>
每个正方形的对角线相加就等于终点的数``
按照这个规律``这个题目是这样做的``
<IMG src="file:///C:/mf8/03.bmp" border=0>

作者: warming 时间: 2008-5-26 20:56:24

有谁还有其他简单的方法?`

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)