千零 2009-11-17 22:37
奥数求解－9
经理有4封信先后交给打字员，要求打字员总是先打最近接到的信。比如：正打第3封信时第4封信到了，应立即停下第3封信，转打第4封信；第4封信打完后，接着打第3封信，而不能先打第1或第2封信。问：打字员打完这4封信的先后顺序有多少种可能？
答案为什么是14？.
Jennierunrun 2009-11-17 22:40
回复 1#千零 的帖子
个趟HY路考试就有这道题目，就是一只只排，好像，明朝帮侬问儿子哦.
千零 2009-11-17 22:49
回复 2#Jennierunrun 的帖子
我给我女儿看了一只只排的图，我女儿就问了一个问题，我就憋特了。.
smartwxc 2009-11-18 09:19
回复 1#千零 的帖子
注意到两点：1）信是按一定顺序发给打字员的；2）打字员打完的信的数量是不可能超过来信的数量的。化归思想，由此用横坐标表示来信，纵坐标表示打完的信，转化为求最短线路的走法数量问题，但纵坐标的值不能大于横坐标的点不能取。
顺便说一下这是一个组合计数里卡特兰数的问题，计算机里叫堆栈问题。
比较同类的一题：爸爸、妈妈饭后一起洗8个花纹互不相同的盘子，爸爸按一定的顺序洗盘子（设为A-B-C-D-E-F-G-H），洗好后一个一个往上摞，妈妈再从最上面一个一个地拿走放入碗柜摞成一摞，爸爸一边洗妈妈一边拿，问妈妈摞好的盘子一共有______种不同的摞法。.
Jennierunrun 2009-11-18 09:26
回复 4#smartwxc 的帖子
哪能家高深饿啦.
xyq2100 2009-11-18 10:41
回复 1#千零 的帖子
[attach]407882[/attach]
[attach]407883[/attach]
[attach]407884[/attach]
这种题目至少应该是高中生看的
[[i] 本帖最后由 xyq2100 于 2009-11-18 10:43 编辑 [/i]].
easylife99 2009-11-18 10:50
可是摞碗问题我们刚刚上四年级学加乘原理的时候就见过了,应该和LZ的那个是一样的,就是一个一个排可能性..
amyhuangli 2009-11-18 10:54
请参见附图.
格格妈 2009-11-18 11:26
回复 8#amyhuangli 的帖子
真清楚，呵呵
看了题目第一反应是这个经理有毛病的[em14].
liduduma 2009-11-18 11:42
同意4楼的观点。计算机中称作栈。
栈就是一种后进先出的结构，就像我们放东西，先放的东西总是放在下面，后放的东西就放在上面一样的道理。而拿出来的时候，最后放进去的先拿出来。
这道题其实就是1、2、3、4依次进栈，但允许中间出栈，只要记住已经在栈中的数，出来的顺序只有一种可能。
那么出栈以1开头的可能性就很多，1234、1243、1324、1342、1432都可以，但是1423一定不可能。因为第二个出来4的话，那么一定在4入栈前，2和3都已经入栈了，按照后进先出，出来必定是1432
这样以2开头的，2134、2143、2314、2341、2431都可以，2413不可能
以3开头的，321的相对次序是不变的，所以有3421、3241、3214
以4开头，只有1个，即4321
这样一共有14种
[[i] 本帖最后由 liduduma 于 2009-11-18 11:44 编辑 [/i]].
Jennierunrun 2009-11-18 12:37
回复 9#格格妈 的帖子
同意，个饿经理是伐大正常.
begme 2009-11-18 12:39
回复 8#amyhuangli 的帖子
肯定不对！第一封信未完，第二封信完成后也有两种可能，一种是打第三封还有一种是打完第一封！同理，第三封信完成后不只是做第四封，还有可能是第二封，还有可能是第二封后打第一封，然后才是第四封！.
冬瓜爸爸 2009-11-18 20:12
回复 8#amyhuangli 的帖子
你的图不完整吧，比如从上往下数第3枝就不完整。
1完，2未完，3完，以后，不一定是来4，也可以是2完，再来4.
所以你的图里没包括1324这样的顺序
总之，你的图例很清楚，但只列了8种顺序，需要再完备一些。
我同意10楼的答案，14种。.
amyhuangli 2009-11-19 09:54
回复 13#冬瓜爸爸 的帖子
嗯，回复有理，请以图上作一更正，应该考虑后一封未来时，前一封已完，但再前一封可以先进行的情况。.
SophieDAD 2009-11-19 12:27
回复 10#liduduma 的帖子
有意思的解释！我曾经偷闲写过一篇关于堆栈序列的文章，还总结了一个堆栈序列数目的公式。
[em16].
liduduma 2009-11-19 13:21
回复 15#SophieDAD 的帖子
是否愿意拿来分享一下.
SophieDAD 2009-11-22 15:12
[quote]原帖由 [i]liduduma[/i] 于 2009-11-19 13:21 发表 [url=http://ww123.net/baby/redirect.php?goto=findpost&pid=6186884&ptid=4690696][img]http://ww123.net/baby/images/common/back.gif[/img][/url]
是否愿意拿来分享一下 [/quote]
不好意思，这个公式是递推公式：
设n是堆栈元素的个数，约定f(n)为这n个堆栈元素按堆栈规则进出所产生的排列数，并约定f(0)=1，则：
f(0)=f(1)=1;
f(n)=f(0)f(n-1) + f(1)f(n-2) + ...... +f(n-1)f(0);(当n>=2时)
若发现有错误，请见谅。
[em19].
页:
[1]