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

gany892

同事的小孩上小学二年级,这是前几天她的一道考试题(正常考试,非奥数),回来后问到我,我思考后得到解法,但我用到了EXCL软件,还有叉形树,这些条件是二年级考试时不可能具备的,大家帮忙想想,小学生怎么做这道题:一个九宫格子(3*3方格),从一个端点沿边长走到另一个端点,最短的路线最多有几条:答案是20条.我是这样做的:

我的解法思路是:研究这些方格的节点,用一些虚拟的平面去截取这个图形,每个平面与水平线成45度角,都通过上边节点.九宫格可以做出7个这样的平面.每两个平面之间的步数就是一步.其次,给每个节点附上一个"权",这个权就代表从左上方第一个节点到达这个点的最少步数.很显然,每个节点的权等于它上方和左方两个节点的权相加.现在我把这些节点和全移到EXCL里面,除上边和左边所有格子设定为一之外,其他所有格子设定为左格与上格的数字之和,于是得到上图.下方的最后以行,代表格中(红色字体)的数字所对应的阶数.例如"5阶"就代表一共25个格子,组成5*5的方阵.此图也可任意增加阶数,可以到上万阶.

从此图很方便的查出,3阶(3*3的九宫)的最短路线走法最多20条,四阶70条,5阶252条........,问题是,小学二年级怎么做的?我确实想不出来.

[em06]

[此贴子已经被作者于2007-4-10 12:42:11编辑过]

whitetiger

1、思路就是这样，没有更简单的方法了。

对于二年级的这道题目，只有三阶，用笔填就可以了，不必用软件算的。

（比较官方的解答：

直接可以对点标数字，或者称为“权”，表明从左上端点到该点的最短路径的数量。

最上面和最下面的端点，都只有1条最短路径，所以都填1；其它点，可能从上面下来，也可能从左面过来，所以它的“权”是上邻点和左邻点的“权”之和。

接着就是填数字了。）

2、很反感“奥数”这个提法，因为这些都是数学的范畴，在小学、中学都是能理解学会的。是用来娱乐的，不是用来考试的！！

这道题在二年级，绝对属于“奥数”范畴，或者是说需要“动脑筋”的，在考纲之外。

3、到了高中，这道题就是组合数学范畴了：格点(m,n)的“权”是C(m,m+n)。

需要往右走m次，往下走n次，把这m+n步任意排序，就有C(m,m+n)种走法。

乌木

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

     

乌木

我对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条，对不对呢？很不放心。

如何是好？

whitetiger

乌木引用的4楼“高手”的说法，太绝对了。

他说的“排队方式问题，或者说是分布状态数”，就说不是一个选取组合问题，很奇怪。

只是一种类型的问题，当然可以用选取组合的方式来解释：

一个方向(X)是m步，一个方向(Y)是n步，一共(m+n)步。

在(m+n)步的顺序中，任意选取m步作为X方向，那么剩下的n步就是Y方向，所以总数就是：C(m,m+n)。

（当然，写成：C(m,m+n)C(n,n)也可以。）

对于三维的，组合数学同样能解决问题：(0,0,0)到(l,m,n)，路线的总数为：C(l,l+m+n)C(m,m+n)C(n,n)。

至于“它与组合公式形式上一样，但内涵不是一回事”，C(m,m+n)只是一种表示方式，有最明显的含义，但不表示不能作为其它问题的答案/计算方式。就如同“立体框架路线数的一般公式为(l+m+n)!/(l!m!n!)”也仅仅是在一种提法，并没有专门的名称（组合数，问谁都知道；“立体框架路线数”，不看问题的话，问谁都不知道）。

这个题目，很明确的是一个组合数学问题，按4楼“高手”的说法，不能用组合数描述，倒是很奇怪的讲法。数学研究的是一般性的问题，而不是专门来描述“立体框架路线数”、“状态相貌数要排除全同粒子间的交换”的；可以用一般的形式来解决这些专门的问题。

whitetiger

3楼的问题，个人认为，反而是用1楼的方法最简单。

用慢慢在纸上填也可以；

我刚才也用EXCEL算了一下，少线路的就去掉对应的“加左”和“加上”项，空的格子可以不考虑（实际去了一个格子，去了2个“加左”项，去了2个“加上”项）。

答案是357。

whitetiger

5楼的问题，可以分成两步：从(0,0,0)到(3,a,0)再到(3,3,3)。

1、“3”，“a”在维度上可以任意，所以有A(3,3)=6种可能；

2、a是1或者2；

3、被重复计算的是同时通过(3,1,0)和(3,2,0)的路线。

所以，答案是：

[C(1,3+1)C(2,3+2)+C(2,3+2)C(1,3+1)-C(1,3+1)C(1,3+1)]×A(3,3)=384

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

乌木

<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 编辑 ]