★最短路径问题

金眼睛

<P>

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

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

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

noski

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

s-dilo

N种走法 哈哈 ~~~~~

bbshanwei

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

halaqq

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

Cielo

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

purple

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

金眼睛

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

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

whitetiger

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

金眼睛

<P>

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

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