魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: 金眼睛
打印 上一主题 下一主题

★最短路径问题 [复制链接]

Rank: 2

积分
421
帖子
233
精华
2
UID
25681
性别
保密
11#
发表于 2008-5-18 16:40:59 |只看该作者
<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 编辑 ]

使用道具 举报

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解达人 论坛建设奖 六年元老

12#
发表于 2008-5-18 17:22:56 |只看该作者
我是发现每个节点只能走到其右面和上面的节点,这样右面节点的路径数加上面节点的路径数,就是该节点的可能路径数,在图上就是做加法就可以了。B节点定为1更合理一点。。<BR>
如果这个不够理论的话,可以把题中不规则的图拆成规则的长方形,然后用排列组合来算。。
The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

Rank: 2

积分
210
帖子
192
精华
0
UID
30626
性别
13#
发表于 2008-5-18 17:25:50 |只看该作者
N种走法 哈哈 ~~~~~
没事拧两下
山东群:57795783 欢迎大家加入

使用道具 举报

透魔

红舞半支烟

Rank: 6Rank: 6

积分
6790
帖子
6356
精华
1
UID
19686
性别
14#
发表于 2008-5-18 20:04:49 |只看该作者
小学生的题啊!!!中国的教育在进步???还是。。。。
一切从“零”开始。

使用道具 举报

Rank: 1

积分
109
帖子
82
精华
0
UID
15125
性别
保密
15#
发表于 2008-5-18 20:27:28 |只看该作者
呵呵,高中数学的老题了!其实很简单啊!而且不用一条条数!用统计学原理啊!

使用道具 举报

透魔

有空了学学4D二阶

Rank: 6Rank: 6

积分
5924
帖子
3936
精华
0
UID
1290
兴趣爱好
结构
理论

魔方破解达人 八年元老

16#
发表于 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<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>

使用道具 举报

红魔

sub18

Rank: 4

积分
2291
帖子
2047
精华
1
UID
18627
性别

两年元老 国家(地区)纪录(NR)

17#
发表于 2008-5-18 23:37:40 |只看该作者
怎么感觉像算法中的动态规划!
青海长云暗雪山
孤城遥望玉门关
黄沙百战穿金甲
不破楼兰终不还

使用道具 举报

Rank: 2

积分
421
帖子
233
精华
2
UID
25681
性别
保密
18#
发表于 2008-5-19 08:36:44 |只看该作者
<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 编辑 ]

grid.JPG (16.74 KB, 下载次数: 41)

路径转化数字

路径转化数字

使用道具 举报

Rank: 4

积分
1609
帖子
266
精华
0
UID
5208
性别
19#
发表于 2008-5-19 08:55:33 |只看该作者
在高中学了“排列组合”后就好做了,但是高中生差一点的也做不出来(甚至是大学生)。
给小学生做么,用noski的方法,解释么,要走最短路径,只有横向、纵向两个方向,把两个方向的可能性加起来,就是这个结点的可能性了(唯一不足是,题目从A到B,他的解答是从B到A,不过都是一样的)。
这个题目,对于聪明的小学生来说也不难,因为只用到了很简单的原理(“加法原理”)和很简单的计算(加法),至少我当初读小学的时候能做出来。

使用道具 举报

Rank: 2

积分
421
帖子
233
精华
2
UID
25681
性别
保密
20#
发表于 2008-5-19 09:13:07 |只看该作者
<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>

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2025-6-14 08:23

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部