4
回答
求大神解救C++一个组合问题的建模
注册华为云得mate10,2.9折抢先购!>>>   
每个girl身旁至少坐着一个boy。也就是说,最多只能有两个gril坐在一起。能计算符合位置安排有多少种吗?请注意这是个组合问题,不是排列问题。你编写程序的输入描述是:有多组输入,每组输入为两个正整数n和m(0<n<=30, 0<m<=10且m<=n/3),n表示班级总人数,m表示班里girl人数。输入数据处理到文件末尾。输出描述是:对每一组输入数据,输出不同位置安排的方法数量。每组输入的结果独占一行。
输入样例:
10 2
9 3
输出样例:
36

50

我的思路是这样的,设男的为0,女的为1,然后列出所有的情况,然后再去遍历每组,如果出现了相邻三个的和为3的话就不要这组。。。但是我觉得这样是不是效率太低了??还有其他的方法吗?请问有大神来教教我吗??

举报
共有4个答案 最后回答: 4年前


问一下,你那个10 2的输出样例是不是有问题?

当两个女生被男生分隔开的时候,就有36种情况:

GBGBBBBBBB, BGBGBBBBBB, BBGBGBBBBB, BBBGBGBBBB, BBBBGBGBBB, BBBBBGBGBB, BBBBBBGBGB,BBBBBBBGBG, 
GBBGBBBBBB, BGBBGBBBBB, BBGBBGBBBB, BBBGBBGBBB, BBBBGBBGBB, BBBBBGBBGB, BBBBBBGBBG,
GBBBGBBBBB, BGBBBGBBBB, BBGBBBGBBB, BBBGBBBGBB, BBBBGBBBGB, BBBBBGBBBG,
GBBBBGBBBB, BGBBBBGBBB, BBGBBBBGBB, BBBGBBBBGB, BBBBGBBBBG,
GBBBBBGBBB, BGBBBBBGBB, BBGBBBBBGB, BBBGBBBBBG, 
GBBBBBBGBB, BGBBBBBBGB, BBGBBBBBBG,
GBBBBBBBGB, BGBBBBBBBG,
GBBBBBBBBG
当女生在一起的时候,又有7情况:
BGGBBBBBBB,BBGGBBBBBB,BBBGGBBBBB,BBBBGGBBBB,BBBBBGGBBB,BBBBBBGGBB,BBBBBBBGGB


--- 共有 7 条评论 ---
大大大嘛嘛嘛@林大官 能加我扣扣讨论下??2109501082 4年前 回复
摩西.M回复 @林大官 : 围成圈的情况,我下面也有评论。。 4年前 回复
大大大嘛嘛嘛回复 @摩西.M : 如果是环状排列,那答案呢???好像好多人都认为是43种 4年前 回复
摩西.M回复 @林大官 : 晕倒!没看到你题目中说是环状排列! 4年前 回复
大大大嘛嘛嘛@林大官 因为这个是围成圈的 4年前 回复
参考思路:先把girls随便排个队,再把boys往girls里面插入,插入的唯一要求是至少插入一个boy在相邻两个girls之间。注意,队尾的下一位置是队头。不知可否。
--- 共有 2 条评论 ---
wharf_zhang这个地方输入排列组合公式太难了,只能大致说下我的思路,以9男3女为例:先把3个女孩子随便排队,记住这个队伍是环状的。接着,随便取9男中的3男(这是一个排列),分别放入3个女孩直接的空档。然后,从剩下6个男孩中取1~6个的组合,放入1、2号女孩间。依次类推,直到安排完。哎,不好描述,只能这样表达了。 4年前 回复
大大大嘛嘛嘛那个,可以给我一个简单的例子吗?一下子理解不了,就好比总共有9人,3女人,这种要怎么排 4年前 回复

如果像你说的,是围成圈的,那就更不对了。
10 2的情况 那只有5个答案了!
两个girl之间分开有4种:

GBGBBBBBBB,GBBGBBBBBB,GBBBGBBBBB,GBBBBGBBBB

两个girl在一起:
BBBBGGBBBB


从哪方面来说, 我都认为题目说的10 2的答案都不应该是36. 

如果你认为你理解了这个题目,那你把你理解的排列情况列出来就是了。 不要让别人猜来猜去。 如果题目无法理解正确, 何谈做正确这个题目!


顶部