魔方吧·中文魔方俱乐部

标题: 奇妙的组合之复杂的路（唤醒沉睡的数学版块的好帖） [打印本页]

作者: Osullivan 时间: 2009-6-24 21:42:31 标题: 奇妙的组合之复杂的路（唤醒沉睡的数学版块的好帖）

最近数学版块比较沉寂，我来唤醒吧。找了个图文并茂的帖子，问题也不错，漫画故事形式，这样的好帖，由简到难，深入浅出，斑竹不申精也要加分啊，不要吝惜哦~~~~~~~

a．苏珊有一个问题，她上学时总遇到斯蒂克。斯蒂克：喂，苏珊。我和你一起走好吗? 苏珊：讨厌，走开。 b．苏珊：我有主意了，我每天早上上学都走不同的路，斯蒂克就找不到我了。　 c．这个图表示苏珊家和学校间的所有街道，图中苏珊上学这条路不是向东就是向

a．苏珊有一个问题，她上学时总遇到斯蒂克。
斯蒂克：喂，苏珊。我和你一起走好吗?
苏珊：讨厌，走开。

b．苏珊：我有主意了，我每天早上上学都走不同的路，斯蒂克就找不到我了

c．这个图表示苏珊家和学校间的所有街道，图中苏珊上学这条路不是向东就是向南。

d．这是苏珊上学的另一条路，到底有多少条路?

e．苏珊：我想知道到底我能走几条路，我想这很难算。嗨！一点儿也不难，太简单了！苏珊想到什么办法了?

f．苏珊：我在住处所在的角标上1，因为只有一个起点。再在这个角相邻的两个角标上1，因为只有1条路能到达。

g．苏珊：现在我把2标在这个角上，因为我能通过两条路到达这里。
当苏珊意识到2是1加1的和时，她突然想到每个角的数字一定是相邻能到达这个角的两角的数字和。

h．苏珊：已经标出了几个角，我马上就会标上其它角。
你能为苏珊标上其它角并告诉她上学能走几条路吗？
多少条路?
剩下的五个顶点，从上至下，从左到右应标上1，4，9，4和13，最后一个顶点的13表示苏珊按最短路径有13条路去上学。
苏珊的发现的确是计算学上最短径数的简单快捷的算法。如果她试图画出所有路径，再数它们那就太繁杂了，而且当街道网络量大时也是根本办不到的。当你实际画一下13条路径时，你会更好地体验算法的有效性。

图1
为了检验你对这种算法的理解程度，试着画一下其它几种街道网络，并应用这种算法确定从顶点A到顶点B的最短路径的数量。图1给了这种类型的四个同题，它们也可用其它方法求解，如使用组合数学的公式，但这种方法太复杂了。

图2

国际象棋中的车从棋盘的一角到达对角线另一角的最短路径数是多少呢?根据苏珊为街道标号的方法，通过为每个棋格标号很快就可解决。因为车只能沿直角(水平和垂直)移动，所以最短路径只能限制在向目标方向的移动上，如图2所示，整个棋盘已正确标记，标号马上就给出了从起始区域到盘上任何其它区域的最短路径数。右上
角格中的数字是3432，所以车从一角沿对角线到另一角的最短路径数是3432条。

把棋盘沿对角线切成一半，然后转动成为图3所示的三角形。底排格中的数字就是从顶点到底排各格的最短路径数。这个三角形的标号和著名的帕斯卡三角形①中的数字是相等的。
这种从顶到底最短路径的算法，准确地构成了帕斯卡三角形，这种同构的精确推
广，就是帕斯卡三角形的迷人之处。由帕斯卡三角形马上就可得到二项式展开式各项的系数和一些基本概率问题的解答。注意图3中从三角形顶端到底部外边格中数字都是1，越往中心移数字越大，或许你见到过这种按帕斯卡三角形原理构造的装置，一块倾斜的板，几百个小球沿着桶滚入板底各栏、球准确地按漏斗型二项式函数曲线排列，这是因为进入每个口的最短路径致都是二项展开式的系数。
苏珊算法同样适用于具有长体小格的立方体。想一想，边长3个单位的立方体被分为27个小立方体，有一个车在一个小格中，车可以沿三个座标方向平等移动，它沿着空间对角线到达另一端的最短路径数是多少呢?

①中国人称之为杨辉三角，系中国南宋数学家杨辉发现。

[ 本帖最后由 Osullivan 于 2009-6-24 21:48 编辑 ]

附件: abcamber20.jpg (2009-6-24 21:42:31, 12.83 KB) / 下载次数 324
http://www.mf8-china.com/forum.php?mod=attachment&aid=NTY2MjZ8N2Y0YmU5MzR8MTc4MTYzODExNnwwfDA%3D

附件: abcamber21.jpg (2009-6-24 21:42:31, 11.82 KB) / 下载次数 309
http://www.mf8-china.com/forum.php?mod=attachment&aid=NTY2Mjd8OWI4ZTg0ZWR8MTc4MTYzODExNnwwfDA%3D

附件: abcamber22.jpg (2009-6-24 21:42:31, 13.49 KB) / 下载次数 337
http://www.mf8-china.com/forum.php?mod=attachment&aid=NTY2Mjh8NzI5MmM0NWR8MTc4MTYzODExNnwwfDA%3D

附件: abcamber23.jpg (2009-6-24 21:42:31, 13.55 KB) / 下载次数 332
http://www.mf8-china.com/forum.php?mod=attachment&aid=NTY2Mjl8MTY3MzQwMWN8MTc4MTYzODExNnwwfDA%3D

附件: abcamber24.jpg (2009-6-24 21:42:31, 13.77 KB) / 下载次数 330
http://www.mf8-china.com/forum.php?mod=attachment&aid=NTY2MzB8YjVlNjkwYTF8MTc4MTYzODExNnwwfDA%3D

附件: abcamber25.jpg (2009-6-24 21:42:31, 14.14 KB) / 下载次数 343
http://www.mf8-china.com/forum.php?mod=attachment&aid=NTY2MzF8MjE4OGQ4ZjB8MTc4MTYzODExNnwwfDA%3D

附件: abcamber26.jpg (2009-6-24 21:42:31, 13.49 KB) / 下载次数 332
http://www.mf8-china.com/forum.php?mod=attachment&aid=NTY2MzJ8ZWI5MDEzOTB8MTc4MTYzODExNnwwfDA%3D

附件: abcamber27.jpg (2009-6-24 21:42:31, 14.16 KB) / 下载次数 335
http://www.mf8-china.com/forum.php?mod=attachment&aid=NTY2MzN8Nzg2ZTgyNmZ8MTc4MTYzODExNnwwfDA%3D

附件: abcamber28.jpg (2009-6-24 21:42:31, 30.21 KB) / 下载次数 321
http://www.mf8-china.com/forum.php?mod=attachment&aid=NTY2MzR8ZWJlYzNlYTZ8MTc4MTYzODExNnwwfDA%3D

附件: abcamber29.jpg (2009-6-24 21:42:31, 49.85 KB) / 下载次数 329
http://www.mf8-china.com/forum.php?mod=attachment&aid=NTY2MzV8YTUzZGY4NjJ8MTc4MTYzODExNnwwfDA%3D

附件: abcamber30.jpg (2009-6-24 21:42:31, 22.65 KB) / 下载次数 336
http://www.mf8-china.com/forum.php?mod=attachment&aid=NTY2MzZ8MTJjYzM0N2F8MTc4MTYzODExNnwwfDA%3D

作者: Osullivan 时间: 2009-6-24 21:45:41

沙发我的，先顶下我们伟大祖宗的神奇的杨辉三角，咱中国人的骄傲~~~~~~

[ 本帖最后由 Osullivan 于 2009-6-24 21:54 编辑 ]

附件: Osullivan.jpg (2009-6-24 21:54:56, 50.48 KB) / 下载次数 327
http://www.mf8-china.com/forum.php?mod=attachment&aid=NTY2NDJ8YWYwNGM3NWF8MTc4MTYzODExNnwwfDA%3D

作者: 魔葱 时间: 2009-6-24 21:54:53

话说,,,,,,上次等全班同学都不在...我在黑板写了很大的杨辉三角的说....嘿嘿

作者: CodS 时间: 2009-6-24 22:04:22

奥沙利文，就是那么帅啊。只是最近的斯诺克打得及其郁闷。

作者: Osullivan 时间: 2009-6-24 22:08:10

哈哈，我最近玩魔方，snooker也怠慢了，一直非常喜欢这项超级有难度的运动~~~~

作者: nick159951 时间: 2009-6-24 22:29:44

LS一秒回复？
太神了

作者: 四川绵阳 时间: 2009-6-24 23:03:47

楼主发的图好奇怪我看不懂

作者: ggglgq 时间: 2009-6-25 08:58:21

　　

这种帖子论坛中早有了，比如：

http://bbs.mf8-china.com/viewthread.php?tid=3563

http://bbs.mf8-china.com/viewthread.php?tid=8912
　　
　　等。


鉴于楼主的热情以及楼主最近一直致力于 ★数学、算术趣题★ 的发展发了

很多好贴，还是加分鼓励一下。  亦希望各位数学高手都向楼主学习，积极提供

并解答本区的问题，提高我们的数学应用能力。    唉，我那置顶加分帖


         征集各类小巧魔方态态关系网

         http://bbs.mf8-china.com/viewthread.php?tid=30653

一直在等待各位数学高手参与解决呢！问题好像不是很难，关键要花时间呀！　　
　　
  　　
　　
　　
　　

作者: about 时间: 2009-6-25 11:02:14

HELP！我根本不知道在说什么！