阿里笔试题战士传信问题

Q: 战报交流:战场上不同的位置有N个战士(n>4),每个战士知道当前的一些战况,现在需要这n个战士通过通话交流,互相传达自己知道的战况信息,每次通话,可以让通话的双方知道对方的所有情报,设计算法,使用最少的通话次数,使得战场上的n个士兵知道所有的战况信息,不需要写程序代码,得出最少的通话次数。

A:

  1. 分成两组:1) 2个node,2) n-2个node ;
  2. 2个node需要连接1次,使得2个node拥有2个节点信息;
  3. n-2个node至少需要n-3次连接,使得最后连接的2个node拥有这n-2个node的信息;
  4. 第一组的2个node与第n-2组的最后两个node(即获得该组全部信息的2个nodes)分别连接;于是4个节点得到全部信息,连接了2次。这里是为什么节约了一次连接的关键。
  5. 剩下的n-4个node都没有获得全部信息,每个node至少需要一次连接。因此至少需要n-4次连接。用拥有全部信息的其中一个node与剩下的n-4个node连接。则只需要n-4次。
  6. 得总过需要1+(n-3)+2+(n-4)= 2n-4.

需要注意的是:每次连接有且仅有两个node,即使分成很多组,最终还是归结为两组的形式。

提交看法

抢沙发

还没有评论,你可以来抢沙发