我能想到的最少通话次数等于2n-4,不知正解为多少啊？

Question

战报交流：战场上不同的位置有N个战士（n>4），每个战士知道当前的一些战况，现在需要这n个战士通过通话交流，互相传达自己知道的战况信息，每次通话，可以让通话的双方知道对方的所有情报，设计算法，使用最少的通话次数，使得战场上的n个士兵知道所有的战况信息，不需要写程序代码，得出最少的通话次数。算法该如何设计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次通信。

Answer 1

先是一个人和n-1人通话，之后就产生了2个全知的人，因为剩下n-2个人都不全知所以至少要被再交互1次，并且此n-2个中任何两个不全知的人交互都没有意义，必须交互一个全知的人，这样就产生了3个全知和n-3个非全知，同理这n-3个必须同那3个全知中的一个交互，以此类推，直到最后一个非全知被交互，所以是n-2，所以总共是n-1+(n-2)=2n-3

Answer 2

这道题以前做过，正解应当是 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个步骤：

1. 在每堆里面任选一个人收集该堆的信息，需要 sum(a[i] - 1) = n - p 次沟通。

2. 在这些选出来的p个人中同步信息，需要 f(p) 次。于是这p个人都知道了所有的信息。

3. 每堆内再同步信息，又是 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

Answer 3

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