多人之间消息共享问题的算法设计

问题描述：有N个人，每个人都掌握一定的消息，如果两个人之间共享之后，这两个人就会掌握彼此全部的消息，那么如果这N个人中每一个人都掌握全部的消息，请问，怎样设计算法才会使共享次数最少？

设计思路是这样的，在N个人中找出M个作为消息收集的人，N-M个人，每人随机从M中找到一个人，将消息汇报给他，M个人彼此进行消息共享，N-M个人再随机找到M中的一个人做信息共享，这样每个人都会掌握N个人的所有信息；

分为三步：

第一步，N-M个人，每人随机从M中找到一个人，做信息共享，分享次数是N-M

第二步，M个人彼此进行消息共享，我们可以假设N个人想共享全部信息，最少的分享次数是Min（N），则M个人彼此进行消息共享就是Min（M）

第三步，N-M个人再随机找到M中的一个人做信息共享，共享次数是N-M

所以有等式Min（N） = N-M+Min（M)+N-M=2N+Min（M)-2M 

如果要使Min（N)最小，即让Min（M)-2M最小，

下面用归纳法，

M=0            Min（M)-2M =0

M=1            Min（M)-2M =-2
M=2            Min（M)-2M =-3

M=3            Min（M)-2M =-3

M=4            Min（M)-2M =-4

M=5            Min（M)-2M =-4

M=6            Min（M)-2M =-4

  .....                   ........

由归纳法知，M>=4的时候 Min（M）-2M有最小值-4

此时Min（N）有最小值2N-4

最后

以上就是虚心猫咪为你收集整理的多人之间消息共享问题的算法设计的全部内容，希望文章能够帮你解决多人之间消息共享问题的算法设计所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。