life02

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  197 随笔 :: 3 文章 :: 37 评论 :: 0 Trackbacks
作者:baihacker
来源:http://hi.baidu.com/feixue http://hi.csdn.net/baihacker

问题描述:
12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
这个笔试题,很YD,因为把某个递归关系隐藏得很深.

问题分析:
我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排.
用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案.
比如000000111111就对应着
第一排:0 1 2 3 4 5
第二排:6 7 8 9 10 11
010101010101就对应着
第一排:0 2 4 6 8 10
第二排:1 3 5 7 9 11
问题转换为,这样的满足条件的01序列有多少个.
观察1的出现,我们考虑这一个出现能不能放在第二排,显然,在这个1之前出现的那些0,1对应的人
要么是在这个1左边,要么是在这个1前面.而肯定要有一个0的,在这个1前面,统计在这个1之前的0和1的个数.
也就是要求,0的个数大于1的个数.
OK,问题已经解决.
如果把0看成入栈操作,1看成出栈操作,就是说给定6个元素,合法的入栈出栈序列有多少个.
这就是catalan数,这里只是用于栈,等价地描述还有,二叉树的枚举,多边形分成三角形的个数,圆括弧插入公式中的
方法数,其通项是c(2n, n)/(n+1).

在 < <计算机程序设计艺术>>,第三版,Donald E.Knuth著,苏运霖译,第一卷,508页,给出了证明:
问题大意是用S表示入栈,X表示出栈,那么合法的序列有多少个(S的个数为n)
显然有c(2n, n)个含S,X各n个的序列,剩下的是计算不允许的序列数(它包含正确个数的S和X,但是违背其它条件).
在任何不允许的序列中,定出使得X的个数超过S的个数的第一个X的位置.然后在导致并包括这个X的部分序列中,以
S代替所有的X并以X代表所有的S.结果是一个有(n+1)个S和(n-1)个X的序列.反过来,对一垢一种类型的每个序列,我们都能
逆转这个过程,而且找出导致它的前一种类型的不允许序列.例如XXSXSSSXXSSS必然来自SSXSXXXXXSSS.这个对应说明,不允许
的序列的个数是c(2n, n-1),因此an = c(2n, n) - c(2n, n-1).[Comptes Rendus Acad.Sci.105(Paris, 1887), 436~437]

验证:
其中F表示前排,B表示后排,在枚举出前排的人之后,对应的就是后排的人了,然后再验证是不是满足后面的比前面对应的人高的要求.
C/C++ code
#include <iostream> using namespace std; int bit_cnt(int n) { int result = 0; for (; n; n &= n-1, ++result); return result; } int main() { int F[6], B[6]; int ans = 0; for (int state = 0; state < (1 << 12); ++state) if (bit_cnt(state) == 6) { int i = 0, j = 0; for (int k = 0; k < 12; ++k) if (state&(1<<k)) F[i++] = k; else B[j++] = k; int ok = 1; for (int k = 0; k < 6; ++k) if (B[k] < F[k]) {ok = 0; break;} ans += ok; } cout << ans << endl; return 0; }
结果:132
而c(12, 6)/7 = 12*11*10*9*8*7/(7*6*5*4*3*2) = 132
注意:c(2n, n)/(n+1) = c(2n, n) - c(2n, n-1)

估计出题的人也读过 < <计算机程序艺术>>吧.

PS:
另一个很YD的问题:
有编号为1到n(n可以很大,不妨在这里假定可以达到10亿)的若干个格子,从左到右排列.
在某些格子中有一个棋子,不妨设第xi格有棋子(1 <=i <=k, 1 <=k <=n)
每次一个人可以把一个棋子往左移若干步,
但是不能跨越其它棋子,也要保证每个格子至多只有一个棋子.
两个人轮流移动,移动不了的为输,问先手是不是有必胜策略.
posted on 2009-10-17 22:18 life02 阅读(318) 评论(1)  编辑 收藏 引用 所属分类: 笔试

评论

# re: 阿里巴巴试题(转) 2009-10-20 11:51 马良庄
关于移动旗子的问题:
先手是有必胜的策略的。

用奇偶性可以证明的。

对于整个序列,任何两个棋子中间有空的格子(不过多少个空格)的空段数的奇偶性是可以保持的。
例如后手移动B旗子
A_____B_____C (情况1) (空段数为偶数)为
A_B_________C
如果移动C要产生新的空段数(例如C后边紧跟着D),则:
A_BC_________
如果移动C不产生新的空段数(例如C是最后一个或者后边本来为空格),则:
A_B_____C____ C向前移动与B相同的步数。

如果后手将(情况1)移动为:
AB__________C
则先手将根据移动C是否会产生新的片段作出相应的应对:
ABC__________ 或
AB___C_______

对其他情况,例如
A______BC
等情况都有应对方法保持整个序列的空段数奇偶性不变,保证交到后手手上时空段数为偶数,则可以保证先手获胜。  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理