谜题|信息传播

一个班有n个学生，每个学生都有一个不同的有趣故事。由于学生们在课堂上感到无聊，他们决定想出一个游戏来打发时间。他们想通过发送电子信息相互分享有趣的故事。假设一个发送者包含了他或她在消息发送时知道的所有有趣的故事，并且一条消息可能只有一个收件人。为了保证每个人都能得到所有有趣的故事，他们需要发送的最少消息数是多少？

解决方案： 最小消息数等于2n–2。有几种方法可以做到这一点。

方法1： 学生们可以指定一个学生，比如说学生1，其他人向他发送他们知道的有趣故事的信息。在收到所有这些信息后，学生1将所有有趣的故事与他或她的有趣故事结合起来，并将此组合信息发送给其他n-1名学生。可以通过下图来理解。将n名学生表示为S1、S2、S3等…………。。，Sn。学生指定每一个其他学生用他们知道的有趣故事向其发送信息的S1。

在收到所有这些信息后，学生1将所有有趣的故事与他或她的有趣故事结合起来，并将此组合信息发送给其他n-1名学生。因此，最小消息数等于2n–2。

方法2（贪婪算法）： 将学生从1到n编号为S1，S2，S3，…..，Sn，并按如下方式发送前n-1条消息：从S1到S2，从S2到S3，依此类推，直到消息结合了学生S1，S2，Sn–1被发送给n个人。然后，将包含来自学生n的所有n个有趣故事的消息发送给学生S1、S2、，Sn–1。

因此，最小消息数等于2n–2。

注： 2n–2条信息是解决难题所需的最小数量，这一事实源于这样一个事实，即学生数量增加一条，至少需要两条额外的信息，即发送给额外学生的信息和来自额外学生的信息，这正是上述方法所提供的。

参考： 算法谜题——阿纳尼·莱维廷、玛丽亚·莱维廷