战报交流：战场上不同的位置有N个战士（n>4），每个战士知道当前的一些战况，现在需要这n个战士通过通话交流，互相传达自己知道的战况信息，每次通话，可以让通话的双方知道对方的所有情报，设计算法，使用最少的通话次数，使得战场上的n个士兵知道所有的战况信息，不需要写程序代码，得出最少的通话次数。
我能想到的最少通话次数等于2n-4,不知正解为多少
算法该如何设计
a,b,c,d,e.通话
a--b,b--c;d--e;b--d;c--e;a--(b or c or d or e)。 6次通信
通过分组（a,b,c;d,e）,每组进行通信，每组中有两人掌握了组内所有信息，两组中两人分别交换信息，可以比2n-3少一次。
所以可以通过分组，减少通信次数。
我觉得即便求出最少值，算法也未必好实施。 容易实现的算法就是一个中心节点，2n-3次通信。
信息走向图如上，走了不到两圈。由于仅走一圈的有两步，因此2(n-1)-2 = 2n - 4。另外一种思路见下图，分治法，n分成最小为4个战士的单元，然后每层进行通信。同样是2n-4。
S1 S2 ... Sn
n个战士，S1挨个和S2 S3 ... Sn交流，按照条件
每次通话，可以让通话的双方知道对方的所有情报
当交流到Sn时，S1获得了所有位置同时Sn也获得了所有位置，接下来S1再和S2 S3 ... Sn-1 交流自己的信息，所有人都有信息了。
总数 n-1 + n-2 = 2n-3
-----分割线------
如果解为2n-3，那么若有4个战士，代入方程，得到结果 2*4-3=5，但是按照LZ的补充4个战士的最小解可以为4，OMG。
所以就不妨参照4个战士4次互通消息可以知道所有情报。
记下来每增加一个战士X，X只要和战士S1报告一下（是不是打入狼牙山4战士内部了），然后4战士交互完以后，X再和S1报告一下（套取内部资料），结果X也有所有的情报了。
类推，只要战士总数N>4,那么总次数 Sum = (N-4)*2 + 4 = 2N-4
智商低，所以算法题一般喜欢画图来分析。
1~4 步：收集信息，即 N-1 次
5~7 步：同步信息，即 N-2 次
最后可得：(N-1)+(N-2) == 2N-3
这里可能会有一个错误
在到最后一步时，将 2号 与 3号 进行交换信息，要注意，他们分别只掌握了前2个和前3个的信息，都没有第4个的信息，他们的交换无法得到全部的信息。
这道题以前做过，正解应当是 2n - 3 。可以很容易证明增加一个人最多需要2次沟通（详见下面的方案）。问题在于怎么证明增加一个人最少需要2次沟通。后者能证明的话，通过归纳法就可以很容易地得出这个结论。下面给出一个可能不够严谨的证明吧。
记最少的沟通次数 y 为人数 x 的函数， y = f(x)。
由于每次沟通只能在两个人之间，在n个人里面收集所有信息，至少需要 n - 1 次沟通；某个人将自己的信息告诉所有其他人也至少需要 n - 1 次沟通。由于“同步信息”所需的次数显然不可能少于收集信息，所以有 f(x) >= x - 1 。
将所有人分成 p 堆(1 <= p < n)，第i堆有 a[i] 个人。于是问题可以拆成3个步骤：
- 在每堆里面任选一个人收集该堆的信息，需要 sum(a[i] - 1) = n - p 次沟通。
- 在这些选出来的p个人中同步信息，需要 f(p) 次。于是这p个人都知道了所有的信息。
- 每堆内再同步信息，又是 sum(a[i] - 1) = n - p 次。
总共需要 g(n, p) = 2(n - p) + f(p) 次沟通，所以 y = f(x) = max(g(n, p)) ，O(n^2)的算法，对于不大的n可以很容易地求出来这个最小值；当然这不是我们的目标。下面是重点，描述可能很奇葩，我尽量。。。
这时候如果新增一个人：如果把他放在任意一堆里面，那么至多且至少需要增加2次沟通（在1、3步里面各一次）；如果把他另起一堆，于是问题变成递归地求解 f(p+1) 比 f(p) 至少要增加几次。
按照上面的逻辑，把这p+1个人分成q组（1 <= q < p)，新增的那个人所在的组 要么多于1个人（于是至少也要增加2次沟通），要么只有一个人（相当于增加一个组），于是又变成递归地求解f(q) 比 f(q-1) 至少要增加几次…… 不断递归，最后组的数量会得到一个比较小的值，比如3，这时候就很容易证明，新增的这个人至少需要增加2次沟通才能够同步信息。
证毕。
至于设计算法，那就太简单了：从a开始依次传递到z，然后在从y依次传递回a，这就是 2n - 3 次。如下所示：
a = b = c = …… = y - z
|| 说明： 为了讲得更详细，下面说得比较啰嗦。
先思考这么个问题：
有a个node的cluster1和b个node的cluster2.(a>=2,b>=2) 如何连接使得cluster1,cluster2的node拥有cluster1和cluster2的全部信息？
1） 对于cluster1，必须存在一个状态，即至少有1个node拥有cluster1的全部信息，因为我们的目的是拥有cluster1和cluster2的全部信息。 此时至少需要a-1次连接，即单链，此时有且仅有2个node拥有全部信息。额外的a-2个node都不需要知道cluster1全部信息,因为如果要知道就需要1次连接，但由于它还需要是知道cluster2的信息，因而还需要1次。后面我们发现这是多余的。
A_1 ->A_2->A_3....->A_{a-1} -> A_a //A_{a-1},和A_a拥有A_1,A_2,A_3,..A_a的全部信息。
2） 对于cluster2也一样，至少需要b-1次连接使得B{b-1}和Bb拥有B1,B2,...B{b-1},Bb的全部信息。额外的b-2个node都不需要知道cluster2全部信息
3） 当cluster1和cluster2连接时，我们希望所有node都拥有全部信息。只有且仅有A{a-1}，Aa与B{b-1},Bb连接一次，才能使得有node具有cluster1和cluster2的全部信息。当有一个node具有全部信息时，它与其他任何node1次连接就能使该node得到全部信息，这也是为什么上面说多余。
A{a-1} 与B{b-1} ， Aa与Bb （或A{a-1}与Bb， Aa 与B{b-1}）共两次连接,使得这4个node拥有全部信息。
除了这4个node外，其他node相互连接都无法得到全部信息。
这4个node与，其他node 通过一次连接使得该node 具有全部信息。
///////////////////////////////////////////////////////////////////////
- 分成两组：1) 2个node，2) n-2个node ;
- 2个node需要连接1次，使得2个node拥有2个节点信息；
- n-2个node至少需要n-3次连接，使得最后连接的2个node拥有这n-2个node的信息；
- 第一组的2个node与第n-2组的最后两个node（即获得该组全部信息的2个nodes）分别连接； 于是4个节点得到全部信息，连接了2次。这里是为什么节约了一次连接的关键。
- 剩下的n-4个node都没有获得全部信息，每个node至少需要一次连接。因此至少需要n-4次连接。用拥有全部信息的其中一个node与剩下的n-4个node连接。则只需要n-4次。
- 得总过需要1+(n-3)+2+(n-4)= 2n-4.
需要注意的是：每次连接有且仅有两个node
你或许会问 为什么分成两组。因为即使分成很多组，最终还是归结为两组的形式。
// 对于这点，有人还有些疑问，这里给出更多的说明。
假如分成3,4.5..个组。。当第k组（a个node）与第k+1组(b个node)混合一个组（cluster），至少需要的连接数1次，这种情况下，有且仅有2个node具有这两个cluster的全部信息。那么这个cluster至少有(a-1)+(b-1)+1 = (a+b)-1个连接，这与一个cluster的情况完全一致。
补充： y= 2n-4; 还可以使用数学归纳法证明。
k=4时，至少需要4次。4=2*4-4（自己画图试试吧）；
...
设k=n，y=2n-4;
k=n+1时，将信息传递过程分成两个阶段：1）收集所有node信息。2）收集完之后，分发给信息不全的node。收集第n+1个node的信息时1次，在分发全部时1个，共2个。得y = 2n -4 +2= 2(n+1)-4;
先是一个人和n-1人通话，之后就产生了2个全知的人，因为剩下n-2个人都不全知所以至少要被再交互1次，并且此n-2个中任何两个不全知的人交互都没有意义，必须交互一个全知的人，这样就产生了3个全知和n-3个非全知，同理这n-3个必须同那3个全知中的一个交互，以此类推，直到最后一个非全知被交互，所以是n-2，所以总共是n-1+(n-2)=2n-3
我简单的模拟了几个数字，得出一下结论：
n r
1 0
2 1
3 3
4 3
5 6
6 8
......
所以可以得出结论: 2n - 4
我想应该是2n-3,设a,b,c,d，e,e告诉d，d告诉c，如此类推，b告诉完a之后，其实a,b都知道所有人的情报了，此时只需要c，d，e都知道即可。假设每两个人之间的通话不重复，即a和b不会产生两次对话，那么上述情景则需要通话2n-3;