经理有4封信先后交给打字员，要求打字员总是先打最近接到的信。比如：正打第3封信时第4封信到了，应立即停下第3封信，转打第4封信；第4封信打完后，接着打第3封信，而不能先打第1或第2封信。问：打字员打完这4封信的先后顺序有多少种可能？

答案为什么是14？.

个趟HY路考试就有这道题目，就是一只只排，好像，明朝帮侬问儿子哦.

我给我女儿看了一只只排的图，我女儿就问了一个问题，我就憋特了。.

注意到两点：1）信是按一定顺序发给打字员的；2）打字员打完的信的数量是不可能超过来信的数量的。化归思想，由此用横坐标表示来信，纵坐标表示打完的信，转化为求最短线路的走法数量问题，但纵坐标的值不能大于横坐标的点不能取。
顺便说一下这是一个组合计数里卡特兰数的问题，计算机里叫堆栈问题。

比较同类的一题：爸爸、妈妈饭后一起洗8个花纹互不相同的盘子，爸爸按一定的顺序洗盘子（设为A-B-C-D-E-F-G-H），洗好后一个一个往上摞，妈妈再从最上面一个一个地拿走放入碗柜摞成一摞，爸爸一边洗妈妈一边拿，问妈妈摞好的盘子一共有______种不同的摞法。.

哪能家高深饿啦.

1.png (30.48 KB)

2009-11-18 10:41

2.png (32.3 KB)

2009-11-18 10:41

3.png (29.64 KB)

2009-11-18 10:41

这种题目至少应该是高中生看的

[ 本帖最后由 xyq2100 于 2009-11-18 10:43 编辑 ].

可是摞碗问题我们刚刚上四年级学加乘原理的时候就见过了,应该和LZ的那个是一样的,就是一个一个排可能性..

请参见附图.

真清楚，呵呵

看了题目第一反应是这个经理有毛病的.

同意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种

[ 本帖最后由 liduduma 于 2009-11-18 11:44 编辑 ].

同意，个饿经理是伐大正常.

肯定不对！第一封信未完，第二封信完成后也有两种可能，一种是打第三封还有一种是打完第一封！同理，第三封信完成后不只是做第四封，还有可能是第二封，还有可能是第二封后打第一封，然后才是第四封！.

你的图不完整吧，比如从上往下数第3枝就不完整。
1完，2未完，3完，以后，不一定是来4，也可以是2完，再来4.
所以你的图里没包括1324这样的顺序
总之，你的图例很清楚，但只列了8种顺序，需要再完备一些。
我同意10楼的答案，14种。.

嗯，回复有理，请以图上作一更正，应该考虑后一封未来时，前一封已完，但再前一封可以先进行的情况。.

有意思的解释！我曾经偷闲写过一篇关于堆栈序列的文章，还总结了一个堆栈序列数目的公式。
.

是否愿意拿来分享一下.

引用:

原帖由 liduduma 于 2009-11-19 13:21 发表
是否愿意拿来分享一下

不好意思，这个公式是递推公式：
设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时)

若发现有错误，请见谅。
.