戰報交流：戰場上不同的位置有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次通信。
3 回答
POPMUISE
TA貢獻1765條經驗 獲得超5個贊
先是一個人和n-1人通話，之后就產生了2個全知的人，因為剩下n-2個人都不全知所以至少要被再交互1次，并且此n-2個中任何兩個不全知的人交互都沒有意義，必須交互一個全知的人，這樣就產生了3個全知和n-3個非全知，同理這n-3個必須同那3個全知中的一個交互，以此類推，直到最后一個非全知被交互，所以是n-2，所以總共是n-1+(n-2)=2n-3
郎朗坤
TA貢獻1921條經驗 獲得超9個贊
這道題以前做過，正解應當是 2n - 3 ?？梢院苋菀鬃C明增加一個人最多需要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
慕尼黑8549860
TA貢獻1818條經驗 獲得超11個贊
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