戰(zhàn)報(bào)交流：戰(zhàn)場(chǎng)上不同的位置有N個(gè)戰(zhàn)士（n>4），每個(gè)戰(zhàn)士知道當(dāng)前的一些戰(zhàn)況，現(xiàn)在需要這n個(gè)戰(zhàn)士通過通話交流，互相傳達(dá)自己知道的戰(zhàn)況信息，每次通話，可以讓通話的雙方知道對(duì)方的所有情報(bào)，設(shè)計(jì)算法，使用最少的通話次數(shù)，使得戰(zhàn)場(chǎng)上的n個(gè)士兵知道所有的戰(zhàn)況信息，不需要寫程序代碼，得出最少的通話次數(shù)。算法該如何設(shè)計(jì)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）,每組進(jìn)行通信，每組中有兩人掌握了組內(nèi)所有信息，兩組中兩人分別交換信息，可以比2n-3少一次。所以可以通過分組，減少通信次數(shù)。我覺得即便求出最少值，算法也未必好實(shí)施。 容易實(shí)現(xiàn)的算法就是一個(gè)中心節(jié)點(diǎn)，2n-3次通信。
3 回答
POPMUISE
TA貢獻(xiàn)1765條經(jīng)驗(yàn) 獲得超5個(gè)贊
先是一個(gè)人和n-1人通話，之后就產(chǎn)生了2個(gè)全知的人，因?yàn)槭Ｏ耼-2個(gè)人都不全知所以至少要被再交互1次，并且此n-2個(gè)中任何兩個(gè)不全知的人交互都沒有意義，必須交互一個(gè)全知的人，這樣就產(chǎn)生了3個(gè)全知和n-3個(gè)非全知，同理這n-3個(gè)必須同那3個(gè)全知中的一個(gè)交互，以此類推，直到最后一個(gè)非全知被交互，所以是n-2，所以總共是n-1+(n-2)=2n-3
郎朗坤
TA貢獻(xiàn)1921條經(jīng)驗(yàn) 獲得超9個(gè)贊
這道題以前做過，正解應(yīng)當(dāng)是 2n - 3 。可以很容易證明增加一個(gè)人最多需要2次溝通（詳見下面的方案）。問題在于怎么證明增加一個(gè)人最少需要2次溝通。后者能證明的話，通過歸納法就可以很容易地得出這個(gè)結(jié)論。下面給出一個(gè)可能不夠嚴(yán)謹(jǐn)?shù)淖C明吧。
記最少的溝通次數(shù) y 為人數(shù) x 的函數(shù)， y = f(x)。
由于每次溝通只能在兩個(gè)人之間，在n個(gè)人里面收集所有信息，至少需要 n - 1 次溝通；某個(gè)人將自己的信息告訴所有其他人也至少需要 n - 1 次溝通。由于“同步信息”所需的次數(shù)顯然不可能少于收集信息，所以有 f(x) >= x - 1 。
將所有人分成 p 堆(1 <= p < n)，第i堆有 a[i] 個(gè)人。于是問題可以拆成3個(gè)步驟：
在每堆里面任選一個(gè)人收集該堆的信息，需要 sum(a[i] - 1) = n - p 次溝通。
在這些選出來的p個(gè)人中同步信息，需要 f(p) 次。于是這p個(gè)人都知道了所有的信息。
每堆內(nèi)再同步信息，又是 sum(a[i] - 1) = n - p 次。
總共需要 g(n, p) = 2(n - p) + f(p) 次溝通，所以 y = f(x) = max(g(n, p)) ，O(n^2)的算法，對(duì)于不大的n可以很容易地求出來這個(gè)最小值；當(dāng)然這不是我們的目標(biāo)。下面是重點(diǎn)，描述可能很奇葩，我盡量。。。
這時(shí)候如果新增一個(gè)人：如果把他放在任意一堆里面，那么至多且至少需要增加2次溝通（在1、3步里面各一次）；如果把他另起一堆，于是問題變成遞歸地求解 f(p+1) 比 f(p) 至少要增加幾次。
按照上面的邏輯，把這p+1個(gè)人分成q組（1 <= q < p)，新增的那個(gè)人所在的組 要么多于1個(gè)人（于是至少也要增加2次溝通），要么只有一個(gè)人（相當(dāng)于增加一個(gè)組），于是又變成遞歸地求解f(q) 比 f(q-1) 至少要增加幾次…… 不斷遞歸，最后組的數(shù)量會(huì)得到一個(gè)比較小的值，比如3，這時(shí)候就很容易證明，新增的這個(gè)人至少需要增加2次溝通才能夠同步信息。
證畢。
至于設(shè)計(jì)算法，那就太簡(jiǎn)單了：從a開始依次傳遞到z，然后在從y依次傳遞回a，這就是 2n - 3 次。如下所示：
a = b = c = …… = y - z
慕尼黑8549860
TA貢獻(xiàn)1818條經(jīng)驗(yàn) 獲得超11個(gè)贊
S1 S2 ... Sn
n個(gè)戰(zhàn)士，S1挨個(gè)和S2 S3 ... Sn交流，按照條件
每次通話，可以讓通話的雙方知道對(duì)方的所有情報(bào)
當(dāng)交流到Sn時(shí)，S1獲得了所有位置同時(shí)Sn也獲得了所有位置，接下來S1再和S2 S3 ... Sn-1 交流自己的信息，所有人都有信息了。
總數(shù) n-1 + n-2 = 2n-3
-----分割線------
如果解為2n-3，那么若有4個(gè)戰(zhàn)士，代入方程，得到結(jié)果 2*4-3=5，但是按照LZ的補(bǔ)充4個(gè)戰(zhàn)士的最小解可以為4，OMG。
所以就不妨參照4個(gè)戰(zhàn)士4次互通消息可以知道所有情報(bào)。
記下來每增加一個(gè)戰(zhàn)士X，X只要和戰(zhàn)士S1報(bào)告一下（是不是打入狼牙山4戰(zhàn)士?jī)?nèi)部了），然后4戰(zhàn)士交互完以后，X再和S1報(bào)告一下（套取內(nèi)部資料），結(jié)果X也有所有的情報(bào)了。
類推，只要戰(zhàn)士總數(shù)N>4,那么總次數(shù) Sum = (N-4)*2 + 4 = 2N-4
添加回答
舉報(bào)
0/150
提交
取消