摘自：http://segmentfault.com/q/1010000000198718

戰(zhàn) 報交流：戰(zhàn)場上不同的位置有N個戰(zhàn)士（n>4），每個戰(zhàn)士知道當前的一些戰(zhàn)況，現(xiàn)在需要這n個戰(zhàn)士通過通話交流，互相傳達自己知道的戰(zhàn)況信息，每次 通話，可以讓通話的雙方知道對方的所有情報，設計算法，使用最少的通話次數(shù)，使得戰(zhàn)場上的n個士兵知道所有的戰(zhàn)況信息，不需要寫程序代碼，得出最少的通話 次數(shù)。

答案：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）,每組進行通信，每組中有兩人掌握了組內(nèi)所有信息，兩組中兩人分別交換信息，可以比2n-3少一次。
所以可以通過分組，減少通信次數(shù)。

詳解：

先思考這么個問題：

?

有a個node的cluster1和b個node的cluster2.(a>=2,b>=2) 如何連接使得cluster1,cluster2的node擁有cluster1和cluster2的全部信息？

1） 對于cluster1，必須存在一個狀態(tài)，即至少有1個node擁有cluster1的全部信息，因為我們的目的是擁有cluster1和 cluster2的全部信息。 此時至少需要a-1次連接，即單鏈，此時有且僅有2個node擁有全部信息。額外的a-2個node都不需要知道cluster1全部信息,因為如果要知 道就需要1次連接，但由于它還需要是知道cluster2的信息，因而還需要1次。后面我們發(fā)現(xiàn)這是多余的。

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個節(jié)點信息；

n-2個node至少需要n-3次連接，使得最后連接的2個node擁有這n-2個node的信息；

第一組的2個node與第n-2組的最后兩個node（即獲得該組全部信息的2個nodes）分別連接；?于是4個節(jié)點得到全部信息，連接了2次。這里是為什么節(jié)約了一次連接的關鍵。

剩下的n-4個node都沒有獲得全部信息，每個node至少需要一次連接。因此至少需要n-4次連接。用擁有全部信息的其中一個node與剩下的n-4個node連接。則只需要n-4次。

得總過需要1+(n-3)+2+(n-4)= 2n-4.

需要注意的是：每次連接有且僅有兩個node

你或許會問 為什么分成兩組。因為即使分成很多組，最終還是歸結(jié)為兩組的形式。

// 對于這點，有人還有些疑問，這里給出更多的說明。

假如分成3,4.5..個組。。當?shù)趉組（a個node）與第k+1組(b個node)混合一個組（cluster），至少需要的連接數(shù)1次，這種情況 下，有且僅有2個node具有這兩個cluster的全部信息。那么這個cluster至少有(a-1)+(b-1)+1 = (a+b)-1個連接，這與一個cluster的情況完全一致。

補充： y= 2n-4; 還可以使用數(shù)學歸納法證明。

k=4時，至少需要4次。4=2*4-4（自己畫圖試試吧）；

...

設k=n，y=2n-4;

k=n+1時，將信息傳遞過程分成兩個階段：1）收集所有node信息。2）收集完之后，分發(fā)給信息不全的node。收集第n+1個node的信息時1次，在分發(fā)全部時1個，共2個。得y = 2n -4 +2= 2(n+1)-4;

轉(zhuǎn)載于:https://www.cnblogs.com/zmlctt/p/3690959.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的阿里笔试题—战报交流的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。