Question

怎样用c++建这个问题的数学模型？

围一个圈，每个女生身旁至少坐着一个男生。也就是说，最多只能有两个女生坐在一起。这样的围圈用c++怎么去实现？如何建模？个人想了想这是个组合问题，但是思路不清晰，有大神指点下吗？？

Answer 1

重点在女生，对男生没限定，但是题目没给定男女人数，那么这两个是函数参数，或者说模型输入数据。输出有两种，一种是模式判定，给定一个序列检查是否匹配要求，一种是自动排列，给定男女人数，程序自动排列。

自动排列时，可以先通过判断男女人数差，检查数据有效性，标准情况下，男女应该对等，这样正好一个挨一个，如果男生数量大于女生，肯定有效，如果允许存在全部男生的情况，女生与男生之比的下限是无限小，但如果女生大于男生，其极限是2:1，因此数据有效性就女生/男生之比<=2。

当然程序中还要考虑头尾相连时的边际检查，假设0代表女，1代表男，那么这种序列是无效的："001110"，因为头尾相连女生连续挨着3个了，考虑到这些后就可以写程序了，使用char 数组。

自动排列，给定X和Y，分别代表男生女生数量，假设女生/男生比<=2,则系统自动从男生开始排列，这样可以不用在遇到数组尾部时再去验证头部女生排列状态。循环中按照比例，每排一组男生X-n，直到X=0，然后再根据比例排一组女生，Y-m，0<=m<=2。直到X和Y均为0.

至于检查匹配就简单了，循环遍历数组，如果是女生，且女生计数为2则报错，否则计数器加1，（如果为数组尾部，检查数组头是否为连续>=2女生，是就报错），如果为男生，计数器清零。

循环正常结束返回true，报错就是返回false，随便写写，希望对你有帮助。

追问

谢谢你的思路，但我还是不明白，不过通过你的思路，我想到了，用01分别代表男女，然后再排列出2的n次方种排列方式，然后把这些排列方式存到一个2维数组中，最后逐个遍历相邻三个数，使他们相加，如果结果为3的话就删除。小弟知识尚有缺漏，望指点指点

追答

你这种方法是排列组合，而且是逐一尝试所有组合，然后将有效组合存入数组，那这个组合超大，人数越多，组合按指数级增长。
我还是用具体人数举例说明给你看。比如同样是3女2男，女=0，男=1，以下组合都是有效的
00101
01001
01010
10100
01001
10010
一共6种，但其实就是一种，因为数组中可以是6种组合，但围成圈去看其实就是一个序列，只是不同的相位。这样做一侧浪费空间浪费运算时间，二则算法冗余。

我的思路很简单，就是按照规则，首先通过男女比例剔除无效数列，而无需一个个组合去测试，因为如果女生大于男生的情况最多是2女1男的排列，超过1个女生就不符合要求了，因此女生数量除以男生数量的比极限就是2:1，比值就是2，大于2说明给定人数无效。

人数比例有效性检查
设X为男生数量，Y为女生数量
设X=2，Y=3，S=Y/X=3/2=1.5=1（人数不能为小数所以取整，不四舍五入），小于2所以参数有效。

因为男生为分母，所以男生默认为单组1个，而女生单组人数就是S。
设女生单组人数n=S=1，男生单组人数m=1

循环排列方法
排一组男生再排一组女生，如果女生用完补完全部男生（男生多的情况），每排一次，X,Y相应减去人数，当X和Y全部为0结束循环。
所有参数如下
X=2，Y=3，m=1，n=1
下面是循环排列每个步骤的结果
循环1
1 X-m=1
10 Y-n=2
循环2
101 X-m=0
1010 Y-n=1
循环3
10100 X为0不排，Y-n=0
X和Y全为0，结束。

一共3个循环，代码应该很容易写，也不用二维数组，也不用一个个尝试所有组合。

追问

不好意思，还有一个问题，那就是如果像10010这些其他情况应该怎么求出？

追答

你要的不是排成圈吗？一组男女排成圈就不存在头尾，谁都可能是头谁都可能是尾，一个排列代表所有组合，只是内存数组是线性的，但按题意逻辑上是个循环链。

但如果你一定要取出所有组合，有了正确的排列，其他组合随便取啊，左移右移都可以，而且实际上根本不用移动数组元素，只要给定一个起始索引，循环取出所有组合还不简单，又不占内存。
假如原始排列：10100，起始索引设为index，取出时最多建一个临时数组
index=1 01001 （左侧1元素右移移到数组右侧）
index=2 10010 （左侧2元素右移移到数组右侧）
........
index=4 01010 （左侧4元素右移移到数组右侧）
动态输出，而且灵活，编写一个函数给定一个起始索引作为参数，也就是指定第几个人为头。

追问

！！！！刚刚懂了！！原来是这样子！！真的太感谢了！！！好激动！！！！

追答

呵呵，也谢谢你，这题目不错的，搞搞脑子对遇到实际问题时可以有很大帮助。

追问

在吗？？

现在我的问题是，那个男生人数是肯定大过女生的，然后我看回你的解释就懵了，里面还有个限制因素就是（0<n＜30;0＜m＜10;m＜n/3）,n是总人数，m是女生人数，例如n=10,m=2,则有36种位置排法，n=9,m=3,则有50种，这个一下子转不过来，请问能再解释下吗？

追答

我觉得不难啊，本来女生比男生<=2啊，上次不是帮你分析过了，按照题意，女生：男生不能超过2:1，超过就是无效参数，或者说无解。2:1是极限，所以你说m<n/3这个限制不就是出题的让参数有解吗。

比如n=10，m=2，好吧男生数量a=n-m=8，就一种排法
女生/男生S=m/a=2/8=0.25
i=1（男生单组人数）
j=S=1（女生单组人数，人数不能为小数,只要有余数就为1，保证最小单位）

循环1
1 a-i=7
10 m-j=1
循环2
101 a-j=6
1010 m-j=0
循环3
10101 a-j=5
由于m为0补齐所有男生
1010111111
结束
关键是你还是停留在排列组合上，你自己检验下结果是否满足要求，另外你要的排列组合位移几次不就完了。
0101111111
1011111110
0111111101
........
这题目的组合就是等于总人数。有多少人就有多少组合，其他都是无效组合，要踢除的，根本不用一个个去尝试，模型的意义就在于此，优化算法，此题的关键是男女比例，采用排列组合是有前提的，就是要保证所有组合都是有意义的。

追问

😂😂😂如果两个女的挨在一起呢

😂😂😂第一次遇到实际问题建模，所以想弄懂一下套路

再如果三个女人，六个男人，是不是应该分为两种，一种为单组为一个女的，一种为单组两个，另一组为一个？

好像你上面的1010111111这种不是最多10次吗，还有两个女的中间不是应该还有两个或者三个男人，或者没有人的情况吗

追答

哦，这样啊，我以为只要满足“每个女生身旁至少坐着一个男生”就可以了。
如果要在踢除无效组合后的所有组合列出，我再想想。

追问

好比这个是一个团队，每个人都是独立的个体，你之前说的，我算了下都算不出36种😂😂😂

😓😓😓请问你对哈希表熟悉吗

追答

从来没用到过，加密和定位用的，看过，麻烦死了。

追问

不是用于查询的吗？那如果实现二进制的输入储存单词，然后输入一串二进制码的时候，输出英语句子。请问这个应该怎么实现

二进制输入的问题我想到了，用一个二维数组来解决，把二进制代码和他们代表的单词储存进去，然后再通过字符串数组来保存，再通过用指针来一个个检索一段二进制码的内容，把它保存在一段字符串中，如果发现匹配的二进制码就输出它所代表的单词，然后再把字符串清空。这样可以吗？？但是觉得效果好慢

追答

哈希函数就是用一种算法n=f(key)，将一个key转换成一个整数值，和key一起保存到一张表内，一般key就是个字符串，是个关键词或者某种名称，这张表叫哈希表，以后要查某个键的时候还是用f(key)获得一个值，然后到哈希表内查询该值是否存在。据说效率很高，但是他有重码的缺点，所谓冲突，当重码很多时性能会下降，具体应用我没测试过，哈希函数可以自定义，由于哈希函数依赖算法，所以如果算法没优化，算法测试也是个很大的工程。我觉得实际编程中还真没遇到过必须要用哈希函数的情况，查询哈希表不是也要遍历吗？这点我没搞清楚。还有种应用就是加密。

输入二进制码输出句子？我没理解目的是什么。

追问

就是好比“010”对应一个单词hi "011"对应hei 输入010011就会输出hi hei这样的句子

追答

二进制用字符串存储？太浪费空间了吧，直接存无符号整数不行？如何数据不都是二进制？我理解你的二进制一定是个ID，ID为什么要用二进制串？

追问

也可以是整数

#include
#include

int main () {
std::map dict;
dict["010"] = "hi";
dict["011"] = "hei";
std::cout << dict["010"] << " " << dict["011"] << std::endl;
return 0;
}

这条哈希语句正确吗

追答

你定义的是键值对，从代码上看和C#的词典类差不多，但C++这种定义我真没用过，我现在要实现具体问题都是用C#，方便，哈希我没用过，所以对不对我不清楚。

追问

😂😂😂女生的那个问题弄清楚了吗，

😂😂😂话说应该学c#还是java好？？我打算深入一个语言

追答

如果按照你的要求列出所有组合，有点麻烦，不过隐约感觉需要用递归。否则排列组合代码太复杂，我觉得可以实现不过太费脑子。

追问

不用列出来

只要列出有多少种就可以了

就是说明有多少种，

😂😂😂我也觉得要用递归，就是找不到递归方程

追答

问题是这种需要推导的，你不列出来怎么验证你的模型正确。如果按照你的要求，加入2女8男情况下，分两种情况
两女排在一起，这种情况下，如果你按线性排列有10种
0011111111
1001111111
1100111111
以此类推，也就是我之前说的移位；但我觉得既然围成圈，应该算一种。只有在线性情况下才有意义，所以你的题目还是要确定下。
两女隔开，这种情况下又分好多种
0101111111
0110111111
......
可见，其实就是俩女之间隔多少男生，但问题是围成圈的话，又怎么判断以下两种是否算一种组合：
0101111111
0111111101
从线性角度看，第一种排列两女隔一个男生，第二种是两女之间隔7个男生，但是围成圈的话其实是一样的。因为第一种情况，起始位置从第二个女生开始算的话，也是相隔7个男生，因为是环形的，所以我觉得这个题目要求不清晰，既然围成圈了这两种组合其实是一种。
再看下面的组合
0111101111
这种情况两边都是4个男生，对称的，所以如果按圆圈观察，实际只有5种
0011111111
0101111111
0110111111
0111011111
0111101111
在这5种基础上对每个组合位移9次，也就是每种是10种组合，那么5*10=50，我想这就是你的要求吧。你就按这个思路将5和10推导出一个公式就行了，太费脑子了。

追问

😂😂😂但是那种情况只有36种，我都不知道怎么算的

我也想过那样的情况啊，但是给出的例子是36种，6男3女才50种

😂😂😂😂神坑

原题目是这样的

追答

这是学校的题目吗？我觉得现在的题目出得很坑，要求不明确。

追问

是啊😂😂😂也不是不想自己来想这个问题，实在想不出

不是，有些旁白，我删除了，主要信息都在里面

😂😂😂终于知道为什么10个人那个是36种

单个女的在一起应该是7654321=28然后两个女的在一起，把两个看做一个整体，然后就有九个位置，然后因为围圈所以第一个和最后一个位置是一样的，所以只剩下8个位置。但是如果三个女的呢😂😂😂我又懵了