校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 设计和思维考察 > 阶段分析能力
题目

有100个球,甲乙轮流拿,每次最少拿1个最多拿5个,甲先拿,请问怎么拿能保证最后一个球是甲的?

解答

正确的拿法是:

甲先拿4个,后续拿球数 = 6 – 乙的拿球数

分析过程:本题可以用大葱分析法来分析。

甲先拿,第1次甲,第2次乙,第3次甲,4次乙,5次甲…..,如果最后一个球是甲的的话,那甲拿最后一次,那就意味着甲乙拿球次数加起来一定是奇数。我们得到了“条件集合”的第一个条件:甲乙拿取总次数是奇数。

然后看题目,题目中每次最少拿1个最多拿5个,这是一个变量,我们在这里简化问题,假定每次固定拿N个。

那同时问题就转化成了:甲乙每次拿固定个数N个球(不够N有多少拿多少),必须要拿奇数次。每次拿1个?pass。每次拿2个?pass。每次拿3个?需要拿34次,pass。每次拿4个?需要拿25次,目前是满足的。每次拿5个?pass。

ok,那就甲先拿,甲乙每次都拿4个。至此我们简化的问题得以解决,我们进一步释放一些“复杂”出来,每人每次拿1~5个球不等。假设我们是甲,这个复杂点在于我们根本没法控制乙拿多少个球,人家不听我们的,“复杂”果然不好对付,那怎么办?

我们可以看到无论甲拿一次还是乙拿一次,都是在向外拿球。我们现在对问题进行简化,让拿球粒度变粗,我们拿球不再分甲乙,如果把甲乙各拿一次定义为一个回合的话,我们现在只关注回合拿球个数H。

这时我们发现一个问题就是,一个回合的定义是甲乙各拿一次,而我们先前“条件集合”里的第一个条件是“甲乙拿取总次数是奇数”,这就意味着我们会得到“半个回合”,这个“半个集合”对应甲或乙的一次拿球,而且总回合次数是个偶数。

因为我们此前释放了“复杂”,每次最少拿1个最多拿5个,所以单个回合拿球个数H也不确定,最少2个,最多10个。

注意,这里有个双重变化量。就是回合间步调不一致,而且单个回合内拿球数也不确定。我们现在简化一下问题,降低一下复杂度。就是让回合间步调一致,但保留“单个回合内拿球数不确定” 这个变化量。这个时候我们会发现如果回合间步调保持一致,那“单个回合内拿球数不确定” 这个变化量也就不存在了,因为能满足条件的H值只能是6。

也就是说,我们现在需要解决的问题就是,100除以一个数H有余,且得数是偶数,余数在1~5之间,且H只能等于6,那结果已经出来了。

100除以6,得16,余4。

简化后的问题得以解决,现在开始释放“复杂”。我们先恢复拿球粒度,细化到甲乙各自拿球。

按照上述方案,我们只要维持回合拿球次数恒定,就能解决问题。而回合的定义是甲乙各拿一次,且题目规定甲先拿,貌似我们又回到了刚才那个问题,就是无法控制乙拿球个数,从而无法控制回合拿球数恒定。问题虽然还是那个问题,但是我们现在手头所拥有的资源不一样了,我们有了“半个回合”的概念,也就是余数的概念,这是很重要的一点。

另外一点我们有回合的概念,虽然不能控制乙的拿球个数,但是我们可以控制回合的拿球个数,那就是让乙先拿,我们根据乙的拿球数来确定我们的拿球数从而达到控制回合拿球数的目的。题目虽然是甲先拿,但如果我们把甲的第一次拿球看做是那个“余数”的话,那我们真正的回合开始是从乙先拿开始,而乙先拿恰恰能让我们后发制人控制回合拿球数,最终使算法题得以解决。

甲先拿4个,后续拿球数 = 6 – 乙的拿球数

问题解决了,但是我们发现还有一个“复杂”没有释放,就是“回合间步调不一致”。可是我们问题已经解决了,这说明什么,说明那是我们虚化出来的复杂度,而实际结果和这个复杂度并无关联。这也是大葱分析法提倡简化问题,降低复杂度的原因所在。

C 0条回复 评论

帖子还没人回复快来抢沙发