本文主要是介绍【IQ题】三人行 组合问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题来自 阿里巴巴 技术岗位的一道笔试题:
有个学校的15个女生一直3个一群上学。请问该如何安排才能使这些女生每周7天每天都和两个不同的同伴结伴同行呢？例如：用A到O来标识这些女孩，7天A正好和B到O这14个女孩各同行一次。而B到O每个人和都和其他14个女孩各同行一次。
这道问题看起来好像挺简单的,但做起来真好不搞.研究了两个小时,总结一下...
其实解题思路就是要你找出所有的三人组合,而且这个三人组合里面不能有重复过的两人组合.
三人组合所有情况:C315=------------------ = 35 × 13 种
3×2×1
但是,三人组合显然不是我们想要的,因为里面有太多的重复了
题目要的就是每两个人之间在一起只出现过一次,所以先考虑二人组合
15×14
二人组合所有情况:C215=------------------ = 15 × 7 种
2×1
就好比如题目的A~O标号同学,对于二人组合,就有
AB,AC,AD,AE,AF,AG.......AM,AO;
BC,BD,BE,BF,BG......BM,BO;
.........
NM,NO;
MO;
然后通过研究得出了以下几点结论:
结论1.
三人行, 说明是这三个人的组合,是三个组合, 而且成为了一个环.
就比如 ABC 这三个同学吧, 他就是AB,BC,AC这三个组合而来的一个环.
同样,ADE这三个同学,就是有二人组合可能性里面的AD,DE,AE构成的.
至于为什么要说他是一个环?
这个很重要,真的.......我一开始忽略了一点,就随便拿起来就组合...结果多出了几个剩男剩女..(不
上面题目说了,组合只能出现一次,
比如你最后多出了EI,FH,CE,CH,BF,BI,这里六个组合,理应还能再组成两队人的.
可惜不成环,所以就失败了.
结论2.
三人行问题,先求出二人组合,二人组合搭配数整除3,得出的就是可行的不同组合.
题目的15人求三人行.二人组合有105种,除3之后就是最多有35个环,刚好5组×7天 =35
题目得解.
不能整除3的话,呵呵!
结论3.
每一个三人组合,是三个二人组合连接而成.同时,每一个同学,在这三个二人组合里面,都出现了2次.
比如ABC这个三人组合,是由AB,AC,BC这三个二人组合而来的.同时A出现了2次,B出现了2次,C也出现了2次...
听上去好像很白痴的结论,其实这个很重要.
我就换个问题说吧,假如把题目的15个人改成6个人里面求三人行的组合呢?
咋一算,
6×5
二人组合所有情况:C215=------------------ = 3 × 5 种
2×1
再除以3,得到5个环.按照结论2来说应该有5个环,就是可以有五种组合才对.
可不,你可以尝试用ABCDEF这六个代号去试试画连通图.
假如ABC成了一个环, ADE成了一个环, AF就是剩男剩女了.
上面就说了,一个环内的一个代号至少出现两次.
ABC中A在AB,AC出现. ADE中在AD,AE中出现.
那么AF无论跟谁怎么组合,都不可能成环了.
所以结论就是总人数必须是奇数才不会有人多出来.
解决方法这么一来就有很多了,可以用广度搜索树,可以用队列,也可以用图...
为了怕麻烦就换个简单点的数据.比如9个人求三人行的组合可能情况.
首先 ,根据结论1
9×8
二人组合所有情况:C2 9=------------------ = 36 种
2×1
由结论2得出 36÷3=12 ,说明理应可以构成12个环
9个人是奇数,也满足结论三.
标号 ABCDEFGHI
组合的可能情况
ABC ADE AFG AHI
BDF BEI BGH (第二个为啥不是BEG呢,因为BHI是不行的,要跳着来组合,学着点)
CDH CEG CFI
DGI EFH
三人组合所有情况:C315=------------------ = 35 × 13 种
3×2×1
这篇关于【IQ题】三人行 组合问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
