同学聚会

northwolves · 发表于 2010-1-8 17:20:36

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

理工大学90级外语系12个男生和8个女生携自己的老婆或老公参加大学同学聚会,晚餐时每桌10人,分别落座某饭店包间的A.B.C.D桌.为防止特殊情况的发生,大家一致决定该班的20位同学落座时遵循以下原则: 如果自己的配偶不与自己相邻,则不得与本班的异性相邻.客人则不受此限制.
问题: 有多少种落座方法?

northwolves · 发表于 2010-1-17 11:47:01

这个有点无从下手,谁能给个提示?

shshsh_0510 · 发表于 2010-1-18 22:23:16

所以嘛，同学聚会千万不能带家属！

mathe · 发表于 2010-1-19 08:39:43

穷举吧,规模不大.

northwolves · 发表于 2010-1-19 19:22:24

穷举吧,规模不大.
mathe 发表于 2010-1-19 08:39

递归没有合适的出口,主要是筛选前的基础排列:40!/10^4,44位数

medie2005 · 发表于 2010-1-19 20:10:58

本帖最后由 medie2005 于 2010-1-19 20:39 编辑

5# northwolves
应该是:XXXXX

northwolves · 发表于 2010-1-19 21:48:57

5# northwolves
应该是:XXXXX
medie2005 发表于 2010-1-19 20:10

5位数?不会吧?

KeyTo9_Fans · 发表于 2010-1-19 23:37:36

可以不区分4张桌子、12个男生、8个女生，但配偶要区分，所以基础排列可缩减为

40!/12!/8!/4!=1.76e+33

随机落座4亿次，有690682次符合规则。

所以概率约为0.001726705。

如果按照40!的全排列计算，共有大约

40!*0.001726705=1.41e+45

种落座方案。

mathe · 发表于 2010-1-20 07:44:55

看来规模有点大,可以试着用动态规划解决,问题规模同下面不定方程的非负整数解数目相关
$2*x_1+x_2+x_3+2*y_1+y_2+y_3=k$
其中要求$x_1+x_2<=12,x_1+x_3<=12,y_1+y_2<=8,y_1+y_3<=8$
而k=11和k=22可以分别用来估计问题的空间和时间复杂度.
这个方法Fans应该非常熟悉.

shshsh_0510 · 发表于 2010-1-20 08:25:03

首先考虑4个桌子的合并问题，可以从一个固定的位置拼接，然后再考虑所产生的问题。
其次，对一个桌子n男生，m女生,可以这样考虑递归步：由N(n,m)插入新男生，求N(n+1,m)
上面只为楼主提供点思路，我也没仔细想，不一定可行

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 同学聚会

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。