战报交流：战场上不同的位置有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。
我想应该是2n-3,设a,b,c,d，e,e告诉d，d告诉c，如此类推，b告诉完a之后，其实a,b都知道所有人的情报了，此时只需要c，d，e都知道即可。假设每两个人之间的通话不重复，即a和b不会产生两次对话，那么上述情景则需要通话2n-3;
先是一个人和n-1人通话，之后就产生了2个全知的人，因为剩下n-2个人都不全知所以至少要被再交互1次，并且此n-2个中任何两个不全知的人交互都没有意义，必须交互一个全知的人，这样就产生了3个全知和n-3个非全知，同理这n-3个必须同那3个全知中的一个交互，以此类推，直到最后一个非全知被交互，所以是n-2，所以总共是n-1+(n-2)=2n-3
这道题以前做过，正解应当是 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个步骤：
总共需要 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
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 回答1.1k 阅读✓ 已解决
1 回答1.1k 阅读
1 回答1.4k 阅读
1.2k 阅读
959 阅读
821 阅读
795 阅读
极客观点
项目管理
HarmonyOS
|| 说明： 为了讲得更详细，下面说得比较啰嗦。
先思考这么个问题：
有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次。后面我们发现这是多余的。
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 具有全部信息。
///////////////////////////////////////////////////////////////////////
需要注意的是：每次连接有且仅有两个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;