小学2年级的考试题,把我难住了.

乌木

我胡思乱想一下，如果方格阵列中有几处“道路”坏了，比如下图的例子，那么，某两点之间的最短路线数该如何算？

     

乌木

我对2楼说的组合数C（m，m+n）不理解，曾请教别人，最近他给了我如下的答复：

    “我有点不同看法，请大家指正。方格阵两点间的最短路线数，计算式应该写成(m+n)!/(m!n!)，不应该用C(m,m+n)来表示。因为这是一个排队方式问题，或者说是分布状态数，不是一个选取组合问题。虽然它与组合公式形式上一样，但内涵不是一回事。此处用组合公式仅是答数对，但不好解释。只要将平面路径扩展成立体框架就能看出这一点了。

      一个单位立方体，从一个顶角走到对顶角，最短路线一共是3步，有6种走法。
      两个单位立方体拼合，1×1×2的立体框架，从角顶(0,0,0)走到对角顶(1,1,2)，步数是1+1+2=4步，路线数应该是4!/(1!1!2!)=12种。
      一个3×3×3的立体框架（外观有如三阶魔方，但路线可以经过内部交点），从一个角顶(0,0,0)走到对角(3,3,3)，步数是3+3+3=9步，路线数应该是9!/(3!3!3!)=1680种。每到一个交点，只要三个方向的步数限额都还未用完，就有三个‘接近’目标、至少‘不倒退’的可能走向。否则，就有两个或一个可能走向。
      立体框架路线数的一般公式为(l+m+n)!/(l!m!n!)，可见与组合数什么的就不搭界了。

      算法可以推广到高维空间。此问题与‘状态相貌数要排除全同粒子间的交换’有类似处。”

[此贴子已经被作者于2007-4-14 19:33:29编辑过]

乌木

楼上提到立体格阵，那么，如果如三阶魔方那样的立体格阵，从点（000）到点（333）的最短路线，限走表面的话，共有几条呢？

乌木

5楼问题好像蛮复杂。初想之下，在一个3×6的平面方格阵中对角之间最短路线数为84条，借用魔方术语，U－R，U－F，B－R，B－D，L－F，L－D，共6个3×6平面格阵，答案好像是84×6＝504条。再一想，U－R和U－F之间重复计算的至少有20条，B－R和B－D之间、L－F和L－D之间也是，那么就扣除60条吧，答案444条，对不对呢？很不放心。

如何是好？

乌木

<P>384，那么，我那答案444果然还有“水份”啊。下图中，a到c，限走表面，在U，R面走的话，据1楼，有84条路线。其中，包括a到b再到c的20×1＝20条（图中红线）在U，F面走时，84条中显然重复计算了刚才的20条。6个84中减去3个20条，看来是没有问题的。还要减去那些路线呢？让我慢慢想想。这问题蛮有趣。</P>
<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <BR></P>
<P align=right><FONT color=#000066>[此贴子已经被作者于2007-4-16 19:17:22编辑过]</FONT></P>

[ 本帖最后由 乌木 于 2008-5-18 15:50 编辑 ]

乌木

<P>噢，果然还有要减去的重复计算。下图中，蓝色路线共20条，在走U－F面和走L－F面时被重复计算了。类似情况有三处，故还要减去20×3＝60条路线，444－60＝384。谢谢whitetiger 。</P>
<P>到底要理论分析才行，我不懂有关理论，只好玩玩“凑答数”，碰到题目复杂一点等情况就不行了。没办法。</P> <BR>
<P align=right><FONT color=#000066>[此贴子已经被作者于2007-4-16 21:03:06编辑过]</FONT></P>

[ 本帖最后由 乌木 于 2008-5-18 15:51 编辑 ]

乌木

不显示，顶！

[此贴子已经被作者于2007-4-16 19:07:08编辑过]

乌木

那是数学上的抽象，并无实物对应的吧，我也说不清。

乌木

也许吧。好像许多研究工作当时看不出什么，而有些多少年后会在什么事物上有应用。又比如，电脑编程中的“格雷”码最初仅是数字技术中的一种能自动纠错的编码方式，想不到后来有人发现0和1～511的自然数转换为512个九位格雷码之后，竟然有对应的实物－－我国传统的九连环的512个用九位二进制数表示的状态与之一一对应，一点不差，令人惊叹不已。

[此贴子已经被作者于2007-5-6 23:50:07编辑过]

乌木

正是。假定有一种二维“人”，他很难理解三维空间，只能理解一维和二维世界。我们是三维人，能理解一、二和三维，而且常常把三维的东西投影到二维平面中去理解－－照片、绘画、屏幕、电影等等都是借用二维图像来描述三维世界。但要我们理解高维空间，就像那二维人一样，难了。据说数学家有时把高维空间“投影”到低维空间来处理，道理一样。具体的我也说不上来了。

[此贴子已经被作者于2007-5-7 16:35:38编辑过]