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，即使分成很多组，最终还是归结为两组的形式。

chao

微信支付

支付宝