阿里巴巴2014校招笔试题

题目:宿舍内有五个童鞋一起玩对战游戏,每场比赛有一些人作为红方,另外一些人作为蓝方,请问至少需要多少场比赛才能使得任意两个人之间有一场红方对蓝方和一场蓝方对红方的比赛,请写出思路。

分析:

先把问题一般化,假设宿舍有n个人一起玩对战游戏。

当n=2时,只需进行1场比赛;

当n=3时,假设是a,b,c三人,首先三人都要进行比赛,需要进行两场,此时会出现两红一蓝或者两蓝一红的情况,此时再将两红或两蓝进行一次对战,得到的结果是一红一蓝还有一个两色,所以共需进行3场比赛

当n=4时,同理,先最少要进行2场比赛,让4人都参加,然后会出现两红两蓝的情况,再将这两红和两蓝各自进行对战,得到的结果就是一红一蓝还有两个两色的,所以共需进行4场比赛

可以总结下,首先要进行n/2场比赛(这里n/2不是取整,比如3/2在这里等于2),而且只能保留一个红色和一个蓝色,其余的人都必须是两色,所以还要再进行n-2场比赛

最后得到T(n)=n/2+(n-2)场比赛。

T(5)=5/2+(5-2)=6场比赛。

原文地址:https://www.cnblogs.com/riskyer/p/3323216.html