阿里巴巴招聘笔试题2

题目：八卦消息传播时间

     假如我们班有n个MM，每一个MM都有一个独家八卦消息。两个MM可以通过电话联系，一通电话将使得双方都获知到对方目前已知的全部消息。要想所有n个MM都知道所有n条八卦消息，最少需要多少通电话？请给出你们的通话方案。

分析：

1、当n很小时我们很容易通过枚举的方法找出最佳通话方案：

  A1=0,A2=1,A3=3，A4=4，A5=6，A6=8…

2、下面对于n比较大的情况做进一步分析：

要想让n个MM共享所有n条八卦消息，最笨的方法莫过于每两个MM之间都通一次电话，这样共需要n*(n-1)/2通电话。但事实上完全没有必要这样做，因为在一次通话中如果通话双方所掌握的八卦消息不止一条，那么通话所交换的消息就会有多条，从而提高通话的效率、减少通话次数。解决这道题的关键所在就是如何设计通话方案，使得每次通话交换的信息量达到极大，使通话次数达到极小。

模型建立

    基于上面的想法，可以先把所有消息集中于一个或几个人，然后再由这些消息汇总人把消息传给所有人。设n个MM中有m个消息汇总人，她们共享所有消息需要打An通电话。

通话方案如下：

    第一步，剩下的n-m个MM每人从m个消息汇总人中随机选择一个人通电话。这样一来m个消息汇总人就掌握了所有n条八卦消息，并且她们每人所掌握的消息互不重叠，是互补的。

    第二步，m个消息汇总人通过打电话共享所有八卦消息。

    第三步，作为消息汇总人的m个MM再通过电话将自己新得知的八卦新闻告知最开始打电话给自己的MM，使她们也掌握所有n条消息。

    按照上面的通话方案，第一步需要n-m通电话，第二步需要Am通电话，第三步需要n-m通电话。故有An=2*（n-m）+Am，进一步化简得An=2*n-（2*m-Am）。

    即当MM的个数为n时，共享所有八卦消息共需要2*n-（2*m-Am）通电话。若要使通话次数最小，就要求2*m-Am最大。因此取多少个MM作为消息汇总人能使得2*m-Am最大就成为解决这个问题的关键，它反映了MM们之间通话的效率。记Em=2*m-Am。

当有一个消息汇总人即m=1时，E1=2*1-A1=2;

当有两个消息汇总人即m=2时，E2=2*2-A2=3；

                    m=3时，E3=2*3-A3=3；

                    m=4时，E4=2*4-A4=4；

                    m=5时，E5=2*5-A5=4；

                    m=6时，E6=2*6-A6=4；

                      ……

    由归纳法知当M>=4时Em有最大值4、An有最小值2*n-4，即当有大于或等于4个消息汇总人时可通过上述通话方案使n个MM通过最少的电话数共享所有八卦消息。此时共需要2*n-4次通话。